この記事はCompetitive Programming Advent Calendar 2015 Day22の記事です． www.adventar.org 始めてから4ヶ月間競技プログラミングを無事に続けられているのですが，自分がどういう思いで競技プログラミングに対して取り組んできたのかを振り返っていこう…

先ほどyukicoderの解いた問題数が100問になりました．通過点記念に記録しておきます．始めてからおおよそ3ヶ月ですね．もう3ヶ月経ってしまったのか・・ 解いた難易度の内訳： 難易度 AC数 ★ 8 ★★ 22 ★★★ 52 ★★★★ 18 ★★★★★ 0 ★★★★★★ 0 始めた頃はDPや全探索…

最小カットを最大フローに言い換えて解くタイプの問題に挑戦してみました．おそらくフローを使った簡単な応用問題だとは思うのですが，初めて触れたので発想が斬新だと感じました．(この記事はフローを学んで2日目の記事です，間違いがあれば遠慮なく指摘し…

強連結成分は定義しか知りませんが，考えればその界隈のアルゴリズムを知らなくても解ける良い問題でした． 問題： http://yukicoder.me/problems/62 解法： あるステージAがクリアできたらステージBのコスト(難易度)が半分になることをA→Bの有向辺で表現し…

問題： abc031.contest.atcoder.jp 本番中なぜか3進数列(ll.64-67)を作るところでずっと詰まっていて実装が終わらなかった．こういうシンプルな全探索が実はbitDPへの登竜門となっているのは面白いと思いました． C++は文字列の取り扱いがやりにくいなあとい…

このレベルの問題を1時間で解くにはまだ修行が足りないと感じました． 解法はDP(Editorialを大分参考にしました)． 要素数の場合のスコアを]とする．求めるべきは]． 下の図のようなシチュエーションである頂点から左A個のヒープと右B個のヒープに分断される…

CODE FESTIVAL 2015 参加レポート

が与えられた点集合に含まれているならばを満たす全てのもその集合に含まれるという条件を読み落とし，問題を難しく解釈し結局時間内に解けなかった．注意力不足を感じた回でした． 解法は貪欲+2分探索．計算量は． Codeforces #331 Div.2 C

数学★4．というよりは実装★3.5くらい・・？の問題． 問題：No.226 0-1パズル - yukicoder 解法：解説ページにもあるように，仮に第1行目が0または1が一回でも連続したら第2行め以降はuniqueに決定する．uniqueに決定しない場合は0101...か1010...と交互に並…

戻すDPというのをyukicoderで知ったので，理解を深めるために類題をやってみました． arc028.contest.atcoder.jp yukicoderの該当問題へのリンク： No.155 生放送とBGM - yukicoder 時系列順だとyukicoderよりもARCが先のようですね． クエリの入力が1000000…

BIT★4．BITを学んだ後に解く問題でBITやるだけ，では物足りない方にはオススメかもしれません． 右向きに場所で泳ぐマスと左向きに場所で泳ぐマスを連結させ長さのBITを用意する．LコマンドやRコマンドに相当する挿入はのときどこにいるかを計算する．Cコマ…

唐突ですが，直前のエントリーで話題にしたCODE FESTIVAL予選B，通過していました．久しぶりにこの種類の嬉しさを噛み締めています．というのも，大学に入ってからは評価というものは公正でないものも多く(これは考え方の問題ですが)，評価の仕方も教官によ…

結果：3完 + 40点． 順位：110位 A通過を除くとどうやらギリギリ80位以内に入っているみたいですが・・結果を待つのみ． code-festival-2015-qualb.contest.atcoder.jp 区間を管理する解法ですが，STL不慣れが原因で時間がかかってしまった．コンテスト中の4…

一度競技プログラミング系のオフラインイベントには行きたいと思っていたので，思ったら即実行という感じでなんだか自分が参加しても大丈夫そうなイベントがあったので参加しました！ atnd.org 若さオーラを感じながら(人通りは少なかったが)久々に駒場に．K…

結果：A,Bの2完．Cは普通の実装がTLEだと思い込み，Dは問題の意味を読み違えていた．非常に悔しい思いをした回でした． レート変動：1630 -> 1619 (-11) Cがかなり注意力の必要な実装だったらしく，かなりの人がsystestで落ちていて奇跡的に青維持という結果…

組み合わせ★3． 問題ページ： No.287 場合の数 - yukicoder 貪欲にaからhまで順番にそれまでの総和としてあり得る数字を作る組み合わせをそれぞれ調べる． のDPで解きました． あまりにもすんなり通ってしまったのでひょっとしたら★2相当かもしれませんね． …

結果：A,Bの2完．C解けるべきでした・・結果的に大きい方から貪欲にとるだけの解法で，実装も軽くそりゃそうかという感じ．multiset使うのが短くて済むのですが，ポインタ使わずにできないものか(集合の中身の値を見るのにポインタしか手段がないのか？)．D…

DP★3．レーベンシュタイン距離の実装問題．スペルチェッカーなどに使うのだそう． 参考： レーベンシュタイン距離 - Wikipedia No.225 文字列変更(medium) - yukicoder 解答：愚直に実装しました．DP用マトリクスを作って順に埋めていく感じがわかりやすくて…

文字列★3．実装力が鍛えられる自分的良問でした．vector<char>なんて配列，使う必要なかったかもしれない． 方針：先頭と末端両方から文字列を比べる．イテレータを両端においてスタートし，同じ文字であればその文字を別の配列(C)に格納．もし同じ文字でなければ</char>…

4回目の参加．直後にSRMがあったのですが．精神的疲弊を予想して参加登録を断念．ブッキングやめてー 今回の結果：A,B,C,Dの4完．どれも特にトリッキーなアルゴリズムを要求する問題ではなかったが，確実に実装する力を試された回でした．Dを時間ギリギリで…

結果：A,B,Cの3完．DはずっとN<100のケースを通す方法もお思いつかず1時間が経過し，直前で答えありきで順繰りにできるか確かめる方法と2分探索を思いつき，悔しい思いをしました・・予選Bは後悔のないようにしたい． 下はACした解答． intにするとオーバー…

今回は初めて★4の問題に挑戦してみました．無論解法を確認しながらですが・・・ ほとんど丸1日かけてACまでこぎつけました．本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが，一回★4がどのくらいの難易度かみてみたかったので．これ…

今回のABCは4完63分．D問題で時間がかかりかつ1WA出したのがもったいない．実装は時間がかかってしまったがyukicoderでこれより難しい問題をやっていたので安心して取り組めました．次回も全問正答，かつランキング1ページ目を目指したい． 昨日は東工大プロ…

今回は初めてyukicoder主催のリアルタイムでコンテストに参加しました． No.281が本当に問題児だった．始めは★2でしたがコンテスト中に難易度が★3に修正． 問題は門松列に似たような条件を満たすように3本並んだ竹を長さdづつ切っていって，条件が満たすよう…

Codeforces 2回目の参加． まず結果 A,Bの2完．1581 -> 1533 (-48) やはりCで間違いの原因がわからずWA*7を出してしまい，終了2分前に考えのミスに気づいてしまったのが響いてしまった・・・ A: 倍々ゲーム(ただし途中で何度でも1を足すことができる)．指定…

幅優先探索★3．かなり時間かかったけれど自力でACまで持っていけてかなり嬉しかった． 考え方：基本的には前いた場所と今の場所をセットで持っておいて，次行ける座標とキューの座標2つが門松列になっていればqueueにpushする．確認が終わったqueueの中身は…

いつも昼頃に起きる自分がSRMのために早起きしました 結果：1097 -> 1078 (-19) 結果は2完．前回より易しいセットなために前回の1完のときより相対的な出来は悪いという結果． Easy: 文字列を入れ替える問題．特に問題なくできましたが時間がかかってしまっ…

ダイクストラ法(?)★3．この手の問題は初めてだったので，解説を少し読んで，priority_queueの仕様を理解してから実装．正味2時間くらいかかったのでは・・ 解説通りスタートからオアシスまで・オアシスからゴールまで・スタートからゴールまでの3ルートに分…

FFT．多項式乗算にフーリエ変換を使うというのは実際問題として出されると思いつかないですね… 情報系学生なのに今までFFTを手打ちしたことがなかった(爆)ので，今回はFFTの実装がメイン．バタフライとかいう仰々しいアルゴリズムの名前が付いていましたけれ…

いろいろ大会があったので書くネタを溜め込んでしまった．．CFとSRM参加しました．SRMはすごい昔に1回参加したことありますが0完だった気がします．CFは初参加． 結果 CF: (1500) -> 1581(青) 2完． SRM: (1000) -> 1097(緑) 1完... ARC: 1完... CF #319 2B …