2015-10-29

競技プログラミングを始めて2ヶ月が経ちました

General

唐突ですが，直前のエントリーで話題にしたCODE FESTIVAL予選B，通過していました．久しぶりにこの種類の嬉しさを噛み締めています．というのも，大学に入ってからは評価というものは公正でないものも多く(これは考え方の問題ですが)，評価の仕方も教官によってまちまちだったのですが，今回はオートジャッジによる絶対評価と順位が1人単位でわかり，1つ順位を上げる価値が場所によってはとても大きくなるというもので，大会ならではという感じがします．自分がかつて参加した中で一番近いのだと数学オリンピックがそれにあたりますね．さすがにオートジャッジではなかったですが・・

決勝はベテラン勢が上位を制するのは見えているのですが，それでもあと半月あがいて納得できる成績を残したいです．具体的な数値目標としては上位半分(つまり100位以内)に入ることでしょうか．

かつて数学の大会の虜になったのも，中学入りたての当時とりあえずと参加した数学の大会で学内唯一予選を突破し決勝では運良く準優勝したのが，その後高校卒業までモチベーションを上げ続ける最大のトリガーだった記憶があるので，この年ながら競プロでもいい流れを作っていきたいなどと思っています．

さて，競技プログラミングを始めて2ヶ月が経ちましたが，今のところの到達度を書いておきます．もし競プロ始めたての方が万が一この記事を読まれていたら参考にしていただけると嬉しいです．

TopCoder Rate: 1131(緑, Highest)
Codeforces Rate: 1619(青, Highest: 1661)
ABCは全完できるようになった(始めてから皆勤で全回全完)
yukicoderを★3を中心に70問弱解いた(知らないアルゴリズムに関しては解説や他人のソースコードを見ながら学んだ)
CODE FESTIVAL 2015予選突破

当然ですがまだまだコーディングスピードや思考速度は遅く，あらゆるコンテストに出て上位を狙う，というアクロバティックなことはできないので，TopCoder, Codeforces, AtCoderを軸としてちょっとづつ手を広げられれば良いと思っています．

アルゴリズム的な知識や実装技量に関しての自己評価も載せておきます．

実装系の問題は思考終了から実装に落とすまでの時間がまだ長い
STLのコンテナのメンバ関数の扱いは未だ不慣れ(mapにlower_boundがあることを知らなかったり)
DPはメモ化再帰方式だったり更新則が少し変わると対応できないことが多い
DFS，BFSに関しては理解したつもりだが，まだコンテストでの使用経験が少ない
Binary Search, Binary Index Treeなど計算時間が対数時間だったり1クエリに対して対数時間の処理で済むアルゴリズムやデータ構造は未習部分が多い．Segment Tree早く理解実装できるようにならないと・・
TLEが起きなさそうか起きなさそうかの見極めが甘い
貪欲に関してはあまり深く考えずに使うことが多い
整数・行列の累乗やmodに関する処理に関してはある程度は慣れた(気がする)

今はyukicoderを中心に各種アルゴリズム習得に利用しているのですが，AtCoderの問題は問題文も理解しやすく問題もいくらか洗練されている気がするので，ある程度までやったら今度はARCの過去問を中心に進めていく予定です．

CODE FESTIVAL 2015 予選B

AtCoder

結果：3完 + 40点．

順位：110位

A通過を除くとどうやらギリギリ80位以内に入っているみたいですが・・結果を待つのみ．

code-festival-2015-qualb.contest.atcoder.jp

区間を管理する解法ですが，STL不慣れが原因で時間がかかってしまった．コンテスト中の40点解法はlower_boundを使わない方式で，それ以外は特に変わりません．以下ACしたコード．

CodeFes2015B_D

2015-10-20

CODE FESTIVAL 予選突破練習会参加レポート

Events

一度競技プログラミング系のオフラインイベントには行きたいと思っていたので，思ったら即実行という感じでなんだか自分が参加しても大丈夫そうなイベントがあったので参加しました！

atnd.org

若さオーラを感じながら(人通りは少なかったが)久々に駒場に．KOMCEE周辺がかなり様変わりしていました．

参加者の中では自分は間違いなく年長者に区分されていたはず(大学生が多く，高校生も少数いた)．

内容は予選のD相当の難易度の問題を解いていこうというもの．問題の内容については特に触れませんが(atndのリンクにある問題を解いていました)，一つの問題に対し複数人で意見を出し合うのは5,6年ぶりで気分だけでも若くなれて参加して本当に良かった．

今週末はまあ，あまり気張らずに普段通りいこうと思います．どうやらDPが出題される説が濃厚のようですね．

やはりモチベーションを上げながら続けるにはライバルが必要．

2015-10-14

Codeforces #325 Div.2

結果：A,Bの2完．Cは普通の実装がTLEだと思い込み，Dは問題の意味を読み違えていた．非常に悔しい思いをした回でした．

レート変動：1630 -> 1619 (-11)

Cがかなり注意力の必要な実装だったらしく，かなりの人がsystestで落ちていて奇跡的に青維持という結果に．次失敗したら後がないですが・・

2015-10-10

yukicoder No.287 場合の数

組み合わせ★3．

問題ページ： No.287 場合の数 - yukicoder

貪欲にaからhまで順番にそれまでの総和としてあり得る数字を作る組み合わせをそれぞれ調べる．

$dp(i,j) = \sum_{k=0}^{n} dp(i-1,j-k)$ のDPで解きました．

あまりにもすんなり通ってしまったのでひょっとしたら★2相当かもしれませんね．

yukicoder No.287

2015-10-04

Codeforces #323 Div.2

結果：A,Bの2完．C解けるべきでした・・結果的に大きい方から貪欲にとるだけの解法で，実装も軽くそりゃそうかという感じ．multiset使うのが短くて済むのですが，ポインタ使わずにできないものか(集合の中身の値を見るのにポインタしか手段がないのか？)．Dも考えていたのですが結局ACならず．どうやら行列累乗のテクニックを使うそうです．ちょうど次解こうと思っていたyukicoderの問題が毛色の似た問題だったことを知って後悔しています・・次あたりでその問題レポかD問題復習をしようと思います．

レート変化：1661 -> 1630 (-31)

2問しか解けなければさすがに下がるか．

そういえばCodeforcesのレーティング割り振り大きく変わりましたね．青が1600-1899になり，div1入りがますます遠くなってしまいました・・まあdiv1入って2問解けないような実力のうちはdiv2で得点を安定させるのを目指した方が良さそう．

gist5449bdc4f0263f7c6800