E869120さんの超絶まとめQiitaが話題になっていました。
全三部作で、初級編は茶色、中級編は水色、上級編は黄色になるためのアルゴリズムやデータ構造のリンク、勉強法などがまとめられています。このうち中級編には「分野別 初中級者が解くべき過去問精選 100 問」という節があり、アルゴリズムごとに基本から応用まで良問が揃っています。ありがとうございます。
ということでこいつらをやっつけていきます。都合上、AtCoderとAOJで解答できる問題のみとなります。
前回はこちら。
「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」中級編の100問を解く vol1 ~No.17 - 電波ビーチ
今回は33問目まで。（随時更新予定 ...たぶん）
二分探索
18. ALDS1_4_B - 二分探索
解法はいろいろあるけど今回はちゃんと二分探索で解いてみる。アルゴリズムはググれば無限に出てくるのでそうする。「特定の値が存在する」を判定してもいいし、lower_boundとupper_boundを実装して差を求めてそこから判定してもいい。手癖で後者を選んだ。
提出はこちら。 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4193625#1
19. JOI 2009 本選 2 - ピザ
求めるべきは配達先と一番近い店舗との距離。所与の店舗の座標をソートしてにぶたんしていく。環状になってるのをどうするかだが、直線と考えて先頭=0, 末尾=dとして考える。最後の出力は]と
]で差を取って小さい方を取る。というらしいのをAOJのほうの提出を写経した（は？
:thinking_face:な提出はこちら。 https://atcoder.jp/contests/joi2009ho/submissions/10328677
20. AtCoder Beginner Contest 077 C - Snuke Festival
bの各要素を基準にして、aをlower_bound, cをupper_boundして掛け合わせて足していけばいい問題。ジャンルがにぶたんだとわかっていればすぐ解けるけど初見で非誘導だとあんまり自信がない
提出はこちら。 https://atcoder.jp/contests/abc077/submissions/10258534
21. AtCoder Beginner Contest 023 D - 射撃王
教育的問題らしいがちっとも歯が立たなかった。答えそのものをにぶたんで導出していくタイプの実装。この場合は得られるスコアを決め打ちで探索する。決め打ちした値をどうするか、というところで、「最後に撃ち抜くターゲット」を決めて考えてみたものの、5秒くらいで詰んだ気がしたので答えを見た。
目標スコアをxとすると、 番目の風船は
を満たす
回目までに割られる必要がある。ここで貪欲のこころがはたらく。 早く割られなければならない順にソートし、それが実際にそうなっているかを判定し、結果を以てxを更新していく――というフェーズが浮かばなかった。教育ってむずかしいね
提出はこちら。 https://atcoder.jp/contests/abc023/submissions/10336251
22. B - ムーアの法則
グラフが下に凸になるので三分探索が使える、らしい、のだけど、冷静になって考えないと関数がわからなかった。というか最初は解法分からずググって、初めて三分探索の存在を知ったくらい。
グラフは で、謎の霊感によりこれが直ぐに浮かぶらしい。時分は魂のステージが低いためその域には達していない。ともあれ、Wolfram Alpha先生に聞いたらたしかにそうなっているのでヨシ！
で、三分探索は典型すぎるためか、Atcoderでほかに例題がみつからず、同問題の解説を読んで実装を学習した気になった。具体的にはこちらを参考にした。
未だ得心が行かない提出はこちら。 https://atcoder.jp/contests/arc054/submissions/10338597
23. JOI 2008 本選 5 - ダーツ
ぱっと見「部分和DPだな了解！」という気持ちに走ってしまいそうになるが、得点の重複を許しているところでわけがわからなくなる。使う手法は半分全列挙と二分探索で、合わせて[tex: O(N2*logN)]に落とせる。
問題を簡単にして矢を3本だけとすると、（計算量的に）2本は全探索で、最後の1本はmから「全探索で探した2本によるスコア」を引いた残りスコアを超えない最大値をにぶたんで探して更新していく作業になる。つまり2本までなら全探索可能。そこで、あらかじめ得られるスコアを「1本ではなく、2本投げた場合のすべての組み合わせ」にすると、探すのが楽になる。これが半分全列挙の部分。
.... という解説はググって出てきたこちらを眺めてなるほどとなった。なるほどめちゃくちゃわかりやすい。説明が超上手い
自力では解けなかったものの勉強になったなぁと思った提出はこちら。 https://atcoder.jp/contests/joi2008ho/submissions/10352376
深さ優先探索
24. ALDS_11_B - 深さ優先探索
基本形。適当に再帰する。隣接リストをそのまま使ったがふつうに隣接行列で作り直したほうが楽だろう。雑にやりすぎた
提出はこちら。 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4207041#1
25. AOJ 1160 - 島はいくつある？
DFSで全探索していく。訪問済みのところを重複して訪れないようにすることと、上下斜めへの移動の方法に気をつける。そういえばあんまり斜め移動って聞かない気がする
提出はこちら。 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4207191#1
26. AtCoder Beginner Contest 138 D - Ki
根は1と決められているので、最初にクエリの準備をし、最後に一度だけDFSを走らせて累積和のように更新していく感じ。...というだけでなんだが、しかも過去にちゃんと解いてたはずなんだが、無駄に時間かかったしなんなら最初隣接行列で書いててTLEとREの山を築いてしまった。退化してますね。死がちかいのかな
タナトスを感じる提出はこちら。https://atcoder.jp/contests/abc138/submissions/10354346
27. JOI 2009 予選 4 - 薄氷渡り
後で書く
幅優先探索
28. ALDS_11_C - 幅優先探索
はい（後で書く）
29. AtCoder Beginner Contest 007 C - 幅優先探索
BFSでのこうした探索は 「最初にそのマスにたどりついたときがそのマスにたどりつく最短ステップ」という特徴があるので、ステップ数用のテーブルを更新していく感じで雑にやってもいい。キュー構造も適当。迷路探索の超典型問題
提出はこちら。https://atcoder.jp/contests/abc007/submissions/10357081
30. JOI 2011 予選 5 - チーズ
BFSは最短距離が最短で分かる。S -> 1 -> 2 -> ... -> N-1 -> Nの順にそれぞれの間の最短距離を求めるだけ。典型BFSをN回繰り返す感じ
のため計算量的に間に合わなそうにみえるが、よく読んだら制限時間が10secなのでPython3で雑に実装しても間に合う。
提出はこちら。https://atcoder.jp/contests/joi2011yo/submissions/10367937
31. JOI 2012 予選 5 - イルミネーション
後で書く
32. AOJ 1166 - 迷図と命ず
後で書く
33. AtCoder Beginner Contest 088 D - Grid Repainting
白を黒に変えられる量が多ければスコアが高くなるので、できるだけ白い部分を残してゴールしたほうがいい。すなわち最短経路でゴールするのを目指す。
幅優先は最短経路がわかる、すなわちそのステップ数が分かる。ので、ふつうに幅優先でゴールし、踏まなかった白の数を数える。
提出はこちら。 https://atcoder.jp/contests/abc088/submissions/10367483
二分探索、むずかしいね。。。。
続く
