SRM604(Div2) 自戦記

最近Topcoder SRMを毎回やってます。今回のSRM604はレート1187でDiv2に参戦。

レベル1

Javaのsubstringを使えばOK。 境界条件に気を付けてsubmit。

レベル2

問題を読み終わって座標のイメージを浮かべたら3進数で表現してXORしたら全部1になればOKだと気付いてそのように実装。残り60分くらいでサブミット。調子いい。

あとで配列を使わずに解いてる人のコードを見てちょっと冗長だったと気付く。

レベル3

部分木を数える問題だってことは直ぐ分かった。部分木の根でDPの分割をすれば解けると思ってDFSでコード書き始めたが、子の数が3個以上ケースを考えてなかったのでいったん立ち止まって検討。子ノードを一番左と残りに分割すればよいと分かった時に大体残り35分。

それでノードの親子関係のデータを作ってDFSのコードを大幅に修正。そのときに子への再帰と兄弟への再帰で関数を分けて書いたのだが、途中で関数は1個で良いことに気づいてまた修正。

そうこうしてるうちに残り10分。あとは頑張ったけどタイムアップ。通った人のコードを見る限り方針はあってた。

結果と反省

レベル1,2が通ってレート1274。とりあえず最高レート更新。次回またDiv1に復帰で楽しみ。

反省点としては大きな方針だけでなくもう少し実装の細かいところもコード書く前に少し検討したほうが良さそうだというところ。

今年の目標:4/1までにイエローコーダー(1400)、12/31までにレッドコーダー(2200)