CODE FESTIVAL 予選突破練習会 参加レポート
一度競技プログラミング系のオフラインイベントには行きたいと思っていたので,思ったら即実行という感じでなんだか自分が参加しても大丈夫そうなイベントがあったので参加しました!
若さオーラを感じながら(人通りは少なかったが)久々に駒場に.KOMCEE周辺がかなり様変わりしていました.
参加者の中では自分は間違いなく年長者に区分されていたはず(大学生が多く,高校生も少数いた).
内容は予選のD相当の難易度の問題を解いていこうというもの.問題の内容については特に触れませんが(atndのリンクにある問題を解いていました),一つの問題に対し複数人で意見を出し合うのは5,6年ぶりで気分だけでも若くなれて参加して本当に良かった.
今週末はまあ,あまり気張らずに普段通りいこうと思います.どうやらDPが出題される説が濃厚のようですね.
やはりモチベーションを上げながら続けるにはライバルが必要.
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
原作: