過去問はじめて解いた
TopCoderの過去問を初めて解きました。
プログラミングの勉強になると聞いて気になっていたのですが、解けなかったら情けないな〜と思って尻込みしていました。…が、やりもせずにできないと嘆くのはどうかと思い、やってみることに。
SRM305 div2 (250)
問題
- プロセスがリソースを読み書きすることを表すログ(「RRRRWR」のような文字列)と、割り当て可能なプロセス数を与えらてたとき、最低何クロック必要かを答えよ。
- 書き込みと読み込みを混ぜることはできない。
- 同時に複数のプロセスが1つのリソースに対して書き込みはできない。が、同時に複数のプロセスによる読み込みはできる。
自分の解答
高得点の人のコードを読んで思ったこととか
コードが短い。単純な処理で済むものは単純に書いている(つまり可読性を犠牲にして切り詰めているわけではない)。自分は、ムダに配列に変換したり、ムダに変数を使って状態を保持したりしていた。
あと、一瞬で判定できるケースは、さっさと答えを出してreturnするらしい。計算量を考えたらそういうケースもあるんだろうけど、思いつかなかった。
SRM313 div2 (250)
問題
- 正方形が左から右にn個並んでいる。正方形には数字(1〜n)か書かれている。
- 任意のインデックスにある正方形を選び、数字を見て、そのインデックスの正方形に移動する、ということを繰り返す。最初に選んだインデックスの正方形に戻ったら終わり。
- 正方形の並びを与えられたとき、最大何手になるか計算せよ。