Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #7 (参加記録) (この記事を編集する[管理者用])

2010年04月02日00時45分から2時間,5問.

A. Kalevitch and Chess

8*8のグリッドで最初全部のマスが白い.
コスト1である行,または,ある列の全てのマスを黒くできる.
目的の盤面にするための最小コストを求める問題.
目的の盤面にできることは保障されている.

2^16通り全部試せば良いよね.
で書いたけど,最初,与えられた盤面から,何回白く塗りつぶすことで,真っ白にできるか,と勘違いしてWA.
その後AC.

B. Memory Manager

メモリ確保,開放のシミュレーションをする問題.
詳細は問題文参照.

書くだけ. 送る.ちょっと書き方ミスってWA.
直して送る.WA.
メモリは確保されてるところに番号,そうでないところは0と管理してたんだけど,erase 0で成功してることになってた.
直して送る.AC.

C. Line

整数A, B, Cが与えられるので,Ax+By+C=0の整数解を1つ求める問題.
存在しないならそれを指摘する.

拡張互除法は何か苦手.
ってことで,コピペ.
C mod GCD(A,B)が0じゃないとき,解は存在しない.
後は適当に書く.送る.WA.
うーん.
十数分ぐらい悩んでわからないので次.

D. Palindrome Degree

回文Aの次数を,Aの前半と後半が次数k-1の回文だったら次数kとする.前半と後半が回文じゃなければ次数1.
与えられた文字列の全てのprefixの次数の和を求める問題.
文字列の長さは5000000以下.

rolling hash使ってO(1)で回文判定すれば宜しい.
回文だったら,自分の半分の長さのprefixの次数+1にすれば良いので,DPできる.
ごにょごにょ書くだけ.
なんか答え合わないな.
無理やり合わす.送る.WA.ですよね.
ちゃんと考える.うん,rolling hashの式違う.直す.送る.WA.
うーん.
十数分悩む.
回文判定するのに,文字ひっくり返して一致してるかどうか調べないといけないのに,ひっくり返してない…,おいおい.
直す.送る.AC.

C. Line (再)

そういえば,互除法って負の値送ると死ななかったっけ?
死ぬじゃん.
絶対値取るようにする.送る.AC.

E. Defining Macros

C言語のマクロと,それを使った式が1つ与えられるので,
 マクロを関数みたいに思って展開したとき
 C言語の使用と同じように,マクロを置換で展開したとき
で式の評価の順番が変わるかどうかを調べる問題.
ただし,任意の変数で結果の変わらないものは評価の順番が変わっていても変わっていないとみなす.

定数も変数も全部乱数にして,式を2通りの方法で評価して,結果が一致するかどうか見れば良いのでは?
とか思ったけど,構文解析実装問題は苦手だなぁ.
残り時間ではできる気がしないので,放置.

Result

相変わらず酷い成績.こういう問題苦手なんだろうなぁ.
ちなみに,ICPCの国内予選とか日本のアジア地区予選の問題も酷く苦手.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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