Codeforces Round#3 Beta
A : Shortest path of the king
今回は４問セットなのか。
8x8チェス盤のマスAからマスBまでキングが移動する時の最小手数を求める。
障害物などはない。
ただの実装だけれど、移動方向が8方向あるので場合分けが少し面倒。
20分かかった。赤い人たちはみんな5〜10分程度で解いている。
B : Lorry
重さが1と2の荷物しかないナップサック問題の特殊版。
なので次のようなGreedyでいける。
- 重さ1の荷物のうち最も価値の高い二つと、重さ2の荷物のうち最も価値の高い一つを比べて重さ2の荷物のほうが高かったらそれを入れる
しかし問題文には同じ荷物を２度以上つかってはいけないとは書いていない。
何度か読み直すも記述がないので↑を仮定して、書いて送ってみる。
WA→じゃあ使っていいのか？→WA→仮定はただしいけど単にコードが間違ってる？
いろいろ直しながら試す→WAのスパイラル。
ACが出たのはWA8回を出し、問題を読み始めてから1時間半が経過した終了10分前。
CとDは放棄。
結果
3問以上といているのが全体の半分くらいだった。よって半分より結構下。
問題はTopCoderのSRMDiv1より嫌らしい気がするんだけれど……
TopCoderとは違いレートがすぐ算出された。
名前が緑色（初期レート未満の証）に。
考察とか
まず（僕が解いている序盤の）問題の特徴としては、アルゴリズムや数学的考察より正確な実装力・問題読解能力を問う傾向が非常に強いことが挙げられる。
- 解法はやや自明であるが実装において場合分けが多い
- サンプルが恐ろしく不親切
のでサンプルデバッグ便りの適当なコーディングができず、
コード量も多くなるので実装力が問われるという意味である。
これは実装力やデバッグ力を鍛える非常にいいチャンスであるように思う。
複雑なコードをバグを出さずに書き切れれば必然的にコーディングのスピードも向上するし、サンプルがなければ自分ではまりそうなテストケースを作る練習もできる。
Red Coder達との差が一番大きいのもこのあたりであると思うし。
