初中級者が解くべき過去問精選 100 問 の要点や感想をまとめたページです。

a,b,cをループで回すとき、a,bだけループを回してcは $O(1)$ で求まるというやつ。
入力が何行与えられるかわからないけど、100行くらいなら全体で $10^6$ くらいに収まる。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8020234#1

約数列挙して解いたけど、2重ループでもOK。

https://atcoder.jp/contests/abc106/submissions/43227954

しゃくとり法で解いたけど、2重ループでもOK。

https://atcoder.jp/contests/abc122/submissions/43228216

どの2曲を歌うかを全探索。

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/43228371

ABピザの枚数を全探索。
いろいろな値で全探索できるか試してみたり、特徴的な値に着目してみたりするのが大事そう。

https://atcoder.jp/contests/abc095/submissions/43228613

3つの値を全探索したいときは真ん中を固定して両端を高速に求められないかを考える。
真ん中の左側に存在する数字と、右側に存在する数字をカウントしておいて、得られる答えを計算していく。
今回は答えの種類が少ないので、setで重複分を消す。

https://atcoder.jp/contests/sumitrust2019/submissions/43228917

正方形の対角線を構成する2頂点を全探索する。
残りの2頂点は正方形の中心を原点に平行移動させて、正方形の頂点の90°回転と-90°回転を計算し、
元の位置に平行移動させてからそのような2頂点が存在するかを判定する。（mapなどで管理）
注意すべきこととしては、中心の座標が分数になったとしても正方形が作れるパターンが存在すること。
全頂点の座標を2倍に拡大し、あとから縮小することで分数が登場しない形にする。

https://atcoder.jp/contests/joi2007ho/submissions/43230219

スタート地点を $s$、ゴール地点を $t$ とする。
まず、 $s \le t$ としたとき、 $s, a, b, t$ の順に回るパターンだけを考えればよい。
なぜなら、 $a < b$ より、 $|s-a|+|a-b|+|b-t|<|s-b|+|b-a|+|a-t|$ だから。

次に、 $s$ の候補は $a_i$ のどれか、 $t$ の候補は $b_i$ のどれかと予想した。
入出力例が推測できそうなケースになっていたので助かったが、推測できない場合は次の解法を選択した方がよさそう。

https://atcoder.jp/contests/s8pc-6/submissions/43251557

解説にもあったものだが、 $|x-a_1|+|x-a_2|+...+|x-a_n|$ が最小となる $x$ は $a_i$ の中央値であるというものを利用する。
求めたいものは、

• $|s-a_1|+|s-a_2|+...+|s-a_n|$
• $|a_1-b_1|+|a_2-b_2|+...+|a_n+b_n|$
• $|b_1-t|+|b_2-t|+...+|b_n-t|$

これら3つの合計値であることから、 $a_i$ と $b_i$ の中央値が求まればよい。

中央値が整数にならないケースが厄介だが、その場合 $n$ は偶数。
中央値の左側にある $a_i,b_i$ の個数と、右側にある $a_i,b_i$ の個数が等しいので、
中央値を切り上げようが切り捨てようが $-0.5$ と $+0.5$ の分は相殺される。
よって、中央値は切り上げ or 切り捨てのどちらかをすればよい。

切り捨てver
https://atcoder.jp/contests/s8pc-6/submissions/43252035

切り上げver
https://atcoder.jp/contests/s8pc-6/submissions/43252393

平行移動する量を全探索する。
探したい星座の星1つに着目して、その星が写真のどの星と対応するかをみればよい。

コードだと $n,m$ が逆になってるけど許して。
https://atcoder.jp/contests/joi2008yo/submissions/43252964

bit全探索するだけ。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8024462#1

どのスイッチがonになっているかを全探索。

https://atcoder.jp/contests/abc128/submissions/43253303

どの議員で派閥を作るかを全探索。

https://atcoder.jp/contests/abc002/submissions/43253521

★解説AC★

どの行をひっくり返すかを全探索。
どの列をひっくり返すかは列ごとに独立に決定していく。
愚直にやろうとすると $O(2^R RC)$ かかってしまうが、
各列の01をビット列で管理すれば $O(2^R C)$ に高速化が可能。

https://atcoder.jp/contests/joi2008yo/submissions/43294069

どの建物が見えるようにするかを全探索。
ある建物よりも左側にある建物の最大の高さを管理しながら金額を計算していく。

https://atcoder.jp/contests/s8pc-4/submissions/43293442

経路を全探索。

https://atcoder.jp/contests/abc145/submissions/43294389

順列を辞書順に全探索して、p,qと一致するのが何番目かを求める。

https://atcoder.jp/contests/abc150/submissions/43409075

条件から各行、各列に1つずつクイーンを配置することになる。
そのため、はじめからクイーンが存在していない行に対してどの列にクイーンを置くかは、
クイーンが存在していない列番号の順列を全探索することで求めることが可能。
あとは実装を頑張る。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8039502#1

sの中にtの要素が存在するか二分探索する。
lower_boundを使用して、

• ポインタがs.end()ではない
• ポインタの値がt[i]である

両方の条件を満たせば答えを+1。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8039518#1

$d_i$ をソートして、 $k_i$ を二分探索。
$d_i$ に番兵として $d$ （1周後の本店の位置）も入れておくと例外処理が少なくなってよき。

https://atcoder.jp/contests/joi2009ho/submissions/43410822

値が3つあるときは真ん中を全探索。
$b_i$ 未満となる $a_i$ の個数と、 $b_i$ より大きい $c_i$ の個数を掛けて、足し合わせていく。

https://atcoder.jp/contests/abc077/submissions/43411225

答えで二分探索。
風船の割る順番を決定するのは難しいが、ペナルティをある値以下に抑えられるかの判定は簡単にできる点に着目する。

https://atcoder.jp/contests/abc023/submissions/43413687

$f(x)=x+P/2^{x/1.5}$ の極小値を三分探索。

https://atcoder.jp/contests/arc054/submissions/43414204

もしくは、 $f(x)$ を微分して、正負が入れ替わる $x$ （つまり極値）を判定してもよい。

https://atcoder.jp/contests/arc054/submissions/43414454

ダーツを2本投げたときに得られる得点を全列挙する。
その得点2つを足し合わせた値の最大値を、条件を満たすように二分探索で求める。（半分全列挙的な感じ）

https://atcoder.jp/contests/joi2008ho/submissions/43414716

行きがけと帰りがけの番号をDFSで求める。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8040799#1

DFSをして連結成分をカウントする。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8040860#1

木上で累積和をする。

https://atcoder.jp/contests/abc138/submissions/43438631

DFSで経路を全探索。

https://atcoder.jp/contests/joi2009yo/submissions/43438805

BFSするだけ。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8041006#1

BFSするだけ。

https://atcoder.jp/contests/abc007/submissions/43440044

スタート地点には0番目のチーズ工場があるとして、
i番目のチーズ工場からi+1番目のチーズ工場への最短経路を求めるBFSをi=0,1,...,N-1で行う。

https://atcoder.jp/contests/joi2011yo/submissions/43451694

包除原理っぽい考え方でやる。
①建物の内外問わず、壁面の長さをすべて求める。
②建物の内部にある建物ではないマスの内外問わず、壁面の長さをすべて求める。
（範囲外のマスに隣接していないマスが建物の内部のマス。）
「① - ②」で答えが求まる。
実装は気合で頑張る。

DFSで解きました。
https://atcoder.jp/contests/joi2012yo/submissions/43453473

縦横方向に移動可能かの判定を頑張る。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8043026#1

「白マスの個数」から「最短経路長」を引けば答えになる。
（最短経路で使用しなかったマスを黒く塗りつぶすのが最適。）

https://atcoder.jp/contests/abc088/submissions/43455095

漸化式をもとにフィボナッチ数列の配列を作成。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8043083#1

ナップサックDPをする。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8043107#1

複数の品物が選べるようにi->iに遷移させる。
in-place化するとちょっとだけ簡潔になる。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8043168#1

最小値を求めるのでDP配列をINFで初期化する。
同じ種類のコインを2枚以上使用してもよいので、in-place化してちょっと楽をしている。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8043165#1

「dp[i][j]:=文字列xからi文字目まで、文字列yからj文字目まで使用したときの最長共通部分列」とする。

$x_i = y_j$ なら、 $dp_{i,j}=max(dp_{i-1,j-1}+1, dp_{i-1,j}, dp_{i,j-1})$ 。
そうでないなら、 $dp_{i,j}=max(dp_{i-1,j}, dp_{i,j-1})$ 。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8043217#1

先頭の数字に+/-を振り分けたとしても+しか採用されないから大丈夫だと思っていたら、
0の場合は-も採用されるので組み合わせの数が1増えてしまう。（とんでもない罠）
i=0の場合をDP配列の初期値に持たせることでACできる。

https://atcoder.jp/contests/joi2011yo/submissions/43458622

「dp[i][j][k]:=i日目に食べたパスタがj、i-1日目に食べたパスタがkのときの組み合わせの数」とする。
最初に2日分をまとめて初期化しておくと楽。

https://atcoder.jp/contests/joi2012yo/submissions/43461690

「dp[i][j]:=i日目に服jを来たときの組み合わせの数」とする。
最初に2日分をまとめて初期化しておくと楽。

https://atcoder.jp/contests/joi2013yo/submissions/43462800

「dp[i][j]:=i日目までに都市jに着いたときの疲労度の合計の最小値」とする。

https://atcoder.jp/contests/joi2015yo/submissions/43463374

「dp[i][j]:=i列目を色j(R=0,B=1,W=2とする)で塗ったときの、塗り替える必要のあるマスの個数の最小値」とする。

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/43486769

正四面体数で個数制限無し部分和DPをする。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8046960#1

「dp[i][j]:=i個目の入力信号までで、 $y_i=j$ のときの圧縮後の二乗和の最小値とする。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8052443#1

区間を状態に持ちたいので区間DPをする。

区間DPは以下のどちらかの遷移式になることが多い。

• 区間 $[l, r)$ を更新する際に、 $[l+1, r)$ と $[l, r-1)$ などの左右から1つ増減させたものを確認する
• 区間 $[l, r)$ を更新する際に、 $[l, i)$ と $[i, r)$ をすべての $i$ について確認する

今回は後者のタイプ。

「dp[l][r]:=区間 $[l, r]$ の計算に必要なスカラー乗算の最小回数」とする。

更新時は $[l,i]$ と $[i+1, r]$ を1つの行列をみなし、
2つの行列のスカラー乗算回数を計算し、
その最小値でdp[l][r]を更新することで遷移式が立てられる。

実装ではなんとなくわかりやすいかなと思い閉区間を採用し、
メモ化再帰で実装している。（区間DPはメモ化再帰が実装しやすいみたい。）

参考：https://algo-logic.info/range-dp/

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8067897#1

★解説AC★

まず、円環の問題は配列の長さを2倍に複製すると扱いやすくなることがある。

「dp[l][r]:=ピースlからrまでが残っているときのJOIくんの取り分の最大値」とすると、
max(dp[0][n], dp[1][n+1], ..., dp[n-1][2*n-1]) が答えになる。

遷移式は、

• JOIくんが取るとき、
  • dp[l][r]=max(dp[l+1][r]+a[l], dp[l][r-1]+a[r])
• IOIちゃんが取るとき、
  • a[l]<a[r]なら、dp[l][r]=dp[l][r-1]
  • a[l]>a[r]なら、dp[l][r]=dp[l+1][r]

https://atcoder.jp/contests/joi2015ho/submissions/43952355

参考：https://scrapbox.io/magurosdiary/joi2015ho_B_-_%E3%82%B1%E3%83%BC%E3%82%AD%E3%81%AE%E5%88%87%E3%82%8A%E5%88%86%E3%81%912(Cake_2)%EF%BC%88%E9%9B%A3%E6%98%93%E5%BA%A66%EF%BC%89

★解説AC★

「列の中の隣接する 2 項について処理を順次行う」というタイプの問題には以下の手法が有効。

• スタックを用いたシミュレーション
• 区間DP

テストケースを実行していて両端がうまく消せないなと思っていた。
なら、両端が消せるパターンとそうでないパターンをそれぞれ試せばよいだけだった。

「dp[l][r]:=w[l]からw[r]までのダルマから取り除けるブロックの個数の最大」とする。

遷移式は、

• |w[r]-w[l]| <= 1 かつ w[l+1]からw[r-1]をすべて取り除けるなら
  • dp[l][r]=r-l+1
• そうでないなら任意の区間で分割した問題として考える
  • dp[l][r]=dp[l][i]+dp[i+1][r] (l <= i <= r)

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8127845#2

実装の参考：https://algo-logic.info/range-dp/
解説の参考：https://drken1215.hatenablog.com/entry/2020/03/10/160500

集合を状態として管理したいのでbitDPを考える。

まず、始点はなんでもよいので0スタートとする。
1周するのでどこからスタートしたとしても同じ。

「dp[bit][i]:=これまでに通過した頂点の集合がbitで、最後に訪れた頂点がjのときの最短距離」とする。
初期化はdp[0][0]=0とし、bit=0のときだけは訪れた頂点がなくてもif文で弾かないことにすると実装が楽になる。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8068269#1

最短経路長と最短経路数を管理する配列の両方をDPで更新していく。

「dist[bit][i]:=これまでに通過した頂点の集合がbitで、最後に訪れた頂点がjのときの最短経路長」とし、
「dp[bit][i]:=これまでに通過した頂点の集合がbitで、最後に訪れた頂点がjのときの最短経路数」とする。

i->jに移動したときに、次のようにそれぞれの配列を更新する。

• すでに計算した最短経路長と等しければ、
  • 最短経路数を加算する。
• すでに計算した最短経路長より小さければ、
  • 最短経路数を上書きする。

$d_i$ , $time_i$ の最大が $10^{12}$ で64bit整数を使わないとREになる。
問題文中では1,000,000,000,000と書いてあって桁数を見間違えた。

https://atcoder.jp/contests/s8pc-1/submissions/43667926

「dp[i][bit]:=i日目に集合bitに対応する人が活動したときのスケジュール表の組み合わせの数」とする。
最初、鍵はJ君が持っていることに注意する。

https://atcoder.jp/contests/joi2014yo/submissions/43668683

★解説AC★

まず、ある順番にぬいぐるみを整理するとき、ぬいぐるみを取り出す回数を高速に求めたい。
これは累積和を求めておくことで $O(1)$ で計算が可能。

次にやることは部分問題への分割。
この問題はDPである可能性が高いことが問題文や制約から判断できるので、
DPを使える形にするためにはどうしたらよいかを考えることが大事そう。

今回は既に並べ替えを行ったぬいぐるみの順番は答えに影響しないことがわかるため、bitDPが行える。

https://atcoder.jp/contests/joi2017yo/submissions/43992858

参考：https://starpentagon.net/analytics/plushtoys/

LISのライブラリを作った。
in-place化と二分探索を駆使する。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8133061#1

★解説AC★

LISをやる。
最小増加部分列になっている箇所は入れ替える必要がないから、
それ以外の部分だけを入れ替えればよい。

https://atcoder.jp/contests/abc006/submissions/44011594

multisetでゴリゴリやったら通った。

https://atcoder.jp/contests/abc134/submissions/44010898

調べてみたところ、これはLISの双対問題らしい。
つまり、LISと同じようにして解くことができる。
（双対問題については気が向いたときに調べるとする……。）

https://atcoder.jp/contests/abc134/submissions/44011055

参考：https://drken1215.hatenablog.com/entry/2020/12/25/184700

ダイクストラするだけ。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8068419#1

客から注文票が送られてくるたびにダイクストラをする。

https://atcoder.jp/contests/joi2008yo/submissions/43669413

危険な町を判定するために、前処理で多始点ダイクストラをしておく。
そのあと、町1から町Nまでの最小コストを求めるためのダイクストラをする。

2回のダイクストラで同じ名前の変数が登場するので、前処理の方を関数化している。
https://atcoder.jp/contests/joi2016yo/submissions/43670019

町iから町jまでタクシー1本で行けるところに道路を新しく追加する。
雑に実装するとMLEになるので注意。

https://atcoder.jp/contests/joi2014yo/submissions/43671205

ワーシャルフロイドをするだけだが少し手間取った。

• 負の重みがあるときは、更新時にINF64の値は使用しないようにif文で弾かないとINFの判定がうまくいかなくなる。
• 負閉路の検出はdp[i][i]が負かどうかで判定可能。
• 各行の末尾に半角スペースが入っているとPresentation Errorになるので注意。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8068659#1

ワーシャルフロイドをして、頂点iから各頂点の最短距離の最大値を求める。
その値が最小になるような頂点に引っ越せばよい。

https://atcoder.jp/contests/abc012/submissions/43673615

数字iから数字jに書き換えるときの魔力の総和の最小値をワーシャルフロイドで求める。

https://atcoder.jp/contests/abc079/submissions/43673777

表Aをワーシャルフロイドして、元の表Aと一致すればそのような道路の構造が存在する。

頂点iと頂点jを結ぶ辺を削除できるかを考える。
i->jとi->k->jの最短経路長が一致するkが存在すれば、i->jの辺を削除できる。
（i->k->jの経路を使用してもi->jの最短経路長が変わらないので。）

https://atcoder.jp/contests/abc074/submissions/43674292

最小全域木を求めるアルゴリズムとして次の2つが有名。

• クラスカル法：非連結な頂点同士を結ぶ辺を重さが小さい順に選んでいく。（連結判定はUnionFindを使用。）
• プリム法：頂点を1つ選ぶ。その頂点から各頂点への最短距離となるような辺を選んでいく。（ダイクストラ法っぽいことをする。）

クラスカル法
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8068988#1

プリム法
https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8069092#1

まず、k=1の場合は最小全域木を作り、各辺のコストを求めればよいことがすぐにわかる。
kが2以上の場合は最小全域木の森を作ればよい。

つまり、最小全域木を構成する辺のコストを求めて、
「最小全域木の辺の本数-k+1」本の辺をコストが小さいものから順に使えばよい。

https://atcoder.jp/contests/joisc2010/submissions/43686167

各セルの距離を計算して、行き来可能ではないセル同士を結ぶ辺のコストを計算する。
コストの昇順に辺を並べ替えて、辺で結ばれるセル同士が非連結なら辺を追加していく。
あとは、追加した辺のコストの合計を求めればよい。

cout << fixed << setprecision(3);を記述すると、小数点以下第3位までを0埋めで出力してくれる。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8070260#1

xでソートしたものと、yでソートしたものを用意する。
それぞれ隣り合うものだけを辺でつなぐようにする。
辺の個数が $O(N)$ になるので間に合う。

https://atcoder.jp/contests/abc065/submissions/43686933

素因数分解するだけ。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8070325#1

事前に素数列挙しておいて、素数判定を高速に行えるようにする。
$1 ～ 10^5$ が2017に似た数かを判定しておいて、
$1 ～ r$ までの2017に似た数の個数を累積和で求めておく。
あとは各クエリに対して「 $1 ～ r$ までの2017に似た数の個数」-「 $1 ～ l-1$ までの2017に似た数の個数」を計算すればよい。

https://atcoder.jp/contests/abc084/submissions/43687231

繰り返し二乗法で計算する。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8070465#1

歩いた距離の累積和を計算しておいて、区間和の計算を高速化する。

https://atcoder.jp/contests/s8pc-1/submissions/43688508

nCrを求めるだけ。

https://atcoder.jp/contests/abc034/submissions/43688655

★解説AC★

連立方程式を解くことでどの方向に何回動かせばよいかが求められる。
詰まった箇所は、動かす回数をそれぞれa,bとしたとき、a<0またはb<0となるケースを見落としていた。
処理の中で引き算をしているときは、結果が負になるケースが存在しないかをよく確認すること。

https://atcoder.jp/contests/abc145/submissions/43689341

重複組み合わせ _$n$ $H_k=_{n+k-1}C_k$ を使う。

https://atcoder.jp/contests/abc021/submissions/43689633

★解説AC★

全方位木DPで通したけどもう少し楽な方法がありそう。
それはまた後日……。

ちなみに全方位木DPのライブラリを作った。

https://atcoder.jp/contests/abc149/submissions/44015094

参考：https://algo-logic.info/tree-dp/
参考：https://rustforbeginners.hatenablog.com/entry/abc149_f

累積和のライブラリを作った。

https://atcoder.jp/contests/nikkei2019-final/submissions/43690279

現在いる宿場町を変数で管理し、移動距離は累積和で高速に求める。

https://atcoder.jp/contests/joi2010ho/submissions/43727641

二次元累積和のライブラリを作った。

https://atcoder.jp/contests/joi2011ho/submissions/43815839

二次元累積和をする。
$p \le i &lt; n$ と $0 \le j &lt; q$ の範囲を累積和で求めるとよい。

https://atcoder.jp/contests/abc106/submissions/43816118

長方形を全探索する。
左上の座標 $(si,sj)$ と、右下の座標 $(gi,gj)$ を全探索すればよい。
4重ループが $10^8$ になって間に合わないと思い、gjは二分探索で求めるようにした。

3重ループ+二分探索の実装
https://atcoder.jp/contests/gigacode-2019/submissions/43896129

解説によると4重ループは $10^7$ なので十分間に合うとのこと。
たしかに、 $si \le gi$ かつ $sj \le gj$ で定数倍1/4がつくので間に合う。

4重ループの実装
https://atcoder.jp/contests/gigacode-2019/submissions/43896253

いもす法のライブラリを作った。

https://atcoder.jp/contests/abc014/submissions/43903305

時分秒を秒だけに変換していもす法。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8115311#1

各鉄道を何回使用したかをいもす法で求めておくと、
ICカードを購入したらよいかの判断が容易にできる。

https://atcoder.jp/contests/joi2015ho/submissions/43904148

★解説AC★

三角形のいもす法。
以下の累積和を計算することでうまくいく。

• 左から右
• 右上から左下
• 左上から右下

このような累積和を思いつくコツとしては（参考記事を見ていて思ったこととしては）、
累積和を取った後の状態を先に考えて、そこから累積和を取る前の状態を逆算していくと思いつくことができそう。

https://atcoder.jp/contests/joi2012ho/submissions/44100861

参考：https://imoz.jp/algorithms/imos_method.html

UnionFindするだけ。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8115409#1

使わない辺をすべて試して、グラフ全体が非連結になるものの個数を数え上げる。
UnionFindは基本的に辺の削除はできないので、逐一グラフを再構築している。

https://atcoder.jp/contests/abc075/submissions/43904313

UnionFind+辺の削除は、処理を逆から行うとうまくいくことが多い。
はじめは全ての橋が崩落していて、M,M-1,M-2,...,1の順に橋が追加されていくと考えればよい。
はじめの不便さはn(n-1)/2で、a[i]とb[i]が連結でないとき、
a[i]とb[i]の連結成分内の要素数の組み合わせ分だけ不便さがマイナスされていく。

https://atcoder.jp/contests/abc120/submissions/43904477

ランレングス圧縮して、隣り合う同じ色の碁石を一括で管理して高速化する。
パターンがいろいろあってややこしいが頑張る。

https://atcoder.jp/contests/joi2008ho/submissions/43908059

交互列を長さの配列として管理する。
連続する3つの要素の和の最大値が答え。

https://atcoder.jp/contests/joi2013ho/submissions/43908360

最小値の最大化なので二分探索を考える。
二分探索をして半径の最大値が求まったあと、
既に半径が決まっている円の方が小さい半径があれば、
その値に更新する処理が必要な点に注意。

https://atcoder.jp/contests/s8pc-5/submissions/43908753

傾き方が2種類あるので場合分けする。

• x >= a * a * b：水面が水筒の側面にある場合
• x < a * a * b：水面が水筒の底面にある場合

https://atcoder.jp/contests/abc144/submissions/43909564

気合で実装する。（どこも修正することなく一発目の実装で通ったの嬉しい。）

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8118756#1

連鎖消滅パズルのコードを使いまわす。
最初に1つ消すマスを全部試す。
その兼ね合いで、マスを落下させる処理 → マスを消す処理の順に行っている。

https://atcoder.jp/contests/s8pc-3/submissions/43919836

[切られた順番、面積、縦幅、横幅]となるような配列を作成しながらカットを進め、
都度ソートをすることで識別番号を更新していく。（配列のインデックスが識別番号と対応。）

sはピースを1周以上することもあるので、事前に2(x+y)で割っておく必要がある。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=8118995#1

計算するだけ。

• 高橋君のクッキーの枚数：max(a-k,0)
• 青木君のクッキーの枚数：max(b-(k-(a-{高橋君のクッキーの枚数})), 0)

https://atcoder.jp/contests/abc149/submissions/43924104

$P_i = i+1$ が最適。
つまり、1+2+...+N-1を計算すればよい。

https://atcoder.jp/contests/abc139/submissions/43924209

★解説AC★

まず、与えられた式を変形しておくと楽になる。

$X = a_k (p + 0.5)$
$X = 2b_k (p + 0.5)$ $(a_k = 2b_k$ とおく $)$
$X = b_k (2p + 1)$

$X$ は $b_k$ $(1 \le k \le N)$ の倍数であるため、
$X$ の候補は各 $b_k$ の最小公倍数の倍数であることがわかる。

あとは、 $M$ を各 $b_k$ の最小公倍数で割った値を、小数点切り上げで $2$ で割った値が答えとなる。

ここで自分の勘違いポイントとして、
$X / b_k$ が奇数にならないといけないが、
その判定を「すべての $b_k$ の偶奇が一致するか？」で行ってしまったこと。

これには反例があって、それは $4,8$ の場合。
それぞれ $2$ で割ると $2,4$ となり、偶奇は一致するが、
最小公倍数 $4$ を割った値の偶奇はそれぞれ $2,1$ となり、偶奇が一致しない。

よって、正しい判定方法は「最小公倍数を $b_k$ で割った値が奇数になっていること」だった。

この確認をAtCoder Testcaseで行ったが、
コンテスト本番ならnaiveとsolveの比較を行うのがよいと思う。（ARCなどでよくやる。）

https://atcoder.jp/contests/abc150/submissions/44102516

★解説AC★

前から色を決定していく。

各色の決め方は $0～3$ 通りなので、
$a_i$ のときに $0～3$ のどれに該当するかを判定する配列を管理すればよい。

https://atcoder.jp/contests/sumitrust2019/submissions/44105369

★解説AC★

ラウンドを開催することは $N$ に対して以下のどちらかの操作をすることに対応する。

• $N$ の桁数を $1$ 減らす
• $N$ の各桁の和を $9$ 減らす

桁数の減少は「 $N$ の桁数 $- 1$ 」回行われ、
各桁の和の減少は「 $N$ の各桁の和 $/ 9$ （小数点以下切り捨て）」回行われる。

よって、それらの合計が答えとなる。

https://atcoder.jp/contests/ddcc2020-qual/submissions/44105965

★解説AC★

部分集合を頂点、部分集合で使用している数字を辺とするグラフを考える。
すると、条件に該当するのは完全グラフであることがわかる。

よって、辺数と $N$ が等しい完全グラフのみYes、それ以外はNo。

https://atcoder.jp/contests/tenka1-2018-beginner/submissions/44106957