趣味かどうかというと微妙なんですが、最近頑張ってる競技プログラミングです。

AtCoderをメインに活動していて、後で自分で引っ張ってくる用に記録を始めました。
カテゴリと簡単な解き方を書いているので、性質上、多少のネタバレはご容赦ください。

どうでもいいんですが、mathjax で tex の数式を埋め込んだらかっこよくてはまってます。。。

基本問題

ソートなど、各種STL使い方の基本問題。
ABC 128 B - Guidebook A スコアの高い順(降順)、文字列の辞書順にソートする。
 pair にするとスコアは昇順、文字列辞書順になってしまうので、operator を定義してやる。
スコアに -1 を掛けてやってもできるけれど、仕事でやったら殺されそうな実装。 youtube の解説ではtupleを使ってましたね。

貪欲法

比較的直観的ですね。priority_queue は、使うのを思いつくかどうか。
ABC 137 D - Summer Vacation B 費用が払われるまでにタイムラグがある日雇いバイトで最大の賃金を得る。
 直観通りに貪欲法。
あとは priority_queue に食わせるデータをどう作るか。

全探索

実装力を問う問題。入門編といった雰囲気です。
ABC 128 C - Switches B N個の電球とM個のスイッチがあり、条件を満たすと電球が光る。光る電球の個数の最大値を求める。
 スイッチの状態をひたすら全探索。
ABC 129 D - Lamp B X軸、Y軸に光が伸びるランプが照らす領域の最大値を求める。
 障害物をリストにするところまで頑張って、ランプの位置は全探索。
また、障害物をリストにしなくても、障害物からの距離をセルに対して数えるともっと綺麗に解ける。
ABC 128 E - Roadwork D 時間、場所により工事中の道をどこまで進めるか。
 「イベントソート」という想定解法だが、要するにひたすら地道に実装…。

BFS

主に最短経路問題。
ABC 007 C - 幅優先探索 A 迷路の最短経路問題。丁寧なガイダンス付き。
ただのBFSなので地道に実装する。こういうのを久しぶりに見ると安心する…
ABC 088 D - Grid Repainting B ゴールにたどり着ける条件を維持して、迷路を塗りつぶせるセル数の最大値を求める。
問題文の理解が大変だがただの最短経路問題に落ちる。あとは頑張って実装。
ABC 132 E - Hopscotch Addict D 有向グラフ上を1回で3マス進む。ゴールにたどり着く最短の手数を求める。
0マス目・1マス目・2マス目と状態を持ち、幅優先探索で最小距離を求める。 グラフを3枚持ってるのと同じ。
最初、3マス先にある頂点に全部グラフを張ろうとしたらO(N^2) となりTLEしまくりだった… これを本番で時間内に考えつける日は来るのだろうか…。

DP

ABC129C - Typical Stairs A

たまに床が抜けているN段の階段の登り方を求める。

1次元DP。基本はフィボナッチ数列なのだけれど、遷移条件に例外が混ざっている。

ABC021 D - 多重ループ B

\(1 \leqq a_1 \leqq a_2 \leqq ... \leqq a_n\) なる組み合わせの数を求める。

DPでちまちま求めることもできる。
が、実は重複組み合わせそのもの。これが重複組み合わせに見えるかどうかが勝負。

ABC110 D - Factorization B

\(a_1 \times a_2\ \times ... \times a_n = M\) となる組み合わせの数を求める。

素因数分解して分割数。
分割数は、\(_{n+m-1}C_{m-1}\) でも、
DP(\(dp[i+1][j] = dp[i][j] + dp[i+1][j-1]\))でも求めることができる。 両方試したら今回の条件だとDPのほうが10倍くらい速かった。

ABC054 D - Mixing Experiment B

N種類の薬品を混ぜて、比率を A:B にする。

2次元ナップサック問題。最初、平方分割かと思って時間かかりました。

ABC129 E - Sum Equals Xor C

A + B = A xor B となる A, B の組み合わせを求める。

桁DP。

第4回 ドワンゴからの挑戦状 予選 C - Kill/Death D

分割数の変形版。

n個の複数郡の分割数を求めるのだが、配るDPでロジックは統一して解ける。

ABC015 D - 高橋くんの苦悩 B

画面に貼り付けるスクリーンショットの価値を最大化する。

ナップサック問題。

ABC006 D - トランプ挿入ソート B

トランプから1枚を動かしてソートをするときの処理回数。

実はLISを求めればよい。気づくほうが難しいが、気づけば簡単系。

diverta 2019 Programming Contest D - Squirrel Merchant C

リスの高橋君がドングリ交換所で金銀銅とドングリを交換してドングリを増やす。

間の交換所で一度全部ドングリにしてしまえばよいという発想の転換がポイント。 DPは基本的なナップザック問題なのだが、ナップサック問題のi番目の商品がドングリになってるので、 一目ではわからないと思う。(解説見てからも理解するまでに時間かかった…)

ベルマンフォード法(BellmanFord)

負のコストを含むグラフの最短路。
ABC 137 E - Coins Respawn C 経路上でコインを得ることができるが、移動ごとにペナルティがあるゲームの最大得点を求める。
ベルマンフォード法で負閉路を検出するのだが、 実はそれだけだと嘘解法になる(経路上に、小さな負閉路と大きな正のパスが並列であるといつまでたっても収束しない)。 事前にBFS/DFSで到達不可能な閉路を処理しておく必要がある。
テストが甘く、頂点数分だけ余計にベルマンフォード法の計算を回すと通る。
ABC 061 D - Score Attack B パスに正/負の得点があるグラフでの最大得点。
ABC137Eとほぼ同じ。嘘解法で検査が通るのも同じ…。

Union-Find木

ABC 049 D - 連結 / Connectivity B

鉄道と道路の両方で連結されている都市の数を求める。

union-find を2つつくってから、それをくっつければよいのだが、くっつけるときにそのままやるとO(N^2) になってしまうので工夫する。
union-find の親を属性として持たせ、属性についてソートしてから重複する要素数を数える(解説見てやった)。

ABC 120 D - Decayed Bridges B

橋が順に崩落してゆくとき、相互に行き来できなくなった島の組み合わせの数を求める。

逆向きで考えて、橋が順にできてゆくとしたときに union-find で連結してゆく発想でやる。

ABC 126 E - 1 or 2 C

1 または 2 が書かれているカードについて、\(A_{Xi} + A_{Yi} + Zi\)の合計値の情報がわかっているとき、 何枚めくったら全部がわかるか。

情報が連鎖するので、Union-Findでつないでいって、最終的にできた木の数を数える。 実際には、結合した回数を数えると楽だった。

ARC 036 D - 偶数メートル D

偶数メートルでたどりつけるかどうかを判定する。

奇数+奇数 = 偶数になるので、Union-Find木を2つつくるのが想定解法。 自分はUnion-Find木を変形して、「奇数でいける木」の情報を持って解いた。

Binary Indexed Tree

Codeforces
Round #568(Div.2) Exam in BerSU (hard version) 		D

N人が順に合計M時間のテストを受ける。 それぞれ合格するのに要する所要時間が決まっている。落ちると時間は0。 j人目がテストに通るためにそれまでの何人が落ちればよいかの最小値を求める。

合格者の最大数を求める。
j-1人目までを、昇順に所要時間を並べた時、所要時間の累積和が\(M-a_j\) 以下になるような最大の人数を求める。
順に更新されてゆくためまず所要時間を全体で昇順ソート場所を決めてからBITに入れてゆき、 BITの中で累積和を2分探索して境界値を求める。
もうひとつBITをつくり、こちらには人数を入れておくとその境界値に対応する人数が求まる。
BITと累積和の2分探索は相性が良いのかもしれない。

解き方はすぐに思いついたが、実装が…。Codeforcesはテストパターンが公開されているのでデバッグできたが、 AtCoderだったら諦めてたかも。

と思ってEditorial見たら、実は点数が0点～100点しかないので、 点数ごとに学生を数えて累積和にしたら一瞬でできた気が…(BIT関係ない)

ネットワークフロー

最大流、最小費用流、最小カットなど。
ARC074 F - Lotus Leaves C スタートからゴールにカエルがたどりつけなくするための、除去すべき葉の最小数を求める。
 軸を頂点、辺を葉として最小カットを求めるとものすごくすっきり解ける。
AGC034 D - Manhattan Max Matching D 平面上の2N個の点を、X座標、Y座標の差の絶対値が最大になるよう組み合わせる。
 絶対値を、max(a-b, a+b, -a+b, -a-b) と扱うと、ネットワークフローの辺の数が削減でき最小費用流で解ける。
ARC 031 D - 買い物上手 E アイテムを買った結果得られる経験値の、経験値/費用を最大化する。
 燃やす埋める問題と2分探索の組み合わせ。

パズル系

ソートの回数の削減、優先度付きキューの扱いなどでうまくやると解ける問題。
競技プログラミングではこの手の発想勝負な問題が一番多く、そしてこれが一番壁…。
ABC 123 D - Cake 123 C

\(A_X\)個、\(B_Y\)個、\(C_Z個\) のケーキからおいしさ上位順で選んだ3000個を順に出力する。全部ソートすると間に合わない。

ソートの対象をどう削減するか。 priority_queue を使って最小限でやることもできる。

diverta 2019 Programming Contest2 B - Picking Up B

平面上にばらまかれた点のうち、前の点からの座標オフセットが [p, q] であるものの個数が 最大となるよう [p, q] をとった時の個数を求める。

出題でなN数が少ないので、複数の点が直前上とか考えずに、 p, q を定めてから座標のオフセットを全部数えてしまえばよいのですが…。

diverta 2019 Programming Contest2 C - Successive Subtraction B

\(A_1, A_2,,,, A_N\) から、任意の2個の数x, yを取り出し x-y を書き込んだ時に最後に残る数の最大値。

少なくとも一つの数がプラス、一つの数がマイナスとなり、 ほかの数は任意の符号なのでそうなるように演算を構成する。 合計値を求めるのは簡単なのだけれど、その過程を出力されるので頑張って構成する。