SRM607
レート1220でDiv1に参戦。今回はKawigiEdit+Emacsでコード書く設定を整えてスタート。
Easy
部分回文の個数の期待値を計算する問題。部分文字列ごとに「ワイルドカード'?'の出現ごとに26で割った数」を足せば答えが出る、というところまでは開始5,6分で分かってコーディング開始。部分文字列のサイズごとにウィンドウをずらしていく、というコードでテストケース通ってサブミット。ここまでで25分くらい。幸先いいように見えた。
しかしチャレンジフェーズでレッドコーダーに飛ばされる。通った人のコードを見ても期待値の計算方法自体は変わらないのでしばらく分からなかったが、どうやらウィンドウをずらしていく方式だと計算量がO(N^3)のオーダーになるのが問題だったようだ。通った人のコードはみんなウィンドウ方式を使ってないので不思議だったが、O(N^2)にするためだったのか、と。最大でN=2500なのでN^3だとちょっときつい。
Medium
ダイヤル錠を開けるのに必要な最小ステップ数を求める問題。グリーディーにやって問題ないかを5分くらい検討したのち、コーディング。しかしゼロをまたぐ距離の計算に手間取ってかなり時間を消費してしまって終わらなかった。通った人のコードをみて (x - y + 10) mod 10 って書けばシンプルだと気づく。
一番エレガントだったのは、まず解錠番号を「全てゼロ」に置き換えておいて、全てをゼロにするには番号をそろえる回数が問題になるから隣同士の番号の差を出発点にして回数をカウントしていく、というコード。その人のコードだけはやたら短くて分かりやすかった。
Hard
開いてない
結果&所感
結局ゼロ点で 1220 -> 1213。一応次回もDiv1参戦できるようだ。今回は難しかったみたいで、レッドコーダーやイエローコーダーでもバタバタと不正解の人がいたし、Hardは誰も解けてなかったようだった。
自分としてはコード書く前の分析は改善したと思う。あとは、エレガントな解を考えるようにしてコード量を減らしたり、DPじゃないときのオーダーを意識するくらいかなぁ。