E869120さんの超絶まとめQiitaが話題になっていました。
全三部作で、初級編は茶色、中級編は水色、上級編は黄色になるためのアルゴリズムやデータ構造のリンク、勉強法などがまとめられています。このうち中級編には「分野別 初中級者が解くべき過去問精選 100 問」という節があり、アルゴリズムごとに基本から応用まで良問が揃っています。ありがとうございます。
ということでこいつらをやっつけていきます。都合上、AtCoderとAOJで解答できる問題のみとなります。
続きはこちら。
「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」中級編の100問を解く vol2 No.18~No.33 - 電波ビーチ
今回は17問目まで。（随時更新予定 ...たぶん）
全探索：全列挙
1. ITP1_7_B How many ways?
AOJ。制約が小さい（ ）ので単純に数を3つ選んで判定すればいい。この程度なら枝切りも必要ない
提出はこちら。http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4185648#1
2. AtCoder Beginner Contest 106 B - 105
これも制約が小さいのでなにも考えずに毎回割ってあまりが0になる数（=約数）を数え、それが8ならカウントする。見事に奇数の条件を見逃していて数分無駄にした。
提出はこちら。 https://atcoder.jp/contests/abc106/submissions/10221999
3. AtCoder Beginner Contest 122 B - ATCoder
これ全探索のきもちが芽生えにくい気がする。。。見た瞬間手癖でしゃくとり法で書いてしまった。全探索の場合は、1文字目から2,3, ~ N文字目まで区切っていきながら、区切った文字がすべてACGTで構成されているか判定する。終わったら2文字目から3,4,~N文字目、という二重ループ。
提出はこちら。https://atcoder.jp/contests/abc122/submissions/10222163
4. パ研杯2019 C - カラオケ
にほんごがちょっとむずかしい。外側の二重ループで2曲を選曲し、内側のループでN人ぶんまわして答えを加算し、更新。書けてしまえば単純
提出はこちら。https://atcoder.jp/contests/pakencamp-2019-day3/submissions/10222361
全探索：工夫して通り数を減らす全列挙
5. AtCoder Beginner Contest 095 C - Half and Half
これむずくない？なんで灰パフォなんでしょう。
ABピザを使うかどうかに寄る。制約から、ABピザの上限は となるが、奇数枚は有り得ない。これを念頭においてABピザについて全探索し、Aピザ・Bピザに分解し、足りない分をそれぞれ単体のピザを買い、すべてのピザの合計で掛かった金額を更新していく。
不当なほど時間をかけた提出がこれ
https://atcoder.jp/contests/abc095/submissions/14209791
6. 三井住友信託銀行プログラミングコンテスト2019 - D - Lucky PIN
問題を換言すると、
Sの左から3つ数字を選んで順番に並べた数の種類の総数
となる。えらぶ数は3つなのでせいぜい000~999の1000個。これを全探索すれば制限がゆるくなる。ちなみに過去にこれやって解けてたのに今回やったら長時間解けなかった。。。退化してる。。。
かなしみの提出はこちら https://atcoder.jp/contests/sumitrust2019/submissions/10225992
7. JOI 2007 本選 3 - 最古の遺跡
後で書く
8. Square869120Contest #6 B - AtCoder Markets
愚のパターンを考えると、Aの最小値より小さいところに入口を置き、Bの最大値より大きいところに出口を置くとなる。なんやかんや考えて、A,Bからそれぞれ入り口,出口を選んだらいけるんじゃないのと浮かぶのでそうする。勘。
提出はこちら https://atcoder.jp/contests/s8pc-6/submissions/10227163
9. JOI 2008 予選 4 - 星座探し
後で書く
全探索：ビット全探索
10. ALDS_5_A - 総当たり
「やるか」or「やらないか」の二択を毎回やっていくやつ。還元すれば、いくつ選ぶかとなる。この問題だとビット全探索に向いてないというかわざわざしなくてもいいし、手癖で再帰を使ってしまったんだよ。あらかじめ全パターンを網羅して辞書にでも保存しておけばクエリはで解ける。
そんな提出はこちら http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4187288#1
でもちゃんとbit全探索やらんと練習にならんよね、しかしbit全探索なんてやらんからわからんよね、ということで、ググってパクって書いたのがこちら。bit演算、手になじまない。。。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4188958
11. AtCoder Beginner Contest 128 C - Switches
bit全探索の練習を終えたところでこれ。にほんごがむずかしい。考察を深くすすめるようなフェーズはないものの、問題と入力の構造をしっかり把握しないといけない。
- スイッチの状態をbit全探索して
- 各電球との接続状態をみていく
- 今の電球につながっているスイッチと、現在の（決め打ちしている）スイッチの状態のビットが立っているか確認
- 立っていたらカウント
- 今の電球のカウントを2で割った値が、所与のリスト（
）のものと同じなら通る，ひとつでも違ったら終了
- 無事すべての電球に対して通ったら答えインクリメント
うーん、むずい。。。
悩み抜いた提出はこちら https://atcoder.jp/contests/abc128/submissions/10238030
12. AtCoder Beginner Contest 002 D - 派閥
「だれとだれが仲良しどうしのおともだちグループを作るか」をbit全探索。事前のクエリ（ペア）をテーブルに保存しておき、判定フェーズにおいて全員がちゃんとおともだちであれば答えを更新。一組でも違ってれば駄目。このときの比較する答えは探索に用いたおともだちグループの大きさ
提出はこれ
https://atcoder.jp/contests/abc002/submissions/14216776
13. JOI 2008 予選 5 - おせんべい
後で書く
14. Square869120Contest #4 B - Buildings are Colorful!
より多く選ばなくてもいいので、ぴったり
個どれを選ぶかで全探索。選んだあとの判定フェーズではそれまでの最大値を保存しておき、選んだやつのインデックスでいままでの最大値を下回っていた場合はそれより+1したものまでの差をコストに追加する。
提出はこれ
https://atcoder.jp/contests/s8pc-4/submissions/14215140
全探索：順列全探索
15. AtCoder Beginner Contest 145 C - Average Length
が小さいので、1~Nまでの並び方を数え、それぞれで経路の合計値を計算する。C++なら
next_permutationを適当にやればいい。今回はGoで実装した。ロジックは簡単（というかただのさんすうの全探索）だが順列導出のプログラムが組み込まれてない言語は実装する必要があってだるい。頻出なのでライブラリ化しておきましょう
提出はこちら。 https://atcoder.jp/contests/abc145/submissions/10500314
16. AtCoder Beginner Contest 150 C - Count Order
上記とおなじくnext_permutation的なライブラリをもっておけば一発。こちらのほうが上記とちがってさんすうが発生しないぶん楽かもしれない。Comparableを意識してライブラリ化しててよかったね
提出はこちら。https://atcoder.jp/contests/abc150/submissions/10500488
17. ALDS_13_A - 8 クイーン問題
後で書く
うーん、水色への道は厳しい。。。偉大なる先達たちの登坂ルートはちょっと真似できないので、凡人用のルートを開拓中。
続きはこちら。
「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン」中級編の100問を解く vol2 No.18~No.33 - 電波ビーチ
