この記事は解説 Advent Calendar 17日目の記事です。 問題概要 G - Mancala 一列に並んだ個のマスがある。各マスには個の石を置くことができる。ここで次の操作を何回か行う。 操作：ちょうど個の石が置いてある番目のマスどれかを選び、番目の石を個に、以…
問題 ddcc2017-final.contest.atcoder.jp 解法 コンテスト中の自分の思考を再現してみたので、無駄な(最終的な解法を導くのに有効でない)考察も含まれている可能性がある。考察の正当性の証明はここでは省略する。 問題文には1つの辺の長さのみ変更できると…
問題 agc012.contest.atcoder.jp 概要 aaはaを2回、bubobuboはbuboを2回繰り返している。このように長さ1以上の文字列を2回繰り返しているものは良い文字列と定義する。入力 が与えられるので、良い文字列である部分列の個数がである長さ200以下の文字列の1…
初めてyukicoder contestのwriterをやりました。100人ほど参加してくださって、いろいろwriterとして得られるものがあったので書き残しておきます。解説はそれぞれの問題の解説タブに書いてあるので、ここでは解説や提出コードは書きません。 コンテストのリ…
概ね解説と方法は同じですが、自分の方法は少しアプローチが違うので書くことにしました。 問題 agc003.contest.atcoder.jp 概要 正の整数列があたえられる。この中から出来る限り多くの整数を選んで、どの2つの要素の積も立方数にならないようにしたい。最…
kenkooooさん,roitiさん、わいんさんとICFPCにチーム"COBOL Lovers"で参加していました。 全員非学生なので金曜は問題を読む日にして、土日に集まって問題を解いていました。会場を提供してくださったkenkooooさん及び同居人の方に感謝します。 問題概要 ICF…
kenkooooさん、roitiさんとチームshinsotsuで参加。会場を提供してくださったroitiさんに感謝いたします。 結果：CとEを担当して総合15位。Eはroitiさんの考えた解法を自分が実装した形になり、チーム戦っぽいことができてよかったです。幾何は基本的なライ…
★4昇格．Union-find，木DP，DFSなど色々な要素が入っている問題でためになるのだけれど，実装がかなり難関．個人的には今までyukicoderの問題の中で最凶クラスの実装難の問題でした． 方針：輪の包含関係を根付き木で表現する．Union-findなどで各輪の強さを…
DP★3．3ヶ月位前にも一度挑戦していて，その時は自分の方針のアラが探せず出来ずじまいだったが，今回は一発でACできた． 方針：を満たす最長の上昇部分列の長さを今選んでいる要素のindex，直前に選んだ要素のindexの情報を持った上で求める．下はのときの…
本番はSCCに固執しすぎて実装が間に合わず．その後冷静に考えたらもっと単純な方法があった． 解法 まず気づきそうなこと：実線は辺，点線はそうでないとする．次のようなグラフの場合，bは一意に決定する． そこで点線を辺とする(完全グラフから与えられる…
この記事は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を時間ギリギリで…
