Codeforces #325 Div.2
結果:A,Bの2完.Cは普通の実装がTLEだと思い込み,Dは問題の意味を読み違えていた.非常に悔しい思いをした回でした.
レート変動:1630 -> 1619 (-11)
Cがかなり注意力の必要な実装だったらしく,かなりの人がsystestで落ちていて奇跡的に青維持という結果に.次失敗したら後がないですが・・
続きを読むyukicoder No.287 場合の数
組み合わせ★3.
問題ページ: No.287 場合の数 - yukicoder
貪欲にaからhまで順番にそれまでの総和としてあり得る数字を作る組み合わせをそれぞれ調べる.
のDPで解きました.
あまりにもすんなり通ってしまったのでひょっとしたら★2相当かもしれませんね.
Codeforces #323 Div.2
結果:A,Bの2完.C解けるべきでした・・結果的に大きい方から貪欲にとるだけの解法で,実装も軽くそりゃそうかという感じ.multiset使うのが短くて済むのですが,ポインタ使わずにできないものか(集合の中身の値を見るのにポインタしか手段がないのか?).Dも考えていたのですが結局ACならず.どうやら行列累乗のテクニックを使うそうです.ちょうど次解こうと思っていたyukicoderの問題が毛色の似た問題だったことを知って後悔しています・・次あたりでその問題レポかD問題復習をしようと思います.
レート変化:1661 -> 1630 (-31)
2問しか解けなければさすがに下がるか.
そういえばCodeforcesのレーティング割り振り大きく変わりましたね.青が1600-1899になり,div1入りがますます遠くなってしまいました・・まあdiv1入って2問解けないような実力のうちはdiv2で得点を安定させるのを目指した方が良さそう.
yukicoder No.225 文字列変更(medium)
DP★3.レーベンシュタイン距離の実装問題.スペルチェッカーなどに使うのだそう.
参考:
No.225 文字列変更(medium) - yukicoder
解答:愚直に実装しました.DP用マトリクスを作って順に埋めていく感じがわかりやすくていいですね.
似たようなアルゴリズムにDTWを連想しました.これに関しても何か面白い問題がありそう.
yukicoder No.238 Mr. K's Another Gift
文字列★3.実装力が鍛えられる自分的良問でした.vector<char>なんて配列,使う必要なかったかもしれない.
方針:先頭と末端両方から文字列を比べる.イテレータを両端においてスタートし,同じ文字であればその文字を別の配列(C)に格納.もし同じ文字でなければその次の文字まで見る.1度しか現れなかった文字の方をCに格納.これが文字挿入に相当する(1回までの制限).後は文字数の偶奇で場合分けで回文を生成.
No.238 Mr. K's Another Gift - yukicoder
原作:
CODE FESTIVAL 2015 予選A
結果:A,B,Cの3完.DはずっとN<100のケースを通す方法もお思いつかず1時間が経過し,直前で答えありきで順繰りにできるか確かめる方法と2分探索を思いつき,悔しい思いをしました・・予選Bは後悔のないようにしたい.
下はACした解答.
intにするとオーバーフローする計算があるので注意が必要.