競技プログラミングの鉄則 演習問題集 の要点や感想をまとめたページです。

偶奇に着目する。

まず、最短経路で左上から右下まで到達できない場合はNo。
つまり、最短経路長の $2(N-1)$ より $K$ が小さい場合は到達不可。

次に、左上から右下まで到達できる場合を考える。
これは、最短経路長が必ず偶数になることから、 $K$ も偶数である必要がある。
余った分の $K$ は、右下のマスをウロウロすることで消費することになるが、
「右下のマスに隣り合うマスに移動→右下のマスに移動」は $K$ を $2$ 消費することになるので、
$K$ は偶数である必要がある。

https://atcoder.jp/contests/tessoku-book/submissions/44452512

操作の前後でON/OFFの豆電球は以下のどちらかに変わる。

• 両方OFF　→　両方ON
• 両方ON　→　両方OFF
• 片方がOFFでもう片方がON　→　ON/OFFの個数に変化なし

よって、 ONの豆電球の個数と $K$ の偶奇が一致していればYes、そうでなければNo。

https://atcoder.jp/contests/tessoku-book/submissions/44453076

共通している箇所をまとめて計算する。

https://atcoder.jp/contests/tessoku-book/submissions/44453272

【★解説AC★】

わからん。
実験で求める系っぽい。
解説を写経した。

https://atcoder.jp/contests/tessoku-book/submissions/44642351

働いた時間として考えられる最大値を各日で全探索。

https://atcoder.jp/contests/tessoku-book/submissions/44456235

「低い草→高い草」に辺を張ってDFSをする。
$O(N^2)$ が通るので、雑に全部の始点を試す。

https://atcoder.jp/contests/tessoku-book/submissions/44458920

区間スケジューリング問題をする。
映画の終了時刻の昇順に並べ替えて、見れる映画を貪欲に選択していくのが最適。

https://atcoder.jp/contests/tessoku-book/submissions/44459092

priority_queueで選択できる仕事の報酬を管理する。
各日を全探索して、選択できる仕事の報酬の最大値の総和を求めていく。

https://atcoder.jp/contests/tessoku-book/submissions/44460125

各長さの棒の個数を数え上げる。
$i$ 番目の長さの棒の個数を $k$ としたとき、_$k$$C$_$3$の総和を求めればよい。

https://atcoder.jp/contests/tessoku-book/submissions/44460206

$A_i$ を $100$ で割ったあまりで考えるとわかりやすい。
$A_i$ の個数を数え上げながら、 $A_i$ とペアになるものを全探索していく。

https://atcoder.jp/contests/tessoku-book/submissions/44460523

$3$ つ連続して青または赤となる箇所が存在すればYes、そうでなければNo。
両端から貪欲に色を塗っていき、最後に $3$ つ色が連続している箇所を塗ればよい。

https://atcoder.jp/contests/tessoku-book/submissions/44460867

逆の操作を考えると楽。
はじめは $x=X, y=Y$ からスタートして、

• $x < y$ なら $y=y-x$
• $y > x$ なら $x=x-y$

を $x,y$ の両方とも $1$ になるまで繰り返していく。
$X,Y$ は互いに素なので最終的には必ず $1$ になる。

https://atcoder.jp/contests/tessoku-book/submissions/44461086

【★解説AC★】

下限値を固定して全探索をする。
これにより生徒同士の体力と気力の比較を行わずに済む。

https://atcoder.jp/contests/tessoku-book/submissions/44461840

【★解説AC★】

表と裏の正負を全探索する。

https://atcoder.jp/contests/tessoku-book/submissions/44464780

蟻本のAntsという問題と同じ。
ぶつかったら方向転換ではなく、すり抜けると問題文を読みかえて問題ない。

https://atcoder.jp/contests/tessoku-book/submissions/44464857

すべての人が全問正解した状態からはじめて、
そこから不正解だった分を引いていくとよい。

https://atcoder.jp/contests/tessoku-book/submissions/44464931

反転しているかどうかをフラグで管理する。

https://atcoder.jp/contests/tessoku-book/submissions/44465083

$i$ 番目の行がどの行に移ったかを配列で管理する。
行を指定するときはその配列を介して行う。

https://atcoder.jp/contests/tessoku-book/submissions/44465258

【★解説AC★】

不変量に着目する。

白を $0$ 、青を $1$ 、赤を $2$ として合計値を計算したとき、
合計値を $3$ で割った余りが変化しないことを利用する。

つまり、合計値を $3$ で割った余りが最後に残るカードの数字に対応する。

https://atcoder.jp/contests/tessoku-book/submissions/44465819

$a,b,c$ の合計値が不変であることを利用する。
つまり、 $a,b,c$ の総和が $0$ であればYes、そうでなければNo。

https://atcoder.jp/contests/tessoku-book/submissions/44465945

モチベがないので飛ばします＞＜

Stackを使う。

https://atcoder.jp/contests/tessoku-book/submissions/44466178

Stackに「 $s[i], i$ 」をpair型で乗せる。
$s[i]$ が一致していたらインデックスを出力して、そうでなければStackに積む。

https://atcoder.jp/contests/tessoku-book/submissions/44466315

Queueを使う。

https://atcoder.jp/contests/tessoku-book/submissions/44471908

もはやQueueを使う必要はなさそうだけどQueueでやる。

https://atcoder.jp/contests/tessoku-book/submissions/44472013

PriorityQueueを使う。

https://atcoder.jp/contests/tessoku-book/submissions/44472143

PriorityQueueを使って実装とのことだけど、既に使って実装してるので割愛。

mapを使う。

https://atcoder.jp/contests/tessoku-book/submissions/44472396

$A_i$ をキーにして、それが何個あるのかをmapでカウントする。
$A_i$ の個数を $C_i$ としたとき、 $C_i(C_i-1)/2$ の総和が答え。

https://atcoder.jp/contests/tessoku-book/submissions/44472459

setを使う。

https://atcoder.jp/contests/tessoku-book/submissions/44472540

$x$ との差の絶対値を計算する値は以下の2つを確認すれば十分。

• setでlower_bound(x)をして得られる値
• そのひとつ前にある値（イテレータがst.begin()でない場合）

https://atcoder.jp/contests/tessoku-book/submissions/44472638

【★解説AC★】

RollingHashのライブラリを作成した。（これがRollingHashかどうかは不明。）

https://atcoder.jp/contests/tessoku-book/submissions/44474172

$S$ と $S$ を逆順にした文字列のハッシュを比較。

https://atcoder.jp/contests/tessoku-book/submissions/44474355

【★解説AC★】

Doublingのライブラリを作成した。

https://atcoder.jp/contests/tessoku-book/submissions/44475024

「 $x$ → $x-$ 各桁の和」という遷移を考える。 あとはダブリングをする。

https://atcoder.jp/contests/tessoku-book/submissions/44475333

セグ木を使う。

https://atcoder.jp/contests/tessoku-book/submissions/44475463

セグ木 + DPをする。
$x[i]-r \le x[j] \le x[i]-l$ に該当する $j$ から $i$ に遷移できる。
そのような $j$ は $x$ を二分探索することで高速に見つけられる。
$[posl, posr]$ から遷移できるとき、その範囲のDP値の最小値が求まればよい。
これはセグ木のRMQを使用すれば高速に求めることができる。

https://atcoder.jp/contests/tessoku-book/submissions/44642781

セグ木を使う。

https://atcoder.jp/contests/tessoku-book/submissions/44476264

転倒数を求める。
ライブラリをぺたり。

https://atcoder.jp/contests/tessoku-book/submissions/44476300

セグ木で二分探索をする。

https://atcoder.jp/contests/tessoku-book/submissions/44476444

隣接リスト表現で頂点と辺を管理する。

https://atcoder.jp/contests/tessoku-book/submissions/44484953

隣接リスト表現で生徒と友好関係を管理する。
各生徒を全探索して、最も友達が多い人を出力する。

https://atcoder.jp/contests/tessoku-book/submissions/44485023

UnionFindで連結かどうかを判定する。

https://atcoder.jp/contests/tessoku-book/submissions/44485063

DFSで頂点 $1$ から頂点 $N$ までの単純パスを探索する。
通ったパスはStackで管理して、頂点 $N$ に到達したらStack内の頂点を逆順に出力する。
1度通った頂点は2回以上通る必要がないので枝刈りする。（これをしないと恐らくTLEになる。）

https://atcoder.jp/contests/tessoku-book/submissions/44485274

コストが1の最短経路問題なのでBFSをする。

https://atcoder.jp/contests/tessoku-book/submissions/44485381

グリッド上のBFS。
4方向に進むための配列 $dy,dx$ を用意するやつ。

https://atcoder.jp/contests/tessoku-book/submissions/44485473

コストが2以上なのでダイクストラ法をする。
枝刈りのcontinueと、PriorityQueueに持たせる2つの値のうち1つ目を距離にする点に注意。

https://atcoder.jp/contests/tessoku-book/submissions/44485658

ダイクストラ法の復元。
ダイクストラ法はDPと同じなので、DP復元の要領で逆から辿っていく。

https://atcoder.jp/contests/tessoku-book/submissions/44485793

トポロジカルソート的な感じ。
$A_i$ の逆順に部下の人数を加算するように更新していくと、
全ての社員の部下の人数が求まる。

https://atcoder.jp/contests/tessoku-book/submissions/44486060

DFSで最も深いところから帰ってきた頂点の深さに値を更新していく。

https://atcoder.jp/contests/tessoku-book/submissions/44544509

UnionFindをする。

https://atcoder.jp/contests/tessoku-book/submissions/44544746

逆から見る。
はじめ、クエリ1で運休になる路線がすべて運休になっていることにする。
そこから逆を辿り、運休していた路線が復活していくとみなせるのでUnionFindで管理できる。

UnionFindは結合は得意だけど、分離は苦手。
UnionFindで逆から見る考察は典型。

https://atcoder.jp/contests/tessoku-book/submissions/44544823

クラスカル法をする。
辺をコストの昇順にソートして、非連結な頂点同士をつなぐ辺のみをつないでいく。
そのときのコストの総和が答え。

プリム法でもよい。

https://atcoder.jp/contests/tessoku-book/submissions/44544872

1つ前の問題で、辺をコストの降順に並べ替えるように変更すると最大全域木になる。

https://atcoder.jp/contests/tessoku-book/submissions/44544908

最大フローをする。

https://atcoder.jp/contests/tessoku-book/submissions/44544988

【★解説AC★】

難しくてあまり理解できていない。
あとでもう一度解き直した方がいい。

解説：https://github.com/E869120/kyopro-tessoku/blob/main/editorial/chap09/chap09.pdf

https://atcoder.jp/contests/tessoku-book/submissions/44546798

【★解説AC★】

2部マッチングは最大フローで解く。

https://atcoder.jp/contests/tessoku-book/submissions/44547305

以下のグラフを作成して最大フローで2部マッチング問題を解く。

• 始点となる頂点 $s$ から社員に流量 $10$ を流す
• 社員から勤務時間（0～23）に流量 $1$ を流す
• 勤務時間から終点となる頂点 $g$ に流量 $M$ を流す

頂点 $s$ から頂点 $g$ の最大フローが $24M$ の場合はYes、そうでなければNo。

パズルみたいで面白い。

https://atcoder.jp/contests/tessoku-book/submissions/44547533

【★解説AC★】

考察の段階で $O(M2^n)$ くらいになりそうだな、から思考を放棄したのがよくなかった。
この考察はあっていて、 $O(2^n)$ の頂点から $O(M)$ 本の辺を張ったグラフ上でBFSをすればよい。

https://atcoder.jp/contests/tessoku-book/submissions/44548321

問題に挑戦するときに少しずつヒントを見つけていくことが大切。

• 特殊ケースを考える
  • $N$ が小さいケース
  • $A=[1,1,1,...,1]$ など
• 問題設定から考える
  • 最短経路 → 幅優先探索やダイクストラ法ではないかと考える
• 制約から考える ※必ずしもこれが当てはまるわけではない点に注意
  • $N \le 20$ ： $O(2^N)$ ビット全探索など
  • $N \le 30$ ： $O(2^{N/2})$ 集合に対する半分全列挙など
  • $N \le 400$ ： $O(N^3)$ for文の全探索・動的計画法・ワーシャルフロイド法など
  • $N \le 10^8$ ： $O(1), O(logN)$ 数学問題・繰り返し二乗法・二分探索など
• 単純な解法から考える
  • 実行時間制限に間に合わなくても、全探索などの「単純な解法」から考えていくことは大切
  • 単純な解法の計算量が $O(N^2)$ だった場合、制約が $N \le 200000$ であれば、少し改良して $O(NlogN)$ の解法に至る場合がある
• 問題設定を変えてみる
  • 「設定を少し簡単にした問題」を考えることで、正解へのヒントが得られる場合がある
  • 「最大何問解けるか？」ではなく「全問解けるか？」を考える
  • 「答えの最大値は何？」ではなく「答えは△△以上か？」を考える
• 分解して考える
  • 二つ以上のものを同時に考えると難しくなることが多い
  • 分解できるものを分解する手法が効果的

$A_i$ を昇順に、 $B_i$ を降順にソートする。
先頭から順に $A_i$ と $B_i$ を選択するのが最適。

https://atcoder.jp/contests/tessoku-book/submissions/44554485

制約に着目する。
$H$ が小さいのでbit全探索ができる。
どの行を黒く塗るかを決めてしまえば、どの列を黒く塗るかは貪欲に決められる。

https://atcoder.jp/contests/tessoku-book/submissions/44555306

基本的にはダイクストラをする。
更新するときの距離が同じとき、木の本数が多い経路を採用すればよい。

https://atcoder.jp/contests/tessoku-book/submissions/44555740

列を入れ替える操作と行を入れ替える操作は独立なので、
それぞれに対して転倒数を求めてその合計を出力すればよい。

転倒数を求めるパートはライブラリをぺたり。

https://atcoder.jp/contests/tessoku-book/submissions/44555918

【★解説AC★】

区間スケジューリングかな？動的計画法かな？と考えていたが、どちらもだった。
締切の早い順に動的計画法する。

解く問題が決まっているのであれば、締切の早い順に解くのが最適。
問題は解く or 解かないの2択があるので、動的計画法を考える。

https://atcoder.jp/contests/tessoku-book/submissions/44556960

LazySegmentTreeで通してごめんなさいになりました。

https://atcoder.jp/contests/tessoku-book/submissions/44557738

解説を読んで、貰うDPだとDP値を累積和で持つことで区間和を高速に計算できるのでなるほどとなった。
配る/貰うDPでうまくいかないときは、もう片方を考えることで見通しがよくなることがありそう。

https://atcoder.jp/contests/tessoku-book/submissions/44558276

答えを決め打ち二分探索。
分割する位置は左から貪欲に決めていく。

https://atcoder.jp/contests/tessoku-book/submissions/44559094