使用言語を Haskell に変えてみました！
復習ず のしょっぱな。
基本的な考え方 (まずどちらも１本ずつ必要で、そのあと (x-1), (y-1) でわる)は OK だったものの、負になってないかのチェックをおこたって WA
また、bisectRight は、条件を満たすもののうち最も右にあるものの「さらに１つ先」のインデックスだぞ！
方針はすぐに立ったものの、入力例２があわず。 左に行ってから折り返すのと、右にいってから折り返すのとで良い方をとらなければいけないことを見落としていた（この投稿例でいうと r1 の方のみ考えてしまった）： 19082735
★★実装力的な意味で要復習
何日か前に自力ではとけなくて解説を読んだので、今日はそれを実装してみた。 …が、TLE と WA がとれず。
これくらいが要注意点だったかな： 19058216
桁 dp, 要復習： 19063138
メモ： 最初、k （二番目の添え字）に関するループ範囲を、最初 [0..(k-1)] としてしまったために答えがあわず、原因になかなか気づけなかった。
３変数だけど、ひとつ固定すると「つるかめ算」になるので O(1) で解けるので、 全体で O(N) となり、たぶん、これだけでも解けた。
さらに、老人２人を大人１人と赤ちゃん１人に交換可能なので、老人の数は０と１のみ試せばよく、全体でも O(1) となる。
ここ、早とちりして、大人２人を赤ちゃん１人にも交換可能じゃないかとおもってしまったが、 それだと総人数がかわってしまうので、交換可能じゃない。
ぜんぜんなんてことないのだが、WA がなかなかとれず。 最大値をもとめるのに、初期値 (solve 関数に最初にあたえる res) を 0 としてしまって、 答えが負のケースに間違えるというポカだった。注意しよう。
これ、解説読んでもよくわかんなかったやつ。
解説とは少し違うのだけど、次のように考えるのがわかりやすいように思う：
なので、後者を行うのに十分なだけ、\(a_j\) に 2 を足す余地があるかどうかを調べればよい： 19046757
要反省。
なんか、よさそうな方法を思いついたものの、あり得る解をすべて列挙できずに WA。 解説になるとおりなのだが、\(f(x)\) は高々 9*17 = 153 にしかならないので、 x の取り得る範囲は十分にせまく、全探索が可能だった： 19018899
けんちょんさんの と似たやり方でやろうとして、WA だった。 まず不要な 1 を対消滅させてから残りを処理しようとしたのが最適でなかったのに気づいたところでこの方針をあきらめてしまったのだが、この方針でもちゃんとやれば通せたのか： 18995525
解説にあるやり方はまだ。
いちおう自力で AC だが、ごちゃごちゃしている。 もっかいやっておきたい: 18999918
緑のうち、推定難易度が experimental でないものが６つ、このページで★をつけたものが４つ。合計１０問は、ちょっとしっかり復習しようかな。
最初、連結成分の数を数えるのに、nub <$> mapM (findUF uf) [0..(n-1)] とかやって TLE をだしてしまった。解説にあるように、root が自分自身になるようなノードの数を数えればよい（その方がずっと速い）。
dp かなと思ったけど書けなかった。貪欲っぽくやっても解けるようだが、 dp できちんとかけるようになっておきたい。要復習。
ごく単純な BFS なのにハマった回。
TLE がでてしまい、ずいぶん悩んだ。いろいろ遠回りしたんだけど、 TLE の原因は、探索において、つぎの升に到達したときの距離を ct , すでにその升に書かれている距離を t としたときの t < ct か t <= ct の違いだった。はじめその升を重複して訪れないための条件を前者で書いていたので、 なんどもなんども同じ升をめぐることになってしまって探索回数が伸びていた。
Queue にいれる前に判定しないといけないのかとおもって、書き換えたりしたけど、 それは関係なかったので、当初の書き方でももちろん通った： 18626717
トーナメント方式で、k 回試合をすると（グラフの深さが k）勝者がきまる。 なので、k 回文字列を更新して、最初の文字を取り出せばよい。 また、文字列は常に長さ N あればいいので（index は i mod N なので）、 長さ N の文字列を k 回更新すればいい。計算量は \(\textrm O(KN)\)
提出例：18480027
典型的な確率 dp だった模様。解説動画 をみて、最後の＋１が直感的にわかりづらいなぁなどと思って、少し考え込むなど。要復習
dp[i][j][k] = (i*dp[i+1][j][k] + j*dp[i][j+1][k] + k*dp[i][j][k+1]) / (i+j+k) + 1.0
そうか、i/(i+j+k) の確率で、dp[i+1][j][k] から１手の距離になるので、それを素直に書くと下のようになる。上の式は、それと等価なのね。
dp[i][j][k] = (i/(i+j+k)) * (dp[i+1][j][k]+1) + (j/(i+j+k)) * (dp[i][j+1][k]+1) + (k/(i+j+k)) * (dp[i][j][k+1]+1)
解説文 には、こちらの式が書いてある。
i, j, k いずれかが100のときには、すでにゴールしているので、ゴールまでの期待手数は 0。 あとは、i, j, k が大きいものから順にうめていって（３重ループ）、最後に dp[i][j][k] を表示するか、メモ化再帰にするか、どちらでも解ける。
提出例：
茶色埋めの一環。
はじめ書いたプログラムは WA だった。 なぜかわからず、テストケースを見る。ひとつみたらわかった。
keyencbbzsqzezyvefbhtwriljcvrymirjmbljehlslmrxslnspsiujxiznmlyfcpe
で、書き直して提出、AC
答えはそうかなと思ったのですが、ほんとにそうなのか不安になってしまった。 \(m = a_1 \times a_2 \times \cdots \times a_n\) とすると、\(m \mod ai = 0\) なので、\((m-1) \mod a_i = a_i - 1\) となるので、\(f(m-1) = \Sigma_{i=1}^{N} (a_i - 1)\) が答え。
別に難しいわけではないのだけど、ByteString.intercalate なる関数を初めてつかった： 18221180
intercalate （挿入する）という英単語もしらなかった。
問題みて、「座標圧縮がつかえるのでは」と思って書き始めてしまい、 当然 TLE になったのだが軌道修正できずに落としてしまった。
S, T にくらべて、N がはっきりちいさいわけではないので、座標圧縮は効果がない。
順列で考えると、全集合は N^3 個。
N 以下の数のうち、K より小さいものを A, K より大きいものを B とすると、
最初、リストの一番上のケースのみしか考えてなくて、入力例１で気づいた orz.
簡単だなぁと思いつつ、WA をだしてしまう。 K-1個の和がすでに十分なケース (コード中では t = r*k - sum0 が負になるケース）の考慮が漏れていて、k < n のときには結果的に拾われていたが、k == n のときに条件がもれて WA
引き算の結果が０以上になるとは自動的には保証されないことを気を付けるとか、 いくらか避ける方法はあったはず、かな。
提出例： 18008350
ニブタンだと思ってとりかかったのに、めちゃめちゃ何度も間違えてしまった。 まず、判定方法をさくっと思いつけず。反省を込めて、以下解説文の説明とほぼ同じですが、書いておく：
K個の花束が作れるかという判定問題を考える。 花束をつくるためには、まず、赤い花と青い花が少なくとも 1 本ずつ必要なので、 赤い花と青い花を K 本ずつ減らす。赤い花束をつくるには、さらに赤い花が x-1 本必要なので、 赤い花束は (r-k) `div` (x-1) 本つくることができる。 どうように、青い花束は (b-k) `div` (y-1) 本つくることができる。よって、 ((r-k) `div` (x-1) + (b-k) `div` (y-1)) >= k かどうかを判定すればよい。
また、bisectRight の使い方を間違えたり（False < True であることに気を付けて使う必要がある）したのだが、二分探索くらいは、その場で書いた方がいいのかもしれない。
また、このくらいの難易度の問題では、run スクリプト（自作のチェックスクリプト）を使った方がよさそう。
実装例：17606716
解けたけど、B を決めたらAが決まる的に、B についてでの全探索にして、なんどかWA。 解説にあるとおり、A、B どちらも範囲がせまいので、両方について単純に全探索でよかった。 （このあたりのあたりをきちんとつけよう）
１時間以上つかえたのに、WA をひとつ残してしまって通せなかった。
m >= n - 1 のときには -1 を出力すればいいのだが、n = 1, m = 0 のときが この判定に引っかかってアウトだった。 m = 0 のときは n にかかわらず Ok だという ある意味コーナーケースにひっかかった。
反省点は以下：
また、Haskell で TLE になったので C++ に乗り換えたりしてしまったのだけど、 Haskell での TLE は、ループ条件がまずかったため、初めから i < 0 だったときに無限ループしていたのだった。TLE だからといって Haskell が遅いせいにしてはいけない。
ポイントが２つあった。ひとつは、１回のシミュレーションを累積和をもちいて \(O(N)\) で処理すること。もうひとつは、それでも K 回やると \(O(KN)\) になるのをどうするか。
シミュレーションしないで済む方法があるのかなと思ったら、そうではなくて、 操作を一定回数以上行うと、すべての電球の明るさが N の状態に収束するので、 それ以上シミュレーションする必要がなくなる。
「シミュレーションしないで済む方法がある」以外の出口を思いつかなかったので、 こういう考え方もあるのか、と。
回答例： 16789119
なんども submit したけど、TLE がとれず。最後 TLE いっこで結局通せなかった。
はじめ DFS で TLE になり、プレーンな BSF に変更。 近場から埋めることになるのでいいかなと思ったのだが、これでもまだ TLE。 歩いていけるコストの増えない移動と、ワープ先をまぜこぜにするのがいけないのかと queue を毎回ソートするようにして、当然だめで、ならばと Priority Queue に任せてみたが、そこでタイムアウトでした。TLE がひとつ残っていた： 16151035
行先は、いまいる場所と同じコストのものと、＋１のものの二種なので、 PriorityQueue などつかわなくても、dequeue で前者をあたまに、後者をおしりにくっつければよかった： 16152946
\({}_n C_r\) が最大になるのは、\(\{A_i\}\) のなかから最大のものを n に、 nの半分にもっとも近いものを r に選んだ場合。 切り捨てで失敗したくなかったので、距離に Double を使ったけど、r の二倍が n により近いことを条件にすれば整数でいけたかな： 16008154
たなばた。なんかひさびさだ。すこしずつでも緑を。
今日はみてすぐこの回答を思いついたけど、以前わかんなくて解説みたやつかもしんない： 15063034
なんてことない全探索なのだが、WA をだした。 升目を探索するときの座標を y, x の順で書くことが多かったのだけど、 今回 solve x y と書いてしまって、かつ、関数の中では solve y x の順で呼び出してしまっていた。悪いことに、入力例に対しては顕在化せず。 それを直せば普通に AC: 13155838
今週は、すこし真面目に C/D あたりをこなす。また、もういちどやった方がいいものに、 「（要復習★）」マークをつけてみよう。
簡単に考えて、いい加減なプログラムを書いてしまった。
S から T への一対一対応表をつくればいいのだが、それには、Si -> Ti のマップと、 Ti -> Si のマップの両方を使う。というのも、一対一対応であるというのは、
なのだが、後者は対偶をとって 「Ti == Tj ならば Si == Sj」と言い換えられる： 13116832
わからず解説をみてしまった。最初の i 人のなかで、同じ色の帽子をかぶっている人の 数を \(x_i\), \(y_i\), \(z_i\) とする。また、i 番目の人がかぶることのできる帽子の かぶり方を \(T_i\) 通りとする。
| i | i=0 | i=1 | i=2 | i=3 | i=4 | i=5 | i=6 |
| \(x_i\) | 0 | 1 | 2 | 2 | 2 | 2 | 3 |
| \(y_i\) | 0 | 0 | 0 | 1 | 1 | 2 | 2 |
| \(z_i\) | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
次にかぶれる帽子は、\(x_{i-1}\), \(y_{i-1}\), \(z_{i-1}\) のうち \(A_i\) と等しいものに対応する色の帽子である。 したがって、 \(T_i\) は [\(x_{i-1}\), \(y_{i-1}\), \(z_{i-1}\)] のうち、\(A_i\) と等しいものの個数、また、 (\(x_i\), \(y_i\), \(z_i\)) も、\(A_i\) と (\(x_{i-1}\), \(y_{i-1}\), \(z_{i-1}\))から求めることができる。
こたえは、\(T_1 \times T_2 \times \cdots T_n\) : 13015966
簡単に反省点をメモ。C, D ともに見てすぐ方針がたったのに、 バグったり、D では TLE を連発したりしてロスが多かった。
C については、検索の範囲が [1..n] と [1..m] の二種類あるのに、 間違っていたという初歩的なあやまり。これは手元で気づいたので WA にはならなかったが。
D は、ループの検出に d `elem` xs と List の elem を使うという、 競プロではありえない書き方から、TLE を連発。 町の個数は限られているのだから、フラグの配列をもてばよかった。
それ以外にも、k が短いケースで、off by one エラーとか。 TLE 連発で焦っていたというのもあるけど、ちょっとうかつすぎ。
やっぱ、緑をしっかりやるべきだな（ずっと同じこと言ってる）。
C# でレーティングがあがりつつあったころには、C# で 300 近く投稿していたわけだから、 まだ投稿数が100ほど足りないんだよな。
もしかして愚直にやんのかなといぶかしみつつ、 (A, B) の組み合わせが good なら (B, A) でも good なのでという程度の減らし方で やってみたけど、当然 TLE。
これでは、半分にしかならないのだけど、 解説にもあるとおり (A, B) が good なら (A+1, B+1) も good （上図も参照）なので、 (0,0) から (0, N-1) の範囲でしらべて、good だったものの個数を N 倍すればいい： 12988326
自力で書いたやつは、解説にある別解と同じ方法によるものだったのだけど、 WA。
理由は左端の処理で、偶数番については、fmin 2 inf とすれば自然と \(d_0 = 0\) と \(d_2\) が比較されるのだが、奇数番は fmin 3 inf では、\(d_1\) と \(d_0\) が比較されないので、これが最小だったケースに WA となっていた。
これに気づかず、テストケースをもってきて判明。いわれてみれば簡単なミス。
その前にも、特別な点（高橋君）の扱いでまちがっていて、 これは入力例に助けられて気づいたりしている。うかつ。
提出例： 12917832
またもや、端の処理が間違っていて WA をなんども出してしまった。 最初を決めるとあとは芋づる式に決まっていくので、 高々４通りを試せばいいという方針はすぐに思いついて、それを実装していったのだが、 自由度がなくなって、OK / NG が決まるのが末尾だけでなく、 末尾から二番目もすでに次が決まっているので自由度はない。
…というのを、ちゃんと考えずに書いてはいけないな。反省： 12923222
必要な受像機の数は、高々３０台なので、３０台の稼働状況をシミュレートした。 各受像機は、何もしていないか、あるチャネルをある時刻まで録画している。 観たい番組を開始時刻でソートしておき、ひとつずつ、なるべく小さい番号の受像機に わりあてる。最後に、最大で何台使うことになったか答えればいい： 12902431
解説では、各時刻における台数を配列でもつやり方があった。 それも思いついたけどメモリと時間がかかりすぎる気がしてやめたんだよなぁ。
おれの、嘘回答なの、もしかして？
Difficult の 10 位で recommend されてたもの (difficulty = 1261)。 普通にとけたけど、結構時間がかかった (43分）： 12821536
奇数個しかないアルファベットの個数に着目して、その個数と同じだけ分割する。 そのとき、残りのアルファベットをいかに均等に振り分けられるかという問題。 そこで、なんか和分割みたいなことをしないといけないのかな、dp かな？ とあらぬ方向に迷い込んでしまった。
もっとシンプルに考えることができて、奇数個だったアルファベットが k 種類だったとすると、 残りの N - k 個のアルファベットで、\(\lfloor \frac{N-k}{2} \rfloor\) 個のペアを 作ることができる。
それらをなるべく均等に k 個の部分文字列に割り振っていくことを考えればいいので、 いちばん小さなものに割り振られるペアの数は \(\lfloor \frac{N-k}{2k} \rfloor\) になる。
したがって、求める答えは、
提出例： 12703595
これが解けなかったのは少し悔しいけど、ここ７回くらい、悲惨なレートだったのに比べれば、やっとマシな感じになったかも（昨日はパフォ400台だったし…）
解説にある通りなのだが、\(j - i = A_i + A_j\) という条件を、 \(A_i + i = j - A_j\) と書き直して、\(X_i = A_i + i\) と \(Y_j = j - A_j\) が等しくなるような (i, j) の個数を求めてやればよい。片方（たとえば \(Y_j\) ）の値と、その値になる index の個数を Map で持てば OK: 12783033
ABC165 は A-B しか解けずに 434 パフォ（茶色の下の方）をとってしまった！やばい。
制約小さめだなぁとは思ったのだけど、全探索が思い浮かばず。 各項 1以上10以下で長さ10の数列を列挙したケース (\(10^{10}\) 通り) が頭をよぎってしまったのだけど、単調増加である場合は、まったくそんなオーダーにならない。
解説にあるとおり、\({}_{(n+m)} \textrm{C}_n\) であり、最大 (n=m=10) でも 184756 通りでしかない： 12654296
解説にあるようなことを復習しておくのはもちろんなんですが、 いくつかの小さなケースの挙動を手元で試して気づくなどできないとなぁ。
（未提出）
EDCBAABCDE のように数字の組をつくる（同じアルファベットの同士をペアに）と、 距離が 1, 3, 5, 7, 9 ... のペアが手にはいるな、というとこまで気づいたのだけど、 2, 4, 6 なども作るにはどうしたらいいんだ？
…ということを、あまり落ち着いて考えられなかった。
解説にあるように、数列を半分にわけて、前半は上述のようにして、 後半ではEDCBAxABCDE のようにとれば、こちらは距離 2, 4, 6, 8, 10 のペアがつくれる。
なるほどっていう。
（未提出）
最小全域木を求める問題なのだが、素朴に考えると経路の数が \(N^2\) になってしまうのと、 距離の扱いがややこしく感じられる。
というわけで、解説を読んだしまったのだが、ポイントは以下：
これらから、点を x 座標でソートした列における隣接する２点をつなぐ辺と、同じように y 座標でソートした列いおける隣接する２点をつなぐ辺のみからなるグラフの最小全域木を求めればよい。こうすることで、辺の本数は \(\textrm O(N)\) まで減るので、 例えばクラスカル法を用いることで \(\textrm O (N \log N)\) 時間で解ける： 12543960
簡単かなと思いながら書いたのに WA が出て悩んでしまった。 違うマークがきたときだけでなく、番号が 2 から 9 のものも捨てるのが漏れてたんだけど。 要反省（このレベルの問題を多く解いた方がいいと思う）： 12489267
各桁の数字が a, b, c, d, e, ... であるような数字を abcde ... と書くとする。
abcdefghij ≡ m,
fghij ≡ m,
であれば、
abcde00000 ≡ 0
となる。(abcdefghij = p*x + m, fghij = p*y + m とおいて引き算すればいい）
かつ、今回の剰余の法である 2019 は 10 と互いに素なので、さらに、
abcde ≡ 0
となる。
したがって、下の桁から桁数を増やしていったときの剰余を計算していって、剰余が同じになる箇所を i, j とすればいいので、その個数をしらべる。なお、０桁のとき、剰余は０とする： 12410747
すべての部分文字列を列挙しなくても、早いものから（頭文字が 'a' のものから） 順番に Set に溜めていって、十分たまったら前から k 番目を出力すればいいなと思い、 それを実装したのだが TLE。 これでは、十分には探索数を減らせなかったよう。
うーん、なんか特別なアルゴリズムが要るのだろうかと解説を見てしまったのだが、 答えの部分文字列の長さは高々 k なので、この長さ以内に限って探索すればよかった： 12236881
abcabcabc ... ab のようにできればいいなと気づいて実装したのですが、WA。 最後は abc, ab, a のいずれかで終わらないといけないという条件にしたのですが、 cbacbacba ... cbac とやってもいいので、条件はもう少し緩かった。 a, b, c は対称であることに気づくべきでした： 12184362
クラスカル法による最小全域木の基本っぽい問題。 ただ、速度制約がやや厳しく、入力列のソートに Seq.unstableSort をつかったのでは 間に合わなかった。お手軽で便利だったのだけど、面倒がらずに Vector の quickSort を使うべきか: 12162471
コストが、辺をつくるだけでなく、ノードに「交易所をつくる」場合の２種類がある。 クラスカル法を改造して、交易所をつくるのと舗装するのとどちらが得か、 なんてことを判断しながら辺をついかし、最後に連結成分に１つずつ交易所をつくればいいかな… などと考えたのだけど、WA だった。
そうではなく、仮想的なノード X を追加し、「あるノード i に交易所をつくる」ことを、 ２点 i-X 間をつなぐ辺で表現してやれば、最小全域木問題に帰着できる： 12168778
有向グラフに関して、ノード１から各ノードまでの距離と、各ノードからノード１までの距離の 両方が必要になる。
Warshall-Floyd でも解けるが、計算量が \(\textrm O(N^3)\) になってしまうので、 TLE やら MLE やら
帰りについては、有向グラフを逆向きにたどると考えると、 こちらも単一始点最短路問題になる。つまり、全経路（Warshall-Floyd）を解く必要はなくて、 ２つの単一始点最短路問題を解けばいい。
…が、Bellman-Ford でやると、やっぱり TLE
Bellman-Ford の計算量は \(\textrm O(|V||E|)\) で、dijkstra の方が速い。 閉路がないことがわかっている場合には、dijkstra で： 12073938
同じく単一始点最短経路問題をとく Bellman-Ford アルゴリズムを用いる問題。 だが、これらは終点もきまっている２頂点間最短経路問題なので、 この２点間にかかわりのない閉路は無視しなければならなかった点に要注意。 一度、これに気づかず WA。
ABC137E の入力例３も見よ。
解けたんだけど、バグって時間がかかってしまった。
等差数列の和、「２分の（項数）×（初項 ＋ 末項）」って覚えているせいで、 (r - l + 1) `div` 2 * (l + r) とかやって答えがあわずに悩んでしまうなど。（切り捨て発生）
項数か（初項＋末項）のどちらかは偶数になるので、 (r - l + 1) * (l + r) `div` 2 のように最後に割れば切り捨て誤差はでない。
最初にたてた方針であっていたのに、書き間違えからはまってしまった： 11995794
ともに、せっかくの計算量減らしが台無しになるのだが、手元では答えを間違うわけではないので気づかず。
「リストが遅いんかなぁ」、「ベクターでもだめか…」と明後日の方向にいってしまった。
反省。
なんてことないプログラムなんだけど、
if elem x "atcoder@" then check xs ys else False
とか書いていたら、hlint に x `elem` "atcoder@" && check xs ys って書けばと教えてもらって、かなりすっきりした。
適当な頂点 r を根とすると、クエリ (a, b) は (r, a), (r, b) と分解できる。 これは、(a, b) の LCA (Lowest Common Ancestor) を p としたとき、 a-p, b-p 間を +1, r-p 間を +2 するので、mod 2 において元のクエリと同一視可能。
なので、クエリ全体は、(r, v) を f(v) 回行うという形に変形できる。 f(v) がいずれも偶数であればよい： 11766336
いいかげん、foldr を覚えたいと思った： 11748054
foldr f v as は、cons を f に、[] を v に置き換えると考えるといいらしい。
1:(2:(3:[])) 1 `f` (2 `f` (3 `f` v)
最初、なにやらヒューリスティックなやり方を思いついて実装したが WA
できあがりは、"..###" とか "....#" とか、境界が１つあって、それより左が '.' で右が '#' のような形。境界が端にあるときには、すべて '.' とか '#' にもなる。
もとの文字列を、その形にもっていくのに必要な変換回数は、境界より左にある '#' と右にある '.' の個数の合計なので、それぞれの個数をインクリメンタルに維持しながら、端から端までチェックして最小値を求めればよかった： 11707189
貪欲法っぽく解いた： 11601629
…が、これは \(\textrm O(1)\) で解けるみたい。解説読んで、考えよう（未）。
解けたけど、もっと簡単になる（大きい方と小さい方で処理をわける必要はなく、後半のやりかただけで全部いけた）： 11592184
最初、桁上がりの方向に列を成長させることを考えて、断念してしまった。
n + 1 桁の LunLun 数は、n桁の LunLun 数の末尾に、一桁付け加えることで作ることができる（付け加える数字の候補は、 元の数の末尾で決まる）。 このことを用いると、n 桁の LunLun 数が小さい順にすべて列挙されていれば、これを用いて、n + 1 桁の LunLun 数も列挙できる： 11593990
今日時点のしんちょく： 400 ACs, 93300 pt, Haskell では 101 ACs
はじめ、なんかいい加減なコードを投稿してしまった。反省。
M の約数のうち、\(\lfloor \frac{M}{N} \rfloor\) を超えないものが答え。 これより大きいものはあり得ないし、これが答えとなるよう数列を具体的に構成できる （N-1 個を D とし、残りを \(A_n\) にすると、これは D の倍数）： 11476026
\(\textrm{Fib}_0 = 1, \textrm{Fib}_1 = 1, \textrm{Fib}_2 = 2, \textrm{Fib}_3 = 3, \cdots\) とすると、
\[ \textrm{gcd}(\textrm{Fib}_k,\ \textrm{Fib}_{k-1})\ =\ \textrm{gcd}( \textrm{Fib}_{k-1},\ \textrm{Fib}_{k-2}) \]
のようになることから、\(\textrm{gcd}(\textrm{Fib}_k,\ \textrm{Fib}_{k-1})\) の計算に必要な回数が K 回となることがわかる。
約数に着目して、\(\textrm O(\sqrt N)\) で解くというのは気づいたのだけど、WA。 もう少し丁寧に考えるべきだった。
\(N = k(M+1)\) の形になることから、M の候補は約数ひく１。 すべてについて判定すればよかった： 11482338
\(N \le 2000\) なので、3重ループで x, y, z の値の決め方すべてを試す時間はないけど、 x, y を決めると z は一位に決まるので、二重ループですべての可能性を列挙可能： 11485843
中心をみつけて真ん中から外側にみていこうとして、なんかバグってたらしく RE。 これはこれで、合わせられるべきかと思うが、外側から見ていけばより簡単に書ける。 以下、解説 PDF より抜粋：
こうして、x を追加した回数が答え： 11452636
大きな n に対する \(2 ^ n \ (\textrm{mod}\ p)\) や、逆元を用いる問題： 11456949
解説 PDF にある通りだけど、以下のように考えることができる：
数列に含まれる数字がすべて偶数だった場合、P == 0 のときの答えは \(2^N\), P == 1 のときは 0
数列に奇数が含まれるとき、その数字１つに着目する。残りの数列に含まれる個数は N - 1 個。 残りの数列から選んだ数字の合計が奇数であれ、偶数であれ、着目した数字を加えるかどうかを適切に選ぶことで、偶数／奇数のいずれもつくることができる。 よって、この場合の答えは P によらず、残りの N-1 個の選び方の個数、つまり \(2^{N-1}\) となる。
投稿したプログラム： 11462263
貪欲でいけるんかなぁ、でも、E 問題だしなぁ。制約（変数の範囲）は…、 というので dp にして回答： 11431501
ニブタンで適当に…とかおもったんだが、N, P ともに最大 \(10^{12}\) という範囲が厄介で悩む。 素因数分解してしまえば、あとは簡単だった： 11406708
Easy さすがに物足りなくて、Recommendations Moderate を、実験 hide にして、 20番目（Moderate のなかでは簡単なの）に取り組みように切り替え。
いまは解き方がわかったあとの実装力を訓練したいというのに、良い感じで合った問題だった。 ただ、今回は、ありものの組み合わせで、Primes を計算したあとに、それを用いて isPrime 判定しているが、Primes の計算過程でできる配列を (filter せずに）そのまま 持ち入ればよかった。この点いまいちでした： 11414269
おとといあたりから、Recommendation (Easy) をやっていってる。 使用言語を Haskell にしてから、実装力とアルゴリズム力の両方が不足しているんですが、 まずは前者を強化するのに、負荷の軽いのをさっさかやろうかと: 11382372
んで、Hlint にこういわれました（↓）。以後きをつけます。
abc058c.hs:44:12: Warning: Use replicate Found: take (hmin' V.! (ord c - ord 'a')) (repeat c) Why not: replicate (hmin' V.! (ord c - ord 'a')) c 1 hint
貪欲。後ろから貪欲にというのはすぐ気づいたのだけど（配列を逆順にしたので処理は前から）、さいしょ、素朴に更新をかけてしまって TLE に。そうか、これだと \(\textrm O(N^2)\) か。というので、やり直して AC： 11359075
それなりに時間を残して書き始めたんだけど、確信もないまま貪欲っぽいのを書いて WA。 解説をみて、「あー、なるほど」となった。これは…。自分で思いつくかなぁ： 11319293
解説PDFより：「元から赤色のリンゴを X 個以上食べることはないので、美味しさの大きい方から X 個以外は捨て ます。元から緑色のリンゴを Y 個以上食べることもないので、美味しさの大きい方から Y 個以外は 捨てます。すると残ったリンゴからどのように X + Y 個のリンゴを選んでも、無色のリンゴを適切 に着色することで赤色のリンゴ X 個と緑色のリンゴ Y 個にすることができます。よって、残ったリ ンゴを美味しさの大きい方から X + Y 個食べれば良いです。」
昨日、蟻本の「しゃくとり法」のところ読んだし、やってみようと思って。 たかがしゃくとり法と思っていたけど、けっこうてこずってしまった*1。
しゃくとり法の実装上の注意点として、「左端が右端を追い抜かさないように」というのが、解説にも書いてあるのだけど、solve 関数を書いていて、\(k == 0\) のときにこれの扱いが面倒だなと気づいて、ゼロのケースは solve の外で処理するようにした。
結果、それなりに簡潔には書けたとは思うが、書くのに時間がかかった： 11190145
Difficulty = 1186
貪欲に。みたまま解いたけど、一回 TLE 踏んでしまった： 10930676
昨日の パナソニックプログラミングコンテスト2020 は惨敗。40 もレートが下がってしまった。
というわけで復習。
盤の幅（または高さ）が 1 だと角行は動けない： 10919896
いくつも反省点あるけど、メジャーなものは、
かな。文字列を後ろに伸ばしていくので、また Data.Sequence をつかった： 10920257
Difficulty = 1221
これも、解説 PDF みてもピンとこず、動画みた。 操作に気を取られず、\(M = \pm a_1 \pm a_2 \cdots \pm a_n\) の形になることに着目、 あとは…（解説動画をみよう！）
実装には、また、Data.Sequence をつかった。\(\textrm O(n \log n)\) の sort （unstableSort の方が速い）もあるし、便利だ： 10769906
Difficulty = 1236
解説 PDF 読んでもいまいちピンとこなかったのだけど、解説動画みたら、 PDF に書いてある通りだという…。 辺に書かれる数字がある数以上であることを保証しながら木を成長させていくには、 どうすればいいか？と考えると、求める muximum 値と構成方法の両方がわかる。
BFS *1 の queue を List で実装して、TLE をくらった。 Haskell ではキューがほしくなったら Data.Sequence を使えということになっているらしい。両端キューとして使える。 つかった: 10750861
剰余、素数の性質、など。 解説みないと解けなかった。みても、いくつか躓いたり。: 10728035
貪欲法、difficulty = 1128 : 10519601
とちゅう、d の計算（let d = max (ai_1 + ai - x) 0 ) で、 d の下限が ０ になるように…というので、下限のイメージでつい min と書いてしまってバグるなど。ああ、頭が腐ってしまったのかと思った。
まぁ、ふつうに、びっとで。 IOUArray や UArray をつかった。型注釈ないとコンパイル通らない…んですよねえ： 10504123
現在のすうじ：
AtCoder:
AtCoder Problems:
dp かなぁ、状態数爆発しちゃうなぁと少し悩んで。 貪欲にいけばいいんじゃないのと書いてみたら通った： 9668798
解説をみると、それすら必要なくて所謂 \(\textrm O(1)\) 解法がある問題だったもよう。 そういう勘もつけたい。
Int ではなく、Integer をつかうとすっきりサクっと解けた。 これを期に、getIntegerVec も用意しておくことにしよう： 9643004
コンテスト当日に書いたもの（9628302, 380ms）より、上記の版の方が 1.8 倍ほど速い（208ms）点も要注意かも。正格版 foldl' を用いたことと、多相の sum ではなく、ベクタ専用の VB.sum を用いたところが違う。
see also: foldlを直す
「区間スケジューリング問題」（蟻本 p.43）そのもの。 終了時間の早いものからとっていく（貪欲法）。 状態としては、選んだ個数と、すでに選んだ仕事の終了時刻だけを持てばよい： 9643837
Rolling Hash と二分探索でとくやりかたを書いてみたのだけど、どうにも TLE から脱出できない： 9534064
この解き方にこだわるわけではないが、同様の方法での C#版 にくらべてはっきり遅い理由は理解したい…が、てこずりそう。
いろいろ調べるなかで、今日わかったこと：
or $ map (<5) [0..] は一瞬で停止するが、V.or $ V.generate 100000000 (<5) は終わらない（V は Data.Vector.Unboxed）。 それもあって、明に停止するように or $ generate に相当するような再帰関数 check' を書いてみたのだが、 どうも、そういう問題ではなかった。