{__uint128_t}
に頼らなくてもいけるかなぁと思ったのだけど、1WA 残る。
かなり多くの人が D 落としてしまったのは、これかな：
[20350950](https://atcoder.jp/contests/abc192/submissions/20350950)
## 2021-02-19
### AGC046B - Extension ★ DP
解説にはなんかむずかしいことが書いてあるが、以下の漸化式で DP できる
（ [@kyopro_friends さんのツイート](https://twitter.com/kyopro_friends/status/1274619856420102144) の図も参照）。
$${
dp[i][j] = dp[i][j-1] * i + dp[i-1][j] * j - dp[i-1][j-1]*(i-1)*(j-1)
$$}
引き算があるので、mod をとった結果が負になる場合の処理がいった：
[20258607](https://atcoder.jp/contests/agc046/submissions/20258607)
### AGC051A - Dodecagon
[tsugittaさんの解説](https://zenn.dev/tsugitta/articles/atcoder-agc-051)が詳しい：
[20258992](https://atcoder.jp/contests/agc051/submissions/20258992)
## 2021-02-18
### ABC016D - 一刀両断
なんども WA を出した。線分と辺が交差する回数を数えるのだけど、与えられているのが直線ではなく「線分」なので、判定をもうすこし正確にする必要があった。
交差の判定は、ベクトルの外積を用いた「符号付き面積」で行うのがいい（線分が水平や垂直の場合もそのまま扱える）のだが、線分 A-B が短いために交差しないケースもあるので、上図の左の形での判定だけでなく、右の形でも判定して、いずれも OK の場合のみ「交差」となる：
[20247064](https://atcoder.jp/contests/abc016/submissions/20247064)
### 天下一プログラマーコンテスト 2014 予選 A B - かぶりん！
ふつうにシミュレートできる。時系列のイベント queue として、priority_queue
をつかった：
[20248708](https://atcoder.jp/contests/tenka1-2014-quala/submissions/20248708)
## 2021-02-17
### ABC029D - 1 ★
もういっかいやっておこう：[20230054](https://atcoder.jp/contests/abc029/submissions/20230054)
### ARC034C - 約数かつ倍数
とけた：
[20231769](https://atcoder.jp/contests/arc034/submissions/20231769)
### ABC030D - へんてこ辞書
なかなか合わせられなかった。もういちど解いておこう：
[20234229](https://atcoder.jp/contests/abc030/submissions/20234229)
※はまったポイントは提出コードのコメントに記載（二か所）
ひとつめに関しては、かならずループはあるのだから、ループ検出するまで繰り返せばよかった。
## 2021-02-16
### ARC045B - ドキドキデート大作戦高橋君
各教室の被覆数（何人がその教室を担当しているか）を Imos 法で求めるというのは思いついたのだけど、各担当者の範囲に被覆数１の教室を含むかどうかをすばやく判定する方法が思いつかなかった。
解説にあるとおり、被覆数が１であるような教室の場所が１、そうでない場所が０であるような配列の累積和を用いると、各区間に被覆数１であるような教室を含むかどうか（何個含むか）をすばやく求めることができる：
[20204846](https://atcoder.jp/contests/arc045/submissions/20204846)
### ARC028B - 特別賞
でけた：
[20205550](https://atcoder.jp/contests/arc028/submissions/20205550)
## 2021-02-15
### ARC038B - マス目と駒 ★
どうも Min-Max 的探索を書いてしまって TLE しがち。
メモ化していて計算量は同じかなぁと思ったのだけど。
もっとシンプルに Judge を一本化できる：
[20191654](https://atcoder.jp/contests/arc038/submissions/20191654)
### ARC046B - 石取り大作戦 ★
だいたいこんな感じかなぁと思ったものの、つめきれず。のちほど再挑戦。
プログラム自体は簡単：
[20193097](https://atcoder.jp/contests/arc046/submissions/20193097)
## 2021-02-14
### ARC005C - 器物損壊！高橋君
0-1 BFS:
[20179519](https://atcoder.jp/contests/arc005/submissions/20179519)
### ABC037D - 経路 ★★
DP と思って眺めてたのに書けなかった。要復習！
入力１に関しては、下記のような dp 配列になって、これを全部足したものが答え。
メモ化で素直に書ける：[20181763](https://atcoder.jp/contests/abc037/submissions/20181763)
$${
7 3 2
3 2 1
$$}
※ typo でバグったりもした。要注意。
## 2021-02-13
### ARC049B - 高橋ノルム君
重み付き座標の重心のようなものを求めるんだろうか…とか考えてたどり着けず。
そうかぁ、ニブタンかぁ。そうだなぁ：
[20141178](https://atcoder.jp/contests/arc049/submissions/20141178)
### ARC086D - Non-decreasing
難しそうと思ってしまった。
非負整数の列から累積和をつくれば non-decreasing になるなぁと気づけば、
- すべてゼロ以下の数列からも同様に累積和をつくる要領で Non-decreasing にできる
- 一般の数列も N 回以下の操作で、ゼロ以上もしくはゼロ以下ばかりの数列にできる
というので、かならず 2N 回以下で可能：
[20141653](https://atcoder.jp/contests/arc086/submissions/20141653)
## 2021-02-12
### ARC011C - ダブレット
普通に書くだけだったのだけど、ちょっとバグって時間がかかった（タイポ的ミスだった）のと、コーナーケース（first = last の場合や、到達不可だった場合）処理がぬけているのを入力例２，３に救われたりしたのは要反省：
[20116524](https://atcoder.jp/contests/arc011/submissions/20116524)
### ABC095D - Static Sushi ★
なん日か前にわからず解説みて、少し寝かせてあったやつ。
どうにか AC のプログラムは提出したが、なんかあやふや：
[20123174](https://atcoder.jp/contests/abc095/submissions/20123174)
解説を素直に実装すると、[こんな感じ](https://atcoder.jp/contests/abc095/submissions/20121427)
になりそうに思えるんだけど、これだと WA なんですよね。
同じ方法であれこれ実装しても、おなじく WA となるので、実装上のミスというより方法にあやまりがあるようなのだけど…。
## 2021-02-11
### ARC111C - Too Heavy ★
ひとまず、体重の軽いものから正しい荷物を持たせればいいという方法のコードを提出した。
解説にある考察に関して要復習：
[20092744](https://atcoder.jp/contests/arc111/submissions/20092744)
### Code Festival 2014 予選 A D - 壊れた電卓
桁 dp と Bit dp の組み合わせ。かけた！…んだけど、AC でるまで何度も間違えた。
- 電卓の場合、押さなきゃいいだけなので、最初の桁を 0 にするのは数字を使ったことにならない
- 差が正で推移する場合と、負で推移する場合と別にもつ。（ただし、０から正、負への遷移があるので両者を完全に別系統とは扱えない）
提出コード：
[20108362](https://atcoder.jp/contests/code-festival-2014-quala/submissions/20108362)
### Indeed なう予選 B D - 高橋くんと数列
出題意図とは違うやり方で解けてしまった…のだけど、int あふれて一度 WA だしてしまった：
[20109994](https://atcoder.jp/contests/indeednow-qualb/submissions/20109994)
あとで、解説にある方法もみておこう。
### ABC026D - 高橋君ボール１号
単調増加ではないけれど、連続、かつ、初期値が f(0) < 100, f(200) > 200 が示せるのでニブタンで求まる。また、こういった浮動小数点数ニブタンでは ok と ng の差で while ループにするのでなく、固定で 100 回とか回せばよい：
[20112064](https://atcoder.jp/contests/abc026/submissions/20112064)
## 2021-02-10
### ARC027B - 大事なことなので Z 回書きました
解けた、が、未使用アルファベットの扱いをさぼって最初 WA だしてしまった。
はじめから単純にやればよかった：
[20084371](https://atcoder.jp/contests/arc027/submissions/20084371)
### ABC005D - おいしいたこ焼きの焼き方
とけた。が、入力２がなかったら（４つ焼くより３つ焼いたほうがいいケース）WA
だしてたと思う：
[20084696](https://atcoder.jp/contests/abc005/submissions/20084696)
### ABC025D - 25個の整数 ★
bitDP。自力では解けなかったので要復習。
25ビットで、使用済の数字、または、すでに埋まっているマスを表現するのだろうなぁとは思ったのだけど、マスの埋まり状況と数字の使用状況、着目しているマスがどれで…みたいなことを状態に持とうとしたら、何次元配列になるのかしら…とか悩んでしまった。
解説にあるように、数字の１から順につかっていくことに決めると、マスの埋まり状況を表現するビットマップだけで、マスの状況と次に使う数字がわかる！（すでに埋まっているマスの個数＋１が次の数字なので）。
また、これも解説にある通りだが、１から数字をうめていくことにきめると、置けるケース、置けないケースの判定が単純にできる。
２５マスとも空の状態から、数字の１から順に置いていくので、
入力であたえらえる情報は、すでに埋まっている数字と考えるのではなくて、そのマスにおける数字を制限していると考えればよい。
提出コードは、ほぼ解説のまんま（のつもり）：
[20088881](https://atcoder.jp/contests/abc025/submissions/20088881)
## 2021-02-09
### ARC025B - チョコレート
二次元累積和。黒と白で符号を逆にしておけば、「たしてゼロ」が求める状態になる。
H, W <= 100 の制約で \(\textrm{O}((HW)^2)\) でいけるのね、というので少し迷った：
[20064273](https://atcoder.jp/contests/arc025/submissions/20064273)
### ABC002B - 派閥
最終的には自力で通したのだけど、回り道をしてしまった。
N <= 12 なので全通り試せる：
[20064900](https://atcoder.jp/contests/abc002/submissions/20064900)
### ABC180E - Traveling Salesman among Aerial Cities
復習：
[20065826](https://atcoder.jp/contests/abc180/submissions/20065826)
## 2021-02-08
### CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除 ★
入力文字列を二つにわける。あり得る分け方すべてについて、２つの文字列の最長共通部分列長を求めればよい：
[20049411](https://atcoder.jp/contests/code-festival-2015-morning-middle/submissions/20049411)
最長共通部分列 (LCS; Longest Common Subsequence) については、
Educational DP Contest の [F LCS](https://atcoder.jp/contests/dp/tasks/dp_f)
で復習しておくのがいい。
### DigitalArts プログラミンコンテスト 2012 B - Passward
以下の方針で与えられたパスワードを加工するプログラムを提出したのだが、WA
1. 先頭文字が 'a' でない場合には、先頭文字をひとつ小さくし、さらに、
1. 後続文字列のなかに 'z' でないものがあったらそれをひとつ大きくする
1. 後続文字列がすべて 'z' だった場合には、文字列の後ろに 'a' とつけたす
1. 後続文字列が 'a' の場合には、先頭を 'a' と取り除き、さらに、
1. 後続文字列のなかに 'z' でないものがあったらそれをひとつ大きくする
1. 後続文字列がすべて 'z' だった場合には、文字列の後ろに 'a' とつけたす
1の2のケースで、加工後の文字列の長さが 20 を超えてしまうケースの考慮が漏れてしまっていた：
[20051382](https://atcoder.jp/contests/digitalarts2012/submissions/20051382)
### ARC111B - Reversible Cards
復習。今回は、各連結成分が木か否かを判定するのに、各連結成分に含まれる辺の数を保持しておいてそれを用いるようにしてみた（前回は、DSF で判定しようとしてややてこずった）：
[20052137](https://atcoder.jp/contests/arc111/submissions/20052137)
### ARC111A - Simple Math 2
[復習](https://uhideyuki.sakura.ne.jp/studs/index.cgi/ja/atcoder_drills4#2021-01-09p1)
:
[20052602](https://atcoder.jp/contests/arc111/submissions/20052602)
## 2021-02-06
### CODE FESTIVAL 2015 予選A - D 壊れた電車
復習。方法はわかっていたのだけど、C++ で書くのがはじめてで、えらいはまった。
- 計算途中であふれることも多いので、int ではなく ll を使おう
- ニブタンの (ng, ok] は開区間なので、ng の初期値は 0 ではなく -1
- いろいろやり直す過程で ${1 << 60} とかやって嵌る（${1LL << 60} でないとだめ）
など。どれもあるあるなのだけど、見直しておいてよかったかな：
[19950214](https://atcoder.jp/contests/code-festival-2015-quala/submissions/19950214)
## 2021-02-05
### ARC021B- Your Numbers are XORed...
解けた…が、ちゃんと証明せずに半信半疑で提出してしまったので、
そのあたり要復習：
[19929241](https://atcoder.jp/contests/arc021/submissions/19929241)
### ARC018B - 格子点と整数
ふつうに全探索：
[19929510](https://atcoder.jp/contests/arc018/submissions/19929510)
### ARC050B - 花束
復習。めぐる式：
[19932295](https://atcoder.jp/contests/arc050/submissions/19932295)
## 2021-02-04
### Donuts プロコンチャレンジ 2015 B - Tokyo 7th シスターズ
とけた：
[19917722](https://atcoder.jp/contests/donuts-2015/submissions/19917722)
### ARC030B - ツリーグラフ
とけた：
[19918292](https://atcoder.jp/contests/arc030/submissions/19918292)
いっぱつ WA を出してしまった。どこにも石がないケース。
## 2021-02-03
### AGC047A - Integer Product
解けた、けど、ちょっと書くのにてこずりすぎ：
[19890766](https://atcoder.jp/contests/agc047/submissions/19890766)
## 2021-02-02
### ARC048B - AtCoderでじゃんけんを
Rate に関する累積和と、（レート、手）を出した人の人数をカウントしておくことで計算可能。
…なのに、うまく比較関数を書いてやればソートできるかなぁと考えてしまって答えが合わなくて嵌った。二者を正しく大小比較はできるけど、じゃんけんなので全体の順序は決められないんですよね。そりゃそうだ：
[19867365](https://atcoder.jp/contests/arc048/submissions/19867365)
### CODE FESTIVAL 2014 EASY C - 身体バランス
N <= 1000 なので Warshall-Floyd でいけた…のだが、
corner-case と名のついたテストケースで WA。なかなか何故かわからなかった。
dp[s][k] == dp[k][t] となるケースには、k が中継点として適切な場合以外に、
k に到達できない場合 (dp[s][k] == dp[k][t] == INF) が含まれていた：
[19879315](https://atcoder.jp/contests/code-festival-2014-morning-easy/submissions/19879315)
もうちょっと N が大きい場合には、s, t それぞれを始点とした dijkstra をやるのだろう。
そっちも確認しておこう。
Dijkstra 版。たしかに、だいぶ速い：
[19883895](https://atcoder.jp/contests/code-festival-2014-morning-easy/submissions/19883895)
## 2021-02-01
### 天下一プログラマーコンテスト 2015 予選 B B - 天下一リテラル
文脈自由文法は括弧の対応を数えられるのだ的な。
自力でといたけど、二回 WA を出してしまった。
"{X}" が set になる（１要素のときはカンマが出現しない）ことに対応する部分で：
[19848414](https://atcoder.jp/contests/tenka1-2015-qualb/submissions/19848414)
### ARC054B - ムーアの法則
下に凸であるような関数なので、３分探索 (Ternary Search) できる。
f(t1) >= f(t2) の場合（上図の赤線のような形）には、次の探索範囲を [t1, hi] に、
そうでない場合には [lo, t2] にする：
[19852531](https://atcoder.jp/contests/arc054/submissions/19852531)
### ABC186D - Sum of Difference
惨敗した ABC186D の復習。この D は、今日どうにか自力で解けたけど、時間かかった。
図形的に考えた（それは、それでいい）のだけど、解説にあるように、数式でシンプルに整理できたほうがよさそう。
\(\{a_i\}\) をあらかじめソートしておくことで i< j のとき \(|a_j - a_i|\ = \ (a_j - a_i)\) にできる。すると、二重Σの内側は、各 i について次のようになる。
\[
\Sigma_{j=i+1}^{N} (a_j - a_i) = \Sigma_{j=i+1}^{N} a_j \ - \ (N-i) a_i
\]
これは、累積和をあらかじめ求めておくことで O(1) で求まる。
したがって、全体の計算量ははじめのソートが支配的となり O(N log N):
[19855576](https://atcoder.jp/contests/abc186/submissions/19855576)
## 2021-01-31
### ABC190E - Magical Ornament ★★
コンテスト中に解けなかったもの。
もうすこし時間があれば解けたかな…と思ったけど、思っていたより難しかったので、
あの方針では解けなかったな。
復習したいポイント：
- dp
- dfs を K 回前もってしておく
なお、実装時にぽろぽろバグったのが、Ci を番号 i で扱うのと c[i] のとの混乱。
もう一回解いておくべし：
[19826224](https://atcoder.jp/contests/abc190/submissions/19826224)
### AGC002C - Knot Puzzle
なんか、いいかげんな貪欲法で WA だしてしまった。反省。
どう工夫しても、最後のひとつの結び目というのができる。隣り合う二本のロープの合計が
L 以上のところを選べばよい。ひとつもなければ Impossible となる。
ひとつあれば、その結び目を最後に残すように、より左の結び目を左から順に、
より右の結び目を右から順にほどき、最後に、選んだひとつをほどく：
[19837865](https://atcoder.jp/contests/agc002/submissions/19837865)
### ARC051B - 円錐
累積和：
[19839517](https://atcoder.jp/contests/arc052/submissions/19839517)
実は、結構バグった。手元で簡単なテストケースをつくってデバッグ。
本番でも、落ち着いてできるかな（はじめからバグのないコードが書ければいいのだけど。）
### ABC183E - Confluence
方針はすぐ立ったのだけど、自力で実装しようとした Union Find がバグってたようで、
無限に WA の様相だった。まずは、方針があってるかためそうと ACL の dsu を使うようにしたら、あっさり AC:
[19842873](https://atcoder.jp/contests/abc183/submissions/19842873)
Union Find を自分で書くことについては、あとで見直そう。
### ABC190F - Shift and Inversions
転倒数（または反転数; inversion number) に関する問題。
転倒数は BIT をつかって O(N log N) で求めることができる。
また、毎回のシフトで先頭にあった数が末尾にうつるのだが、その数を ai とすると
- 数列から ai を取り除くことで、転倒数は ai だけへる（残された数のなかに ai より小さいものが ai 個あるので）
- さらに、末尾に ai を付け加えることで、転倒数は (N - (ai + 1)) 個増える
となる。したがって、一度元の数列の転倒数を O(N log N) で求めたあとは、毎回 O(1)：[19844750](https://atcoder.jp/contests/abc190/submissions/19844750)
なお、また int をあふれさせて WA だしてしまった。なにげなく int つかわない！
## 2021-01-30
### ABC044C - 高橋君とカード（復習）
かけた：
[19762015](https://atcoder.jp/contests/abc044/submissions/19762015)
### AGC029B - Power of two ★
なかなか AC できなかった。反省：
[19765864](https://atcoder.jp/contests/agc029/submissions/19765864)
### ABC155E - Payment
桁 dp。とけた：
[19766489](https://atcoder.jp/contests/abc155/submissions/19766489)
### ABC018C - 菱形カウント
とけた：
[19767781](https://atcoder.jp/contests/abc018/submissions/19767781)
## 2021-01-29
### CODE FESTIVAL 2014 qual B C - 錬金術士
なるべく S1 からとるようにしたら、S1 から何文字とることになるか、および、
なるべく S2 からとるようにしたら、S2 から何文字とることになるかを求める。
それらが両方とも N 以上になれば "YES":
[19753167](https://atcoder.jp/contests/code-festival-2014-qualb/submissions/19753167)
### ABC022C - Blue Bird ★
[ABC022C へのリンク](https://atcoder.jp/contests/abc022/tasks/abc022_c)
これは、自力で解いておきたかった。ノーヒントで復習したほうがいいので、
ここにはヒントになることを書かないでおく：
[19753777](https://atcoder.jp/contests/abc022/submissions/19753777)
### ABC074D - Restoring Road Network
これは、どうにか自力でとけた：
[19756185](https://atcoder.jp/contests/abc074/submissions/19756185)
## 2021-01-28
### ABC078D - ABS ★
もしかして、また Min-Max? とか思ったけど、[そんなわけなかった](https://atcoder.jp/contests/abc078/submissions/19733896)。
解説みて一応提出しておいたけど、間をおいて自力で解いてみよう：
[19734017](https://atcoder.jp/contests/abc078/submissions/19734017)
### ABC175E - Picking Goods
ちょっとだけ凝った dp という感じ。普通に解けたのだけど、
はじめ int をあふれさせてしまって WA。${using ll = long long;}
して用いるようにしよう：
[19735515](https://atcoder.jp/contests/abc175/submissions/19735515)
### ABC020C - 壁抜け
めぐる式にぶたんで。遠回りが最適になるケースもあるので、上や右にも移動するように bfs
にすべき（それで WA だした）：
[19736506](https://atcoder.jp/contests/abc020/submissions/19736506)
## 2021-01-27
### ABC027C - 倍々ゲーム
解けた。
各ターンで出現しうる x の値は下のようになる。2x を選ぶと下図における上よりの値、
2x+1 を選ぶとしたよりの値になる。
$${
Turn 0 1 2 3
---------------
x 1 2 4 8
9
5 10
11
3 6 12
13
7 14
15
$$}
ここで、N がどこにあるかによって、各プレイヤーのとる戦略が変わる。
もし、\(2^{2k-1} \le N < 2^{2k}\) であれば、Takahashi くんは自分のターンで x が N を超えてしまう危険があるので、Takahashi 君は 2x を、Aoki 君は 2x+1 を選ぶことになる。
反対に、 \(2^{2k} \le N < 2^{2k+1}\) であれば、
Takahashi 君は 2x +1 を、Aoki 君は 2x を選ぶ。
このとき、どちらが勝つかをシミュレーションすればよい：
[19712523](https://atcoder.jp/contests/abc027/submissions/19712523)
### ABC068D - Decrease (Contestant ver.)
N = 2 で考えてしまった。二回で周期がくるので、任意の K について答えが求まる。
…のだが、これでは K が大きいときに ai が上限を超えてしまう。
そこで諦めたしまったのだが、N=50 で同様に考えればよかった。
はじめ、k=0 のときに {49, 49, 49, ..., 49} とする。
k=1 のときには、一回の操作でこれになればいいので、{99, 48, 48, ..., 48}
k=2 のときには {98, 98, 47, ..., 47}
k=50 で {50, 50, 50, ..., 50}、k=100 で {51,51,51, ..., 51} のようになり、50 回ごとに周期がある。
なので、高々 N-1 回のシミュレーションで答えがもとまる。また、シミュレーションの際に最大値として選ぶ位置は 0, 1, ..., N-1 のように前から選んでいけばよい：
[19715575](https://atcoder.jp/contests/abc068/submissions/19715575)
### ABC023C - 収集王
各列の個数、各行の個数をかぞえておいて、合計が k かつ交差する点に飴ががないか、
合計が k+1 でかつ飴がある場合を数え上げればいい。
自分でかいたものは、これをそのまま数えようとして TLE になってしまった。
そうではなく、各列、各行の個数の頻度をもっておいて合計が k になる組合せの個数を計算。
すると、交差する点に飴があるケースは数えすぎ、合計が k+1 でかつ飴があるケースは数え漏れになるので、N 個の飴すべてについてこれをチェックして足し引きしてやればよい。
計算量は O(R+C+N)：
[19718154](https://atcoder.jp/contests/abc023/submissions/19718154)
### ARC014C - 魂の還る場所
シミュレーションではなく、考察がいるタイプの問題。まちがえた：
[19722676](https://atcoder.jp/contests/arc014/submissions/19722676)
## 2021-01-26
### ABC044C - 高橋君とカード ★
「\(\{a_i\}\) の平均が A」 から「 \(\{a_i - A\}\) の総和が 0 」
への読み替えはすぐわかって、総和が 0 になる組み合わせをどうやって数えたものかと。
50 個からの全列挙はできないけど、半分ならギリできそう！というので、
つい、「半分全列挙」をしてみたくなって、やってみたものの
[TLE](https://atcoder.jp/contests/abc044/submissions/19699685)
dp でしたね。典型的な dp だと思うけど、まだ、ぱっと出てこないなぁ：
[19699889](https://atcoder.jp/contests/abc044/submissions/19699889)
### ABC146F - Sugoroku ★
後ろから、なるべく遠くから順位みていく DFS で解けそうだなと実装するも
[TLE](https://atcoder.jp/contests/abc146/submissions/19702431)。
もしや、C++ で書けば OK かと思い同じものを C++ で書いてみたが
[同じ](https://atcoder.jp/contests/abc146/submissions/19702744)。
解説動画にもあるが、実は、この問題は貪欲法でとけるので、到達できる場合には、
上記の DFS は一本道にゴールまでたどりつく。したがって、-1 になるケースのみ
前もって弾いてやると [AC](https://atcoder.jp/contests/abc146/submissions/19703072)
となる。
貪欲でとけることを見抜かずにこれで通すのはどうかとも思うが、
-1 になるのはどういうケースかというのを考えるのは大事だなと思う。
（追記：いまの DFS で失敗するケースは、再帰をひとつ上にさかのぼって再トライしても決して成功しないので、そこでアボートさせるしかなかった。…ということを考えると、いまのコードがそのまま貪欲法になるのね。）
解説にあった、後ろからの dp (単調性を用いて工夫）で各ノードからの距離をもとめて答えをだす方法は、あとでもう一度復習したほうがいいと思う：
[19703504](https://atcoder.jp/contests/abc146/submissions/19703504)
ところで、最初の dfs を Haskell で解くときにしらべたのだけど、[Maybe a] から一番はじめの Just a (もしくはなければ Nothing）をもとめるのは ${msum} でよい。${firstJust = msum} だった。
### ARC019B - こだわりの名前
解けたけど、何回か WA だした。もうすこし慎重に：
[19706191](https://atcoder.jp/contests/arc019/submissions/19706191)
### ABC025C - 双子と○×ゲーム
どうやるんだろと思って解説をみてしまったんだけど、普通に Min-Max やれとのこと。
3x3 の〇×くらいだったら、素朴な min-max やれちゃうのか（枝狩りなどはせず）：
[19708902](https://atcoder.jp/contests/abc025/submissions/19708902)
## 2021-01-25
今日から Haskell / C++ の二刀流でいくことにした。
いままで Haskell でやったやつの復習を C++ でやればいいかも。
### ABC013C - 節制
３変数のうち１つを決めたら残り２つは鶴亀算というパターン。
胃袋に上限がないので、食べない日は最後にまとめてよい。
その食べない日数をきめたら、最終日に満腹度が 1 以上になるための食べ方は鶴亀算でもとまるので、食べない日数の全探索。
方針はすぐにたったのだけど、実装でなんどもミスってやたら時間がかかってしまった。反省。
- a, b, c, d, e と一文字変数名がたくさん使用済なのを、鶴亀算中でも使おうとしたり
- 最終日にちょうど 0 になってしまったり
- なるべく安くすませたいので、安い方でもとめて不足をあとから求めたほうがよかった
- 途中の引き算結果がマイナスになった計算がおかしくなったり
投稿したもの：
[19680450](https://atcoder.jp/contests/abc013/submissions/19680450)
### ABC017C - ハイスコア
Imos。各洞くつは、[l, r] の範囲の宝石を点数 s で覆っている。
各宝石について、自身を覆っている点数の合計を imos 法で求める。
それは、その宝石をとらないことに決めたときに失われる点数に等しい。
なので、その最小値を \(\Sigma \ s_i\) から引けばよい：
[19683622](https://atcoder.jp/contests/abc017/submissions/19683622)
### ABC021C - 正直者の高橋くん
以下の方針を思いついたので書いてみる。解説にあったものの１つもこの線だった：
- 各ノードについて、a からの距離を bfs で求める
- 求めた距離をつかって、距離 0 から順に dp で到達経路の総数をもとめていく
Haskell で書いたものは WA やら TLE がとれず。
おなじものを C++ で書いてみたら、すんなり通って 9ms だった：
[19685973](https://atcoder.jp/contests/abc021/submissions/19685973)
ほかのひとの回答をみるに、最初の dfs のときに dp もやってしまっているものが多いようだった（が、べつに上記のやりかたでも良いよねと思ってる）。
Haskell でも通しておきたいが、あとで。
### ABC034C - 経路
でかい \({}_nC_r\) を求めるだけ。
- Haskell : [19687355](https://atcoder.jp/contests/abc034/submissions/19687355)
- C++ : [19688105](https://atcoder.jp/contests/abc034/submissions/19688105)
C++ の方は、modinv をソラで書こうとして結構苦労したり。また、階乗や modinv を int
で計算してたら桁あふれたりした。
## 2021-01-24
### ABC014C - AtCoder
昔の問題で、ふつうの Imos 法。…だが、AC を出してしまった。
Imos が済んでから maximum をとればいいのだけど（それなら AC）、
二回サーチするのは無駄なので、サーチしながら max をとるようにしたのだが、
Imos のサーチは添え字 1 から始めるので、最大値の初期値を d[0] にすべきだったという
凡ミスでした：
[19676692](https://atcoder.jp/contests/abc014/submissions/19676692)
### ABC082D - FT Robot
これは、一度解けなくて解説をみたのを、日をあらためて今日書いてみたというやつ。
- x 座標、y 座標それぞれについて dp
- s を、'T' で区切られた連続する 'F' の個数（0 以上）の列になおす： [d0, d1, d2, ... ]
- d0 は特別扱い（かならず x が増える方向に動く）
- x 軸方向の移動に関する xds = [d2, d4, ...] と、y 軸方向の ydx = [d1, d3, ... ] にわける
- 初期値は dpx[0][d0] と dpy[0][0] がともに True で他は False
- xds の 1 つめが d1 だとすると、dpx[1][d0±d1] が True になる
すべて処理したあとに、ターゲット座標にあたる dp 値が x, y ともに True になっているかどうかで判定：
[19675494](https://atcoder.jp/contests/abc082/submissions/19675494)
### ACL Contest 1 A - Reachable Towns ★
ACL コンテストでもあるし、みるからに UnionFind かなと思うのだけど、
愚直に辺を張ろうとすると多すぎて TLE となる。
まず、x 座標で昇順にソートし、自分より前にあるもの（x 座標が小さい）で、かつ、
y 座標も小さいものの辺を張るようにする（以下のコード片は解説より抜粋）。
$${
dsu d(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (y[i] > y[j]) d.merge(i, j)
}
}
$$}
ここで、各 i について、[0,(i-1)] の範囲の点をすべてチェックする必要はなく、
各連結成分のうち、もっとも y 座標の小さいものを保持しておけばいい。
…というと複雑そうにみえるが、Set をひとつもちいて比較的シンプルに書ける。
- 当初 S は空
- 各 yi に対して、
- S に yi より小さいものがなければ（これは S の先頭をみるだけで判定か）yi を S に加える
- S に yi より小さいものがあれば、それらはすべて i と連結する。さらに、そのなかで一番小さいもの以外は S から取り除く（yi はもとから S に追加しない）
投稿例：
[19674063](https://atcoder.jp/contests/acl1/submissions/19674063)
注意： 上の投稿例で、最初 loop' の「次」の添え字をしていするために (k+1) を渡してしまってバグってました。
$${
loop' i yi k s | k >= Set.size s = return s
| otherwise = do let (yj, j) = Set.elemAt k s
if yj > yi
then return s
else do uniteUF uf i j
-- 下の (k+1) は間違い！
loop' i yi (k+1) (Set.deleteAt k s)
$$}
${deleteAt k} しているので、もともと k+1 の位置にあったものがひとつまえにずれてくるので。
### Nikkei 2019 qual D - Restore the Tree ★
トポロジカルソートの典型的な問題かもしれない。
トポロジカルソートしたあと、各ノード v の親は、w → v の辺をもつもののうち最も大きい（より後ろ、根から遠い）ものとなる。
この問題のように、グラフが非循環であることがわかっている場合には、
トポロジカルソートは比較的簡単に実装できる。
dfs でも可能だが、今回は入次数０の頂点集合と入次数の配列を更新しながら答えをだしていく方法をとった：
[19664161](https://atcoder.jp/contests/nikkei2019-qual/submissions/19664161)
## 2021-01-23
### ABC189E - Rotate and Flip ★
アフィン変換：
[19657798](https://atcoder.jp/contests/abc189/submissions/19657798)
## 2021-01-22
### ABC161F - Division or Subtraction ★
反省点２つ：
- 問題は理解したけど、check 関数をうまくかけず
- N が M^2 の形のとき、divisors 関数が M をダブルカウントしてしまって WA
[19561028](https://atcoder.jp/contests/abc161/submissions/19561028)
### ABC129E - Sum Equals Xor ★
a + b = a `xor` b になる条件もわかったし、
dp[N+1][2] の桁 dp だよなぁと思ったものの、そこから漸化式をうまくつくれなかった。
要復習です：
[19563074](https://atcoder.jp/contests/abc129/submissions/19563074)
## 2021-01-21
### ABC133E - Virus Tree 2
とけた！ 解説と同じ解き方かなぁと思ったら（本質的には同じだろうけど）、
自分のやった解き方のほうがわかりやすい気がしたので、以下に書いてみる。
木の根から順に、同じ深さのノードについては一列にならべて左から順に彩色していくことを考える。
- 根であるノード 0 は、 K 色のうちどの色をつかってもいいので、K 通り
- ノード 1 は、ノード 0 がすでに１色つかっているのを避ける必要があるので K - 1 通り
- ノード ２は、ノード 0, 1 が使っている色を避けて K - 2 通り
- ...
- ノード 5 は、自分より左にあるノード 4 と、親 2 つの色を避けて K - 3 通り
というようになる。各ノードは、位置に応じて K - x 通りの色を使えるのだが、この x (上図で赤字で示した数字）は、以下のように求めることができる。
- depth = 0 のとき ： 0
- depth = 1 のとき（親は１つしかない）： 自分より左にあるノードの数 ＋ １
- depth ＞ 1 のとき（親が 2 つ以上ある）： 自分より左にあるノードの数 ＋ 2
これを dfs で求めて、最後に k - x_i をすべてかけ合わせればよい：
[19546426](https://atcoder.jp/contests/abc133/submissions/19546426)
### ABC150D - Semi Common Multiple ★
ずいぶん簡単だなぁと思って提出して、まんまと WA。
X は \(a_k / 2 \) の奇数倍なので、\(\{a_k / 2\}\) の最小公倍数をもとめて、
それの奇数倍がいくつ M 以下の範囲にあるかを数えればよい…。
のだが、その「最小公倍数」自体が、ある \(a_i\) の偶数倍になっていたらだめなわけで。
そんときは 0 個と答えなければならない：
[19552246](https://atcoder.jp/contests/abc150/submissions/19552246)
### ARC105B - MAX-=min ★
これ、灰色難易度なんだけど、思いつかなかった。
0 <= x <= y のとき gcd(x, y) == gcd(x, y-x) である（ユークリッドの互除法を思い出そう）
ので、操作の過程で gcd は変わらない。カードの数字が全部 a になったときには、gcd (a, a) == a なので、結局もとの数列の gcd を求めればよい：
[19555108](https://atcoder.jp/contests/arc105/submissions/19555108)
## 2021-01-20
### ABC174F - Range Set Query
昨日とけなかったやつを。解き方は、解説みてもいまいちピンとこなかったのだけど、
[f_jhrさんの記事](https://evolite.hatenablog.com/entry/20200809/1596902898)
をみたらよくわかった。
ソートも解説のように右端でソートする必然性もなく、この記事と同様に左端でソート。
なお、BIT をつかっても時間制限は厳しく、次の出現位置や答えの蓄積に Map を使っていたらTLE してしまった。使えるところは全て unboxed vector を使うように書き換えてやっと通った：
[19528522](https://atcoder.jp/contests/abc174/submissions/19528522)
### ABC170E - Smart Infants
自力であっさりとけたよ！
各幼稚園の制御に Set を順序付き多重集合として使い、
各幼稚園の最高レートの最小値を求めるのには SegTree を用いた。
解説では、後者も順序付き多重集合でやってて、それでもいけたかもしれない：
[19529952](https://atcoder.jp/contests/abc170/submissions/19529952)
### ABC156E - Roaming
とけた。最初、以下の ${res} の前に ${!} がないものを投稿したら
TLE になってしまった。恐ろしい…:
[19533686](https://atcoder.jp/contests/abc156/submissions/19533686)
$${
-- z : number of empty room : [0..(min (n-1) k)]
solve z !res | z > min (n-1) k = res
| otherwise = let f1 = n `c` z
f2 = (n-1) `c` (n-z-1)
r = f1 * f2 `mod` p
in solve (z+1) ((res+r)`mod`p)
$$}
### Codefestival 2016 本線 C - Interpretation
なにがむずかしいんだろ？って感じで AC。
人 N 人と言語 M 個の合計 (N+M) ノードの連結性を考えればいいのだけど、
人だけでやろうとするとしんどいらしい：
[19536625](https://atcoder.jp/contests/cf16-final/submissions/19536625)
## 2021-01-19
### ABC185E - Sequence Matching ★
なんか文字列の距離を算出するうまい方法をしらなければならないのかな、とか思っちゃった。
が、dp でした。
dp[i][j] を、\(\{A_i\}\) が先頭 i 文字のみ\(\{B_i\}\) が先頭 j 文字のみあった場合の答えとする。
- i または j が 0 のときの dp[i][j] は簡単に求まる（dp[0][j] = j, dp[i][0] = i）
- i, j いずれも 0 でない場合は、\(A_i,\ B_j\) のどちらか片方を消すか、両方のこす場合しかないので、以下の３通りのいずれか（一番小さいもの）
- dp[i-1][j] + 1 : Ai を消した場合
- dp[i][j-1] + 1 : Bj を消した場合
- dp[i-1][j-1] + x, x = {1 (\(A_i\ \ne \ B_j\)), 0 (\(A_i \ = \ \ B_j\))}
回答例：
[19518742](https://atcoder.jp/contests/abc185/submissions/19518742)
### AGC041B - Voting Judges ★
ニブタンだなってことはわかったのだけど、判定ルーチンをうまくかけず敗退。
解説をよんだものの、まだ、ピンと来ていない。
とりあえず、見よう見まねで書いてみた：
[19519951](https://atcoder.jp/contests/agc041/submissions/19519951)
要復習。
### AGC041B 再トライ
自分でモノにしたく、再度書いてみた。
bisectLeft を使ううえで、添え字が大きくなるについれて True になる方向の方が扱いやすい。
そこで、A0 <= A1 <= ... <= A(n-1) になるよう昇順でソート。
Ax が選択され得るかどうかは、以下のように判定できる。
- x >= n-p であれば、もともと p 個以内にはいっているため可能
- Ax + M < A(n-p) であれば、不可能
- それ以外の場合は、以下の合計が MV 未満であれば不可能（MV 以上であれば可能）
- [0, x] の範囲 （x+1 個）については全員が投票しても問題ない
- [n-(p-1), n-1] の範囲 (p-1 個）についても全員が投票しても問題ない
- j <- [x+1, n-p] の範囲については、Ax + M - Aj までなら投票しても問題ない
このように書いたものを再投稿した：
[19521339](https://atcoder.jp/contests/agc041/submissions/19521339)
### ABC174F - Range Set Query
各色について出現位置の集合をもっておけばいけるかなと思ったのだけど、
これだと O(QN log N) で [TLE](https://atcoder.jp/contests/abc174/submissions/19524670) となる。
平衡二分木を使おうが、自前で binary search しようがオーダはいっしょだ。
Fenwick Tree または BIT (Binary Indexed Tree) （呼び名が違うだけで同じもの）
を使うといいらしい。未修でした。
まず、BIT は snippets/ に用意しておいた： [Bit.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Bit.hs)
sum, add ともに計算量は O(logN)。
BIT を使った解放だが、解説のように右端でソートしなくても、
左端で考えたほうがわかりやすいのでは？という気がした（[参考](https://evolite.hatenablog.com/entry/20200809/1596902898))
## 2021-01-18
### ABC159E - Dividing Chocolate
とけた、んだけど、実装にちょっと時間かかりすぎたかも：
[19501713](https://atcoder.jp/contests/abc159/submissions/19501713)
### ABC075D - Axis-Parallel Rectangle
座標圧縮、二次元累積和、そして、全探索といった感じ。
すぐに方針は立って解けたのだが、すごく時間がかかってしまった。
最初の版を書くのに少し時間がかかったというのもあるが、
その後謎の MLE にでくわす。もしやとおもい、solve の引数の ${res} を
${!res} にしたら、あっさり通った。
すこし昔の問題で、メモリ制限がきついというのもあるかもしれないけど、
そんなことがあるのか…：
[19502534](https://atcoder.jp/contests/abc075/submissions/19502534)
## 2021-01-17
### Tenka1 2018 D - Crossing
わからなかったので解説をみた。
下図のように数字をならべる。図中の線はどれも長さが同じで、
どの二本をえらんでも一か所で交わる。
### ARC093D - Grid Components
十分大きなグリッドを用意して、上半分を黒、下半分を白で塗る。
上の黒半分の中に、A-1 個の孤立した白いマスをつくっていく。このとき、上半分の黒を分断してしまわないようにする。
下半分にも同様に B-1 個の孤立した黒マスをつくっていく。
たとえば、500 500 の場合はつぎのようになる：
$${
50 100
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##
####################################################################################################
#.#.#.#.#.#.#.#.#.##################################################################################
####################################################################################################
####################################################################################################
####################################################################################################
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..
....................................................................................................
.#.#.#.#.#.#.#.#.#..................................................................................
....................................................................................................
....................................................................................................
....................................................................................................
$$}
### ABC186E - Throne ★
いろいろと要復習。
x 回の移動で玉座にたどりつくことは、\(xK + S \ \equiv \ 0 \ (\textrm{mod}\ N)\)
なので、これを解くという問題に帰着できる。
ここまではわかったのだが、解けなかった。
M が素数でないときに、\(A^{(M-2)}\) が mod M における逆元になるとは限らないので、
拡張ユークリッドの互除法などを用いる必要がある。
とりあえず見様見真似で提出：
[19495399](https://atcoder.jp/contests/abc186/submissions/19495399)
## 2021-01-16
### ABC105D - Candy Distribution ★
累積和の各項を剰余で分類するのは、たまに見かける。
似てるとこでいうと、[ABC164D](https://uhideyuki.sakura.ne.jp/studs/index.cgi/ja/atcoder_drills3#2020-04-27p0)
なども
区間 [l, r) の和が M の倍数であることは、累積和 \(\{B_i\}\) をつくっておいて、
\(B_l \equiv B_r \ (\textrm{mod} M)\) であることと同じ。
なので、この問題をとくには、各 \(x \in [0, M)\) について、\(B_i \equiv x \ (\textrm{mod} M)\) となるものの個数をカウントして用いればよい。
カウントには、M が大きいので、配列ではなく Map などを用いる：
[19451943](https://atcoder.jp/contests/abc105/submissions/19451943)
### Keyence2021C - Robot on Grid ★★
コンテストで１時間弱あったので解けるかなぁとか思っていたんだけど、
あのままでは解けなかったな。
(1,1) から (h,w) にいたるある一本の経路に着目する。
経路中に空白がなければ、その経路は \(3^{(HW-K)}\) 回実現する。
つぎに経路中に空白が k 個ある場合を考える。各空白にはどの文字をいれてもいいわけではなく、その経路がそのマスを横切った方向に応じて、３種類の文字のうちの２つを入れなけらばならない。一方、経路上にない空白（HW-K-k 個ある）には３種類の文字のどれをいれても可。
したがって、その経路が実現する回数は \(2^k3^{(HW-K-k)}\) となる。
\[
2^k3^{(HW-K-k)}\ = \ \frac{2}{3}^k3^{(HW-K)}
\]
であることに着目すると、経路上に k 個空白のあるような経路の重みを
\(\frac{2}{3}^k\) 倍すればいいので、1 から始めて空白にであうたびに
\(\frac{2}{3}\) 倍し、最後に \(3^{(HW-K)}\) を掛ければよいことがわかる。
回答例：
[19480433](https://atcoder.jp/contests/keyence2021/submissions/19480433)
## 2021-01-15
### ABC087D - People on a Line
むずかしく感じなかったのだけど、[TLE](https://atcoder.jp/contests/abc087/submissions/19436976)
連結成分ごとに dfs で数字をわりあてていって、全連結成分についてできれば OK。
その通りなのだけど、真面目に連結成分をもとめてリスト化する必要はなくて、
全ノードを順番にみていって、未採番なら dfs を回すようにすればよかった：
[19437235](https://atcoder.jp/contests/abc087/submissions/19437235)
xi = 0 に初期化して採番していくと、負の数になることに注意。
（連結成分を求めるのをやめたとき、最初、負なら未採番と判定していてバグった）
### ABC184F - Playing Tag on Tree
とけた：
[19440021](https://atcoder.jp/contests/abc148/submissions/19440021)
### ABC184E - Third Avenue ★★
どうも TLE がとれなくて。BFS は Data.Sequence を queue として
使っていたのだけど、どうもこれがあまり速くないようだったので、
unboxed mutable vector をつかった deque を作って通してみた。
テレポート先リストに、距離を付け加えるのが遅いのかなと思って、
長さを更新するための特別なエントリを enqueue したり、
長さを付け加える push 関数をつくったりした。
- 長さを更新する特別なエントリをつかう：[19449587](https://atcoder.jp/contests/abc184/submissions/19449587)
- 後ろにくっつける版：[19449574](https://atcoder.jp/contests/abc184/submissions/19449574)
- 前にくっつける版：[19449559](https://atcoder.jp/contests/abc184/submissions/19449559)
…が、deque の完成度が低いので、明日再実装しよう→ した：
[IOUQueue](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/IOUQueue.hs)
- サイズを２の冪にしつつ、リングバファにする
- メソッド名を一般的なものに合わせる。[これ](https://cpprefjp.github.io/reference/deque/deque.html) とか。
- 長さがたりないときは grow する。
## 2021-01-14
### ABC157E - Simple String Queries ★
自力でとけず。Set (平衡二分木）で各アルファベットの出現位置を管理する。
平衡二分木は、要素を二分探索できるので、l 以上の出現位置を検索し、
それが r 以下なら部分文字列にその文字が出現すると判定できる。
もちろん、クエリ１のために要素を追加・削除することも可能：
[19423557](https://atcoder.jp/contests/abc157/submissions/19423557)
### ABC144E - Gluttony ★
問題読み間違えて「？？」ってなってた。これは自力で解いておきたかった：
[19425645](https://atcoder.jp/contests/abc144/submissions/19425645)
## 2021-01-13
### ABC117D - XXOR
とけた。昨日やった 第5回ドワンゴからの挑戦状予選 Ｂ - Sum AND Subarrays
の経験が生きたと思う:
[19410282](https://atcoder.jp/contests/abc117/submissions/19410282)
### ABC184F - Programming Contest
N <= 40 だと、ビットマスクで前パターンを表現するにはでかすぎるなぁなどと思いつつ
（ここで「半分ならいける！」と思い至ればよかった）、方針たてられず敗北。
半分にわければ、消費時間のバリエーションを全列挙できる…ということで、
半分全列挙でした：
[19410992](https://atcoder.jp/contests/abc184/submissions/19410992)
### ABC167E - Colorful Blocks ★
すぐに着想はできたのだけど、実装でしくって WA をだした。
毎回 \({}_n C_r\) や \(M(M-1)^{(n-1-k)}\) を計算しなおしていては TLE になるので、
直前の値をつかって漸進的に求めるようにしたのだが、それでしくじった。
最初のしくじりは、`mod` p をとるべきところで抜かしていたというケアレスミス
なんだけど、それを直しても [1 つ WA](https://atcoder.jp/contests/abc167/submissions/19412028) が残ってしまった。
これは、\(M(M-1)^{(k-1)} = M(M-1)^k / (M-1) \) のように計算していたのだが、
M = 1 のケースでだめだったというもの。なおしたものがこれ：
[19412335](https://atcoder.jp/contests/abc167/submissions/19412335)
こんな微妙な計算をせずに、普通にメモ化的な高速化の方が安全かもしれない
（実際、それで最初の AC となった）：
[19411964](https://atcoder.jp/contests/abc167/submissions/19411964)
## 2021-01-12
### 第5回ドワンゴからの挑戦状予選 Ｂ - Sum AND Subarrays ★
解けそうな気がしつつ嘘っぱちを Submit してしまった。
答えの求め方が結構面白かったこともあり、あとで復習しておきたい。
累積和をつかって、\(N(N-1)/2\) 通りのスコアを計算して、それの降順リストをつくって使うところまでは合っていたのだけど、それの上位 K 個を選んで AND とればいいのではと
簡単に考えてしまって [WA](https://atcoder.jp/contests/dwacon5th-prelims/submissions/19386522)
より上位にあるビットの方が重要なので、(x | (1 << t)) & Ai == (x | (1 << t))
となる Ai が k 個以上あれば x に (1 << t) を加えるというのを、t <- [40, 39, .. 1]
について試していって得られたものが答え：
[19386967](https://atcoder.jp/contests/dwacon5th-prelims/submissions/19386967)
### ABC104C - All Green
敗北。
単純に Greedy にはいけないし、dp 的なのも難しそう。
そこで、解く問題数を固定すれば、
その問題数でもっとも合計スコアが高くなる選び方なら Greedy にいけるのではないか。
それでニブタンすれば解ける！とか思って書いてみたけど、
[WA](https://atcoder.jp/contests/abc104/submissions/19392091)
たとえば、以下の入力例 (テストケースの b08) は 59 が答えなのだけど、59 問以上解く前提において１問あたりの点数が最も高いのは 200 点問題を37 問解く場合なので、
これを選択してしまって間違えた。
$${
2 559100
59 553200
37 343300
$$}
正解は、解説にあるとおりなのだけど、たとえば 100 点問題と 200 点問題が十分あるときに（いずれもコンプリートしないときに）、100点問題を 3 問、200点問題を 3 問とく理由はない。なぜなら、200点問題 6 問といたほうが必ず得だから。
そのことから、以下が言える。
- １問以上といてかつコンプリートしない配点の問題はたかだか１種類
- １問以上といてかつコンプリートしない問題は、コンプリートしないもののなかで最も配点が高いもの。
あとは、コンプリートする問題のバリエーション（2^10通り）すべてについて試せばよい：
[19392886](https://atcoder.jp/contests/abc104/submissions/19392886)
### ABC153F - Silver Fox vs Monster
TLE (とケアレスミスの WA) を出してしまったが、その後自力で AC できた。
左端の敵をなるべく右に置いた爆弾で仕留めていくという貪欲法でいいのだが、
素朴にやると TLE となる。そこで、現在位置での爆弾の威力と、その爆弾の
威力がマイナスになる位置と幅を格納した priority queue を持って、
スパースな imos 法のような方法で解いた：
[19400089](https://atcoder.jp/contests/abc153/submissions/19400089)
解説のように、各モンスター i について、巻き添えにできるもっとも右の番号 j を
尺取法などで求めておくことでも可。その場合でも、体力の計算に累積和を用いる。
## 2021-01-11
### ABC099D - Good Grid
C が比較的小さいので、塗り分けを全通り試せる（30*29*28=24360通り）。
各塗分けについて、全グリッドを走査していては間に合わないが、
最初に mod グループごとにどの色が何回用いられているかを数えておけば、
塗り分けごとの違和感の合計を O(C) で計算できるので間に合う：
[19379907](https://atcoder.jp/contests/abc099/submissions/19379907)
### Tenka1 2018 D - Crossing ★
こんどもう一回やろう。
### ABC128D - enqueue
ふつうにとけた：
[19381048](https://atcoder.jp/contests/abc128/submissions/19381048)
### ABC047D - 高橋君と見えざる手
これもふつうにとけた：
[19382867](https://atcoder.jp/contests/abc047/submissions/19382867)
## 2021-01-10
### ARC111B - Reversible Cards ★
グラフの彩色。色をノード、カードの裏表を辺に対応させたグラフにおいて、
各辺の端点のうち片方だけ色を塗ることができる（解説では片方だけ「光らせる」）
とき、いくつのノードに色を塗れるか。
これは、連結成分ごとにみて、そのサイズを N とすると。
それが木なら N-1 個, 木でなければ N 個のノードに色を塗ることができる。
提出例：
[19303647](https://atcoder.jp/contests/arc111/submissions/19303647)
### ABC188E - Peddler
コンテストではそれなりに時間があったのに TLE, WA となって通せず。
DP でとけると気づけば、さほど難しくはなかった。
最初、後ろから「もらう dp」で書くのかなと思ったけど、
書き始めたら、配る dp で前から書くのが簡単だった。
dp[i] : その町にたどりつくまでに買うことのできる金の最安値
無限大で初期化しておいて、前から順にみて配っていけばいい：
[19361665](https://atcoder.jp/contests/abc188/submissions/19361665)
## 2021-01-09
### ARC108C - Keep Graph Connected
最小全域木にすれば必ず正しく番号を振れるし、最小全域木はいつもつくれるよな、
というのには気づいたものの WA を二連発。
最初は、最小全域木をつくりながら番号を振ろうとして失敗。
そんな無理をしなくても、いったんつくってから dfs で確実に番号を振ればよい。
のだが、二回目は、よく考えもせずに番号を振ってまた WA。要反省：
[19277350](https://atcoder.jp/contests/arc108/submissions/19277350)
### ARC111A - Simple Math 2 ★
剰余の性質に関する問題。一問も解けずに nosub 不参加となってしまった…。
解説にあるとおり、以下がなりたつため、\(10^N\) の代わりに \(10^N (\textrm{mod} \ M^2) \) をつかって計算できる。
\[
\lfloor \frac{10^N - k M^2}{M} \rfloor \equiv \lfloor \frac{10^N}{M} - k M \rfloor
\equiv \lfloor \frac{10^N}{M} \rfloor - k M
\equiv \lfloor \frac{10^N}{M} \rfloor (\textrm{mod}\ M)
\]
なるほどと思い、それなら \(M^2\) だけでなく \(M^3\) の剰余でもいいはずだよね、
と思って試したら、入力例３で答えがあわなかった。
どうも、modinv の引数の範囲が Int に収まっていても、途中の計算があふれる場合があるのね。恐ろしいので、[modinv の内部計算に Integer を使うように変えておく](https://github.com/unnohideyuki/AtHaskell/commit/63550abab4c4cba73cfd61e8b2f14711b33cd429)。
\(M^3\) で計算する必要はないのだが、それで計算したものを submit しておいた：
[19295575](https://atcoder.jp/contests/arc111/submissions/19295575)
## 2021-01-08
### ABC151E - Max-Min Sums
とけた：
[19258673](https://atcoder.jp/contests/abc151/submissions/19258673)
## 2021-01-07
### ABC114D - 756
なんどか WA だしてしまったけど、いちお自力で AC: [19245823](https://atcoder.jp/contests/abc114/submissions/19245823)
WA になってしまった理由は、100 までの整数では 5*5*3 パターンしかないねと
思ってしまったんだけど（混乱）、100! までなので、25*3, 5*15 はおろか、75 まであった。
（素因数分解の添え字のえらびかたのパターン）
### （復習）AGC031B - Reversi
まだ記憶にあたらしいので、実力で解いたという感じではないのだけど、
ともかく、今回はいっぱつで書けた。
以下のような具体例で dp の更新を考える。
dp[6] は下図のように 4 （通り）。dp[7] を求めるには、まず、この後ろにただ C を
付けたケースと、４文字目の C と 7 文字目の C を選んで色を変えたケースを考えれば
排他かつ網羅的となり、dp[7] = dp[6] + dp[4]
$${
i | 1 2 3 4 5 6 7 ...
c| C A B C B A|C
-+------------------
| C A B C B A|C
| C C C C B A|C
| C A A A A A|C
| C A B B B A|C
-+------------------
| C A B C|C C C
| C C C C|C C C
$$}
提出例：
[19250522](https://atcoder.jp/contests/agc031/submissions/19250522)
### ABC126E - 1 or 2
簡単だった：
[19250827](https://atcoder.jp/contests/abc126/submissions/19250827)
## 2021-01-06
### AISING 2020 D - Anything Goes to Zero ★
なんか自分の知らないアルゴリズムが必要なのかなと思考停止してしまったが、
そうではなかった。以下、解説にあるとおりだけど、ポイントをいくつか。
- x が十分ちいさければ、g(x) = x `mod` popcount(x) は素直に実装可能
- 初回の g(X_i) をどうするかだけが問題
実装例：
[19233979](https://atcoder.jp/contests/aising2020/submissions/19233979)
最初 RE を出してしまった。popc - 1 がゼロになってしまうケース。
### ABC015D - 高橋くんの苦悩 ★
典型的な dp だと思うんだけど、Bit DP にしたいけど出来ないなぁ（N が大きいのでビット列の状態数が大きくなりすぎる）とか思ってしまった。
$${
dp[i][j][k] : 使用済の幅 i, 使用した枚数, いま着目している対象の番号
$$}
とすると、dp は 0 で初期化しておいた上で、
$${
dp[i][j][k] = max { dp[i][j][k-1] , dp[i-a_k][j-1][k-1] + b_k}
$$}
で求まる。それぞれ、すでに k-1 番までで幅 i つかっていて k 番目は貼らなかった場合と、
k-1番目までで幅 i-a だったところから新たに k 番目を貼った場合にあたる
[19236667](https://atcoder.jp/contests/abc015/submissions/19236667)
## 2021-01-05
### ABC134E - Sequence Decomposing ★
解説動画をみて実装した。
as の先頭 a を順にとりだし、末尾の数字が a より小さいもののうち最大にバケツを選んで、
末尾の数字をaで書き換えていく。
バケツを末尾数字で昇順にソートしておけば、バケツの選択は二分探索でき、
かつ、書き換えによってソート順は崩れない。
なので、単純に「配列」でいいのだけど、長さが前にも後ろにも伸びるので少し工夫がいる：
[19211828](https://atcoder.jp/contests/abc134/submissions/19211828)
### AGC031B - Reversi ★★
解説よんだりしても、あまりピンときてない。いちおう書いてはみたけど、
時間をおいて、もういちどよく考えてみよう：
[19213605](https://atcoder.jp/contests/agc031/submissions/19213605)
いま書いたものは、
[こちらの記事](https://competitive12.blogspot.com/2019/03/agc-031-reversi.html)
をもとにしている。解説にちかいのは、[こちら](https://www.hamayanhamayan.com/entry/2019/03/17/003754) だと思う。
## 2021-01-04
### ABC179D - Leaping Tak ★
解説動画を見始めたところで（配る dp の絵をみて）、
配る dp + imos 法でいけるじゃないかと書き始めたものの、あわせられず。
dp 配列ひとつで、配る dp と imos の両方をやろうとして混乱していた。
解説と同じように、dp 配列と累積和用をわけて AC:
[19202626](https://atcoder.jp/contests/abc179/submissions/19202626)
解説と同じように「もらうdp」でも書いてみたほうがいいかもしれない。
### ABC183E - Queen on Grid
直前に ABC179D をやっていたので、これは自力で AC。
累積和ともらう dp といった感じで：
[19203562](https://atcoder.jp/contests/abc183/submissions/19203562)
## 2021-01-03
今日から水色埋め。2AC/day ペースで二月末くらいをめどに。
### ABC187E - Through Path (木に対する imos法）
木構造に対する imos 法のようなやつかなと思ったんだけど、コンテスト中には解けなかった。
その見立ては正しくて、自分と自分より葉に近いノードに加える数値を記録しておいて、
最後に足しこんでいけばいいのだが、少し難しいのは、逆のケース。自分より「下」以外に足すケース。これは、全体に足したうえで、自分より葉に近いノードからは同じだけ引けばいい。
- 各辺の両端を記憶しておく (as, bs)
- dfs のため、各ノードからいけるノードのリストをつくっておく (es)
- 1つもの dfs で各ノードの深さ（根=node 0 からの距離）を測っておく
- 各クエリについて、
- 足す側が根に近ければ根に +x (全体に x 足すのに相当) し、一つ「下」のノードに -x
- 足す側が葉に近ければ、そこに +x
- ２つめの dfs で累積和（ここでも各ノードの深さを用いる）
実装例：
[19176602](https://atcoder.jp/contests/abc187/submissions/19176602)
### ARC107C - Shuffle Permutation
行列の要素はすべて異なるので、同じ行があったらどうしようという心配は無用だった。
あと、直接交換可能でなくとも、交換可能なもの同士のグラフで同じ連結成分にあるもの同士は交換可能。なので、解説にあるとおり、連結成分ごとにそのサイズの階乗を掛けていけばよい。
列の交換と行の交換は独立に考えられるので、それぞれの積をさらにかけたものが答え：
[19189642](https://atcoder.jp/contests/arc107/submissions/19189642)
## 2021-01-01
### ABC034D - 食塩水（×）
「平均値最大化」という手法が身についていなくて解けなかったのと、
答えが Double になる場合の二分探索でもまごついた。
- 条件：濃度が x 以上になるように k 個選べるかどうか
この条件を満たすかどうかは、
\[
\frac{\Sigma w_i p_i}{\Sigma w_i} \ge x
\]
と表せる。この式を変形すると、
\[
\Sigma w_i (p_i - x) \ge 0
\]
となり、これなら \(w_i (p_i - x)\)を大きいものから k 個足した結果が 0 以上かどうかで判定可能。
なお、浮動小数点数での二分探索については、[前回解いたとき](https://atcoder.jp/contests/abc034/submissions/17658275) には専用のものをその場で書いたのだけど、
[今回](https://atcoder.jp/contests/abc034/submissions/19091363)
のように bisect を使った方が見通しは良いように思う。
「a[0], ..., a[n-1] の平均が K 以上」を「a[0]-K, ..., a[n-1]-K の総和が 0 以上」にするテクは二分探索に限らずちょくちょく見る[らしい](https://qiita.com/drken/items/2f56925972c1d34e05d8#%E4%BE%8B%E9%A1%8C-3-1-4%E5%B9%B3%E5%9D%87%E6%9C%80%E5%A4%A7%E5%8C%96)
ので要注意。
### ABC180E - Traveling Salesman among Aerial Cities （×）
典型的な巡回セールスマン問題。いちど蟻本みて書いたのだけど、今回もみて書いた。
S をすでに巡回済の頂点の集合としたとき、現在 v にいる状態から、
残りすべての頂点をめぐって頂点0に到達するときの移動コストの最小値を
dp[S][v] とあらわす。すると、初期値および漸化式は以下のようになる。
- dp[すべて巡回済][0] = 0
- dp[S][v] = min { dp[S ∪ {u}][u] + d(v, u) | u \(\notin\) S}
S はビット列であらわし（bitDP）、
- S: (すべて巡回済み-1) から空集合まで: [(1 << n - 2), (1 << n - 3) .. 0]
- v: [0..(n-1)]
- u: [0..(n-1)]
の３重ループで状態を更新してやればよい。
$${
for (int S = (1 << n) - 2; S >= 0; S--)
for (int v = 0; v < n; v++)
for (int u = 0; u < n; u++)
if (!(S >> u & 1))
dp[S][v] = min (dp[S][v], dp[S | 1 << u][u] + d[v][u]);
$$}
提出例：
[19098083](https://atcoder.jp/contests/abc180/submissions/19098083)