Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1640-41db22da
この記事にトラックバックする(FC2ブログユーザー)

SRM485 DIV1 参加記録 (この記事を編集する[管理者用])

2010年10月21日20時02分から.

Assignment

マラソンの覇者とSPOJの覇者と同じ部屋.
250-500-1000の標準セット.

EASY

1以上1000以下の奇数の正整数からなる数列が与えられる.要素の数は4以上50以下.
好きな要素に好きなだけ2をかけていいから,等差数列にしてくださいという問題.
複数答えがあるなら,辞書順最小のものを求める.

問題文長い!
と思ったらそんな感じでもなく,すんなり意味が理解できる.
1つ目の要素と2つ目の要素を全探索するだけで良いよね.
それぞれ適当に2^40まで掛けてみて,残りは等差数列ということから一意に定まるからvalidかどうか判定するのみ.
がりがり.
コンパイルー.
コンパイルできねー,反応返ってこねー.
もう1回.
できた.サブミット.

MEDIUM

50*50以下のグリッドを白か黒に色を塗る.
すでに塗られているマスと塗られていないマスが与えられたとき,validの塗り方が何通りあるか求める問題.
validな塗り方は,a != b, c != dで
 board[a][c], board[a][d], board[b][c], board[b][d]
が全部同じ色ではないこと.

50*50だと!?
長方形の中全部同じ色だと駄目なんだから,2*2の長方形だけ考えれば良いよね.(問題読み間違えてる)
うーん,わからん.
包除原理…できないなぁ.
うーん,うーん.
実は高さか幅の小さいほうが8以上だと答え0なんじゃないの?
だったらbit DPでいける.
証明は…できない.
問題をもう1回読んで考えよう.
あれ,これ条件違うんじゃない?
違うよ,問題読み間違えてるよ,制約もっと厳しいよ!
じゃ,尚更答えなさそうじゃん.
幅と高さの小さいほうが10より大きいと0を返して,後はbit DPする!
で,10*10の?を突っ込んで答えが0なら提出だ!
かきかき.
答え合わねー.
いや,違うじゃん,問題読み間違えてたんだよ,制約違うよ.
あれ…,bit DPできないじゃないか….
紙の上でいろいろ例を考える.
これ,高さと幅の小さいほうが3以上だとあんまり作れないんじゃ….
とりあえず,高さが1の時のコードと,高さが2の時のコードを書く.
1は自明.2の時は?
うーん….
幅が大きいと,WWをたかだか1回使えて,BBをたかだか1回使えて,残りはWBかBW.
WWを使う行,BBを使う行を全探索して足し合わせれば良さそう.
かきかき.
幅3以上は….
全探索のコードをとりあえず書く!
書いた,サンプルは全部通る.
さて,大きいのを突っ込んだら0になるかな?
なる!
高さ3だと幅7以上で0かな,高さ4でもだ.
高さ5だと,幅5以上で0.
高さの方が低いと最初に転置する.
てか,全探索すぐ終わるなー.
ちょっと余裕もっと大きめにしておこう.
サブミット.
いろいろテストする.
1x50の?…OK.
50x1の?…seg falut.え?
!!
1の時の処理が,転置したやつじゃなくて,引数をそのまま見てる!
何やってるんだ…,修正,リサブミット.
うげー,これでだいぶ順位下がったなぁ….

HARD

2つの凸多角形がある.1つはもう片方の内部に含まれている.
外側の多角形の辺上を1つランダムに選び,そこから直線距離で最も遠い外側の多角形の点に向かって線を引く.
最も遠い点が複数あるなら,ランダムに選ぶ.
その線が,中にある多角形と1点でも重なっている確率を求める問題.

残り10分でまさかの幾何.
あれ…,これ普通に解けそうじゃないか….
どうせ一番遠い点って頂点のどれかな気がするし….
でも,10分で実装は不可能….
諦めて,250, 500の見直しすべし.

Challenge

勘違いして2失敗.もう500提出組の中では底辺に近かったからあんまり気にしない.と思ったけどやっぱり痛い.

System tests

Systestは通る.でも完全敗北.
部屋内では,順当に,マラソン覇者とSPOJ覇者がワンツーフィニッシュ.

番外編: DIV2 EASY (診断人師匠のニコ生中)

末尾に9が続く数字は安く見えて魅力的な数字である.
a以上b以下の整数で末尾に9ができるだけ長く続く数字を求める問題.
同じだけ続くなら,その中で最も大きい物を求める問題.
aとbは1以上1000000以下.

サンプル見て意味理解.
書く.
脊髄反射で9が含まれる数全部数える.
提出.249.25点.システムテスト落ちた.
DIV2最下位からやり直したほうが良い….

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1640-41db22da
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。