リンク -> 分野別 初中級者が解くべき過去問精選 100 問
競プロ精選100問を全部解きたいので、このページでタスク管理を行う
途中まで進んだ段階からこの記事を作成しはじめたため、とりあえず途中から開始する。
一通り終わったら、初めの方のものも順次更新したい。
DP (Dynamic Programming: 動的計画法)
区間DP
46 ALDS_10_B – 連鎖行列積
上記のポイントを基準に3重ループを行い、ｄｐを更新する
初見、実装時は3を必要ないと考えてしまっていた。。
47 JOI 2015 本選 2 – ケーキの切り分け 2
30分以上考えたが、実装方針が立たず投了。。
DP=forループという思い込みによって上記が思いつかなかった。
まだ、解説を読んだだけなのだが、実装も結構難しそう。。
48 AOJ 1611 ダルマ落とし
区間DPのかなり典型的な問題だったのだが、慣れてないのもあって全然方針が立たなかった。
DPは本当に色々なパターンがあって難しい。
多少の反復練習が必要そう。。（精選１００問はおそらく範囲が被らないように選択されているので、こういった面ではちょっと使いにくいかも）
苦手分野克服のための問題集などを探して解いたほうが良いか。。
解き直しをすればおそらく良いのだが、難しい問題は方針が立たないことが多いので、多少は答えを見るのは仕方が無い気もする。。
実装も個人的には結構難しかったので、コメントをできるだけ付けた解答のページを作成。（以下リンク）
詳細解説ページ
bitDP
49 DPL_2_A – 巡回セールスマン問題
これも自力では解けなかった。。
dpテーブルの設計が個人的に本当に苦手。
また、dfsを工夫するのが難しすぎる。。少しの応用で解ける問題を解いて経験を積んだほうが良いのだろうか。。
答えをみれば実装が理解できるようになったのは進歩だと思うが、一から実装できる気がしない。。
こちらも実装が難しかったので、コメントをできるだけつけた個別解答ページを作成（以下リンク）
詳細解説ページ
50 Square869120Contest #1 G – Revenge of Traveling Salesman Problem
時間制限の追加はできたのだが、最短経路の保存は思いつかなかった。
最短経路保存の方はメモ化再帰の終了条件が良くないIのか実装しきれていないが、ポイントは上記なので、もう飛ばす。（メモ化再帰のデバッグだるすぎ）
51 JOI 2014 予選 4 – 部活のスケジュール表
シンプルな問題だったので、はじめ方針がうまく建てられなかったが実装していくうちに解くことができた。鍵の受け渡しをどのように考えるかがポイントで、上述のように状態を比較して両方来ている人がいるかどうかで判別し、いる場合のみ値をもらうように更新すれば良い。
こちらもコメントを付けてものを実装したので別記事にまとめた。
52 JOI 2017 予選 4 – ぬいぐるみの整理
１つ目のポイントは制約条件からしてすぐに気づいたのだが、２つ目のポイントは全く思いつかなかった。実装をみてもbit全探索してdpを更新していくことで、順列を調べていくというのを理解するまでにかなり時間がかかった。
これが利用できることを知っていれば方針は立てやすいが、実装は完成してものを修正しながら行わないと厳しそう。。
一応、コメントを大量に追記して自分で解釈しながら写経して、コードを作成したが、うまくコメントできているか自信はない。 -> 個別記事
動的計画法：その他
53 DPL_1_D – 最長増加部分列
ポイントにつきる。
アイデア一発という感じ。これを自力で思いつくのが難しいから有名問題なんだと思う。
個人的には添字をインデックスにしていないせいか、dp tableという感じがしないが、動的に計算を更新していく際のバッファという観点ではバリバリdp table何だと思う。
解説はこちらの記事が具体的でわかりやすかった。
54 AtCoder Beginner Contest 006 D – トランプ挿入ソート
上記53を解いたすぐあとだったこともあったが、最長増加部分列を求めて、元の配列の大きさから引くことでACできてしまった。
55 AtCoder Beginner Contest 134 E – Sequence Decomposing
これも53, 54に続いて取り組んだおかげか、上記のおそらく正攻法の答え方にたどり着くまでが早かった。
添字で少し戸惑ったが、チャレンジ問題とされている割にはそこまで難しくなかった印象。
公式解説と少しはじめの考え方がちがったので、一応個別記事を作成。
このカテゴリの感想
「動的計画法：その他」というカテゴリ名の割には、最長増加部分列とその応用問題たちといった印象だった。
53は解けなかったが、それを理解したことで54、55を自力で解くことができて、カテゴリのまとめとしての理解につながったのはとても良かった。
グラフ
ダイクストラ法
56 GRL_1_A – 単一始点最短経路
完全な典型問題なので、用意してあるダイクストラライブラリで実装。
ダイクストラは慣れてくるとpriority_queueの実装がシンプルで良い。
57 JOI 2008 予選 6 – 船旅
典型のダイクストラを関数化してグラフを都度更新して、都度ダイクストラを実行してもC++なら計算時間は間に合う。56に比べてアルゴリズム的に新しい要素は無いように思う。
58 JOI 2016 予選 5 – ゾンビ島
重みつき作成するために通常のグラフ探索（距離の計算）が必要。 距離の計算結果とゾンビの位置、開始地点、終了地点で重みの場合分けを行う必要がある。（開始、終了時の判定をしないと、間違った結果になるので注意） 幅優先はかなり計算時間については適当だったが、C++なら実行制限が10sとゆるいので間に合う。（私は6180msだった。）
59 JOI 2014 予選 5 – タクシー
初めは重みつき辺を幅優先での距離探索をもとに作成すれば良いかと考えて実装したが、それだと同一の辺ができてしまう。（同一の辺ができると、マイナスの辺ができるのと同じ効果になるため、ダイクストラが使えない）
そこで、ダイクストラ自体の修正が必要と考えて、重み付きグラフでなく、到達可能かどうかを表す行列とコストの２つのバッファを用意して、これを用いて更新を行うことで実装したところ、こんかいも2308msと時間はかかっているが、制限がゆるい(10s)ためAC。
このカテゴリの感想
基本的に典型を修正していく形で実装していけるイメージ。
また、グラフアルゴリズムに関してはあまり計算時間は考慮しなくても、どの典型を用いるかをうまく選択すれば制限時間は通るように思われる。
（まだ、このカテゴリしか演習してないのではっきりとはいえないが。。）
ワーシャル・フロイド法
おそらく知ってないと厳しいアルゴリズムかと思う。この間ABCに類似問題が出題されていたが、知っていたおかげで大分楽ができた。
60 GRL_1_C – 全点対間最短経路
典型問題。これをライブラリとして整備したほうが良さそう。
61 AtCoder Beginner Contest 012 D – バスと避けられない運命
典型問題をひと工夫するだけで解ける。
62 AtCoder Beginner Contest 079 D – Wall
使うアルゴリズムがわかっていると楽。
63 AtCoder Beginner Contest 074 D – Restoring Road Network
これは今までと違ってかなり難しくて、自力で解くことができなかった。
構造の存在判定が特に実装の先が見えなかったので、ワーシャル・フロイドでとりあえず最短路を求めるということもできなかった。
個人的に問題の分割というのが上手くできていない気がするので、意識したい。
このカテゴリの感想
ワーシャル・フロイドを使うということがわかれば、そこからの応用はそこまで難しくなかった印象。
最小全域木
これもクラスカル法を知らないと難しいと思う。
64 GRL_2_A – 最小全域木
基本問題。クラスカル法自体は実装は重くないので、ライブラリとして持っておく必要はないかも？
65 JOI 2010 春合宿 – Finals
最小全域木を求める際に最後のK本を除くことで問題の要求する答えになることに気づければ実装は典型問題を少し改修すれば良い。
名前が紛らわしいが「Finals」という名前の問題。
頂点IDが違うという実装ミスだったので、ほとんどテストケースが通ってしまっていてミスに気づくのに時間がかかった。
66 AOJ 1127 – Building a Space Station
問題文英語だけです。ただ、今は翻訳ツールがあるので、deeplで全文変換したらほとんどの内容は理解できた。
問題自体は入力データをグラフに変換したらクラスカル法をそのまま適用するだけで解ける。
今回も、return文の位置を間違えて大分バグ探しに時間がかかってしまった。。
67 AtCoder Beginner Contest 065 D – Built?
元記事のヒントに従って、制約条件がN<=2*10^5なので、N^2の辺を減らせるように工夫をすれば良い。
今回の問題ではx, yのそれぞれでソートして隣の頂点とのみ辺を結ぶようにすると、2*(N-1)個の辺だけ用意すればよく、それ以外同士の頂点同士の辺は最小全域木には不要な点となるのでこれで十分。
同一間の辺が２つできる可能性があるが、これはクラスカル法が最小のながさの辺から利用していき、それ以降の同じ頂点同士の辺は捨てるというアルゴリズムのため、問題ない。
このカテゴリの感想
ワーシャルフロイド同様アルゴリズムが強力のため、典型に落とし込みやすかった。
知ってるか知ってないかが大きいため、出題頻度は多くないかもしれない。
整数
高速な素数判定法
68 NTL_1_A – 素因数分解
for文を√Nまで行って、中でwhileを呼んで順に追加していけば良い。
素数だった場合に最後に自身を追加する点に注意。
69 AtCoder Beginner Contest 084 D – 2017-like Number
ポイントの通り。
実装方針はあってるはずだが、ACにならなかった。
何かWAになったのだが、よくわからん。テストケースはもっと簡単にDLできるようにしてほしい。
トライアンドエラーが全然できない。
バグ解決面倒なので、近い実装の人のコードをコピペしてAC。
本当、境界値とかでエラーにされるの嫌だがからサンプルケース多くしてほしい。
このカテゴリの感想
実装方針は割と単純だし、検索すれば参考になりそうな実装がたくさんある。
高速なべき乗計算
70 NTL_1_B – べき乗
１つ目のポイントの上限を見極めるのが少し難しいが、それ以外は単純。
（n<=10^9より2^30 = 2^(10+10+10) = 1024*1024*1024 ≒ 1000*1000*1000 = 10^9より30までで良い）
bit全探索などでシフト演算などを知っていると楽に実装できるが、知らないと少し面倒かも。
71 Square869120Contest #1 E – 散歩
atcoderライブラリを使用するとただの累積和の問題。
絶対これで解くべきではないが、解けてしまうものはしょうがない。
このカテゴリの感想
整数系の問題はatcoderライブラリが使用できればかなり楽できるのでは？
フェルマーの小定理など理解できていないので、どこかでまとめて勉強したくはあるのだが。。
逆元を使う問題
72 AtCoder Beginner Contest 034 C – 経路
atcoderライブラリのmodintを使用すれば上記の工夫だけで実装できる。
atcoderライブラリが無くとも自己ライブラリを準備していれば簡単に実装できるのでライブラリは正義。
73 AtCoder Beginner Contest 145 D – Knight
ベクトルの考え方を使うと、組み合わせの計算に帰着できる。
74 AtCoder Beginner Contest 021 D – 多重ループ
これもatcoderライブラリを使ってnCrするだけ。
75 AtCoder Beginner Contest 149 F – Surrounded Nodes
いきなりレベルあがりすぎ。
解説記事みてもわかんなかった。動画があってようやくわかったがまだあやふや。。
これは個人的にはDFSの問題。（このカテゴリの問題がatcoderライブラリのmodintライブラリでほとんど解決されてしまっているというのもあるが。）
DFSとDPは奥が深いと感じる。
簡単な問題をたくさん解いて慣れたい。（毎回新しい問題だと発想力的に厳しいものがある。。）
このカテゴリの感想
おそらくこのカテゴリ自体はatcoderライブラリがあればかなり楽。
ただ、最後のだけ考察が難しい。DFSの問題。
累積和
76 全国統一プログラミング王決定戦本戦 A – Abundant Resources
考察自体はすごい簡単だが、添字が多く丁寧に実装しないとバグる。
for文の境界値とか大嫌いなので緩くしてほしい。。
77 JOI 2010 本選 1 – 旅人
76より素直。バグらせずに実装できた。
78 JOI 2011 本選 1 – 惑星探査
相当、愚直に実装したこともあるが、１００行近くプログラムが必要だった。
累積和のリストは引くことを考えて、N+1のサイズにしたほうが良さそう。（ちょっと添字考えるのが嫌だが。）
79 AtCoder Beginner Contest 106 D – AtCoder Express 2
半分累積和でバッファを持つことで、各クエリー対してO(N)で解答が可能だが、頑張れば各クエリーに対してO(1)で回答することも可能だと思われる。
初見では解けなかったが、理解していれば解くことのできる良い問題だと思う。
80 GigaCode 2019 D – 家の建設
二次元累積和を作成すれば、H*H*W*Wの全探索をしてもH,Wが小さいので計算時間は間に合う。
累積和の作成で境界値付近の値が怪しくバグらせてしまったので、慣れないうちは出力して結果を確認したほうが良いと思われる。
81 AtCoder Beginner Contest 014 C – AtColor
１次元いもす法をそのまま適用する問題。また境界値でバグらせてしまったので気をつける。
82 AOJ 2013 – 大崎
前設定が長い問題。（たぶん最初は読まなくても良い）
実装上は時刻（hh:mm:ss）をどうパースするかで少し悩む。
（今回はsubstrとstoiでパース）
81のちょっとの改良で実装できたので、いもす法は流用しやすいかも。
83 JOI 2015 本選 1 – 鉄道運賃
今回もいもす法だが、足すインデックス、引くインデックスに注意して行う。
累積和はやはり出力しておいたほうが無難。
インデックスが嫌な問題は簡単な例をやってみて上手く行くか試すのが良いかもしれない。
84 JOI 2012 本選 4 – 釘
このカテゴリのボス。圧倒的に難しい。
上記の２ポイント目まではわかったが、更新位置を自力で求めることはできなかった。
また、ななめの累積和のときにうまくインデックスを設定しないとはまることがあるので注意。
（プリントでバッグを３０分くらいやってようやっとインデックスがずれていたことに気づいた。）
このカテゴリの感想
結構応用問題は難しい印象。
問題数が多かったので演習にはなったと思う。
また、累積和を求める際のインデックス処理が厄介なので、累積和は簡単なケースで出力するなどして確認しながら実装したほうが良さそう。
UnionFind
85 DSL_1_A – 互いに素な集合
典型問題。unionFindを使って各クエリを処理するだけ。
86 AtCoder Beginner Contest 075 C – Bridge
制約が緩いので、１つの辺だけを除いたunionFindを作成して、サイズを調べることで連結かどうかがわかる。
これを愚直に実装してもO(M^2)の計算量で実行できる。
87 AtCoder Beginner Contest 120 D – Decayed Bridge
２つ目のポイントが特に重要。
ちょうど、unionFindの関数であるissame, size, uniteを全て使用しており、unionFindの練習にもってこいという感じの問題。
このカテゴリの感想
UnionFindは強力な割には実装も単純で使いやすいので、覚えているだけで大分得するアルゴリズムだと感じた。
有名なアルゴリズムの書籍でも独立した章で紹介されていて、重要視されているのも納得。
その他のテクニック
圧縮
88 JOI 2008 本選 1 – 碁石ならべ
圧縮するというアルゴリズムでは無いと思うが、ランレングス圧縮風にデータを持つことで計算量を減らすことができる。（愚直に実装するとN^2となり10^10オーダーになる）
89 JOI 2013 本選 1 – 電飾
愚直に解こうとするとなかなかポイントに気づきにくい問題。交互列を圧縮すると、一瞬で解答方法がわかる。
このカテゴリの感想
８９のような問題はひらめきのような要素が必要（問題文から推測できるのかもしれないが）なので、似たような問題に対しては色々と圧縮方法を試してみるのが大事だと思った。
初等幾何
90 Square869120Contest #5 B – Emblem
最小の最大化ということで二分探索かと一瞬かと思ったが、実は探索は不要で、一意に求めることができる。
決まってない円同士はちょうど同じ半径にしたときに最小値が最大化し、それで決まっているNの円とぶつからなければそれが答え。ぶつかるなら、ぶつからないようにした値が答えになる。
91 AtCoder Beginner Contest 144 D – Water Bottle
２パターンの体積を三角関数を用いて計算する。
このカテゴリの感想
紙で計算して式を実装するだけなので、かなり楽。
実装も短く書けるのでデバッグもおそらく容易だと思う。
実装問題
92 AOJ 1193 – 連鎖消滅パズル
実装問題とあるとおり、場合分けやインデックス処理などいちいち面倒な問題。
ロジックはシンプルなので、途中状態を適切に確認しながら実装すれば時間があれば解ける。
93 Square869120Contest #3 B – 石落としゲーム
パス。
ほとんど９２と同じだが、最初に１つ選んで消す処理が増えていたり、スコアの計算方法が少し実際のゲームっぽくなっている。
９２のコピペでほとんど解けるのであれば解いても良かったが、上記の１つ選んで消す処理とか面倒そうなので、これはパス。
94 AOJ 1149 – ケーキカット
適切に関数化して見通しを良くして実装するのが重要。
コードは１００行まで行かないで書けたので、９２，９３に比べればちょっと楽。
このカテゴリの感想
適切に関数化するのと、適切なタイミングで状態を確認するのが大事だと感じた。
実装が重い問題は各処理は単純だが直列に並ぶ処理が多いような印象なので、それぞれの処理を確かめるようにしながら実装すればバグりにくいと思う。
数学的な問題
95 AtCoder Beginner Contest 149 B – Greedy Takahashi
貪欲法の基礎の基礎と行った感じ。
96 AtCoder Beginner Contest 139 D – ModSum
最大値を数学的に一意に求めることができるので、それを使うだけ。
めっちゃ短く書ける。
97 AtCoder Beginner Contest 150 D – Semi Common Multiple
最小公倍数で割るという発想にはすぐたどり着いたが、その後丁寧な実装が必要。
割るときに１をたして割ったり、素因数分解した際の２の数が全てのaiで一緒である必要があるなどと細かい部分を注意しながら丁寧に実装する必要がある。
別々に上記のポイントに気づいてたのだが、全体として両方を実装に上手く組み込むことができなかった。
ちょっと難しい。
98 三井住友信託銀行プログラミングコンテスト2019 予選 E – Colorful Hats 2
２時間くらいかかってしまったが、解くことができた。
はじめは夜に解いていたのだが、この手の問題は特に朝のほうが解きやすいと思う。
N<=10^5なので、O(NlogN)のアルゴリズムが必要なのかと思ったが、そうではなかった。
こういう引っ掛けはあるのかもしれないので、Nの大きさでの判断に依存しすぎないほうが良いと思った。
99 DDCC2020 予選 D – Digit Sum Replace
ポイントに気づけば実装はとても簡単。
実装面で言うと、２のポイントの考察に少し時間がかかってしまったが、long longは10^18までは大丈夫。
99問目にふさわしい？
100 Tenka1 Programmer Beginner Contest D – Crossing
方法を思いつくのに１時間、実装に３０分位かかったが初見でACできた。
N=10まで答えがあるか確認することで実装方針が建てられた（N=６の答えを求めるのに大分手間取ったが。。）
公式解説の実装方法（階段状に数を並べる）は少し違ったが、答えは同じだった。
こういう問題は時間をかけて、具体例を求めていくと方針が見つかることが多いというのは大事かもしれない。
このカテゴリの感想
具体例を求めるのは大事。
実装に比べて考察が重いので、考察に時間がかかっても焦らないようにしたい。
コメント