# AtCoder 練習帳３： 2020 年 1 月～

使用言語を Haskell に変えてみました！

## 2020-12-31
### ARC050B - 花束

[復習ず](excercise202012) のしょっぱな。

基本的な考え方 (まずどちらも１本ずつ必要で、そのあと (x-1), (y-1) でわる)は OK
だったものの、負になってないかのチェックをおこたって [WA](https://atcoder.jp/contests/arc050/submissions/19073578) 

また、bisectRight は、条件を満たすもののうち最も右にあるものの「さらに１つ先」のインデックスだぞ！

### Codefestival 2015 qual A D - 壊れた電車

方針はすぐに立ったものの、入力例２があわず。
左に行ってから折り返すのと、右にいってから折り返すのとで良い方をとらなければいけないことを見落としていた（この投稿例でいうと r1 の方のみ考えてしまった）：
[19082735](https://atcoder.jp/contests/code-festival-2015-quala/submissions/19082735)

## 2020-12-30
### ARC110C - Exoswap ★★

★★実装力的な意味で要復習

何日か前に自力ではとけなくて解説を読んだので、今日はそれを実装してみた。
…が、TLE と WA がとれず。

- ちょうど N-1 回の操作が必要なので、はじめから正位置にある数字も NG
- 数字を都度サーチしていては時間がかかりすぎるので、逆写像を準備する
- 答えの列を蓄積するのに、後ろへの連結が速い Data.Sequence を使う

これくらいが要注意点だったかな：
[19058216](https://atcoder.jp/contests/arc110/submissions/19058216)

### ABC154E - Almost Everywhere Zero ★桁dp

桁 dp, 要復習：
[19063138](https://atcoder.jp/contests/abc154/submissions/19063138)

メモ： 最初、k （二番目の添え字）に関するループ範囲を、最初 [0..(k-1)] としてしまったために答えがあわず、原因になかなか気づけなかった。

## 2020-12-29
### ABC006C - スフィンクスのなぞなぞ ★

３変数だけど、ひとつ固定すると「つるかめ算」になるので O(1) で解けるので、
全体で O(N) となり、たぶん、これだけでも解けた。

さらに、老人２人を大人１人と赤ちゃん１人に交換可能なので、老人の数は０と１のみ試せばよく、全体でも O(1) となる。

ここ、早とちりして、大人２人を赤ちゃん１人にも交換可能じゃないかとおもってしまったが、
それだと総人数がかわってしまうので、交換可能じゃない。

[19045645](https://atcoder.jp/contests/abc006/submissions/19045645)

### ABC031C - 数列ゲーム

ぜんぜんなんてことないのだが、WA がなかなかとれず。
最大値をもとめるのに、初期値 (solve 関数に最初にあたえる res) を 0 としてしまって、
答えが負のケースに間違えるというポカだった。注意しよう。

### APC001B - Two Arrays ★

これ、解説読んでもよくわかんなかったやつ。

解説とは少し違うのだけど、次のように考えるのがわかりやすいように思う：

- \(a_i \lt b_i\) はいくつあっても大丈夫（\(a_i\) に 2 を足し、\(b_i\) に 1 を足す操作を好きなだけ繰り返せばよい。
- \(a_i \gt b_i\) の組があった場合、\(a_j\ (j \ne i) \) に 2 を足しつつ、\(b_i\) に 1 加えなければならない

なので、後者を行うのに十分なだけ、\(a_j\) に 2 を足す余地があるかどうかを調べればよい：
[19046757](https://atcoder.jp/contests/apc001/submissions/19046757)

## 2020-12-28
### ARC034B - 方程式 ★

要反省。

なんか、よさそうな方法を思いついたものの、あり得る解をすべて列挙できずに WA。
解説になるとおりなのだが、\(f(x)\) は高々 9*17 = 153 にしかならないので、
x の取り得る範囲は十分にせまく、全探索が可能だった：
[19018899](https://atcoder.jp/contests/arc034/submissions/19018899)



## 2020-12-26
### AGC049B - Flip Digits

[けんちょんさんの](https://drken1215.hatenablog.com/entry/2020/11/15/051800)
と似たやり方でやろうとして、WA だった。
まず不要な 1 を対消滅させてから残りを処理しようとしたのが最適でなかったのに気づいたところでこの方針をあきらめてしまったのだが、この方針でもちゃんとやれば通せたのか：
[18995525](https://atcoder.jp/contests/agc049/submissions/18995525)

解説にあるやり方はまだ。


### ABC132D - Blue and Red Balls 

いちおう自力で AC だが、ごちゃごちゃしている。
もっかいやっておきたい:
[18999918](https://atcoder.jp/contests/abc132/submissions/18999918)



## 2020-12-25

緑のうち、推定難易度が experimental でないものが６つ、このページで★をつけたものが４つ。合計１０問は、ちょっとしっかり復習しようかな。

### ARC032B - 道路工事
最初、連結成分の数を数えるのに、$<verb>{nub <$> mapM (findUF uf) [0..(n-1)]}
とかやって TLE をだしてしまった。解説にあるように、root が自分自身になるようなノードの数を数えればよい（その方がずっと速い）。

## 2020-12-20
### [dp] Codefestival 2014 final E - 常ならずグラフ ★

dp かなと思ったけど書けなかった。貪欲っぽくやっても解けるようだが、
dp できちんとかけるようになっておきたい。要復習。

[解説資料](https://www.slideshare.net/chokudai/codefestival2014final)

## 2020-12-07
### ABC088D - Grid Grid Repainting

ごく単純な BFS なのにハマった回。

TLE がでてしまい、ずいぶん悩んだ。いろいろ遠回りしたんだけど、
TLE の原因は、探索において、つぎの升に到達したときの距離を $<verb>{ct}, すでにその升に書かれている距離を $<verb>{t} としたときの
$<verb>{t < ct} か $<verb>{t <= ct} の違いだった。はじめその升を重複して訪れないための条件を前者で書いていたので、
なんどもなんども同じ升をめぐることになってしまって探索回数が伸びていた。

Queue にいれる前に判定しないといけないのかとおもって、書き換えたりしたけど、
それは関係なかったので、当初の書き方でももちろん通った：
[18626717](https://atcoder.jp/contests/abc088/submissions/18626717)

## 2020-11-29
### ARC109C - Large RPS Tournament

トーナメント方式で、k 回試合をすると（グラフの深さが k）勝者がきまる。
なので、k 回文字列を更新して、最初の文字を取り出せばよい。
また、文字列は常に長さ N あればいいので（index は i mod N なので）、
長さ N の文字列を k 回更新すればいい。計算量は \(\textrm O(KN)\)

提出例：[18480027](https://atcoder.jp/contests/arc109/submissions/18480027)

## 2020-11-25
### [dp] ABC184D - increment of coins ★

典型的な確率 dp だった模様。[解説動画](https://www.youtube.com/watch?v=iWS5WCvMMak&t=3195s) をみて、最後の＋１が直感的にわかりづらいなぁなどと思って、少し考え込むなど。要復習

$$<pre>{
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] から１手の距離になるので、それを素直に書くと下のようになる。上の式は、それと等価なのね。

$$<pre>{
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)
$$}

[解説文](https://atcoder.jp/contests/abc184/editorial/152) には、こちらの式が書いてある。

i, j, k いずれかが100のときには、すでにゴールしているので、ゴールまでの期待手数は 0。
あとは、i, j, k が大きいものから順にうめていって（３重ループ）、最後に dp[i][j][k] を表示するか、メモ化再帰にするか、どちらでも解ける。

提出例：

- [３重ループ](https://atcoder.jp/contests/abc184/submissions/18397127)
- [メモ化再帰](https://atcoder.jp/contests/abc184/submissions/18397273)

### キーエンス 2019 B - Keyence String

茶色埋めの一環。

はじめ書いたプログラムは [WA](https://atcoder.jp/contests/keyence2019/submissions/18398442) だった。
なぜかわからず、テストケースを見る。ひとつみたらわかった。

$$<pre>{
keyencbbzsqzezyvefbhtwriljcvrymirjmbljehlslmrxslnspsiujxiznmlyfcpe
$$}

で、書き直して提出、[AC](https://atcoder.jp/contests/keyence2019/submissions/18398592)

### ABC103C - Module Summation

答えはそうかなと思ったのですが、ほんとにそうなのか不安になってしまった。
\(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)\) が答え。

## 2020-11-19
### 天下一プログラマーコンテスト2012 予選A B - 分類たん

別に難しいわけではないのだけど、$<verb>{ByteString.intercalate}
なる関数を初めてつかった：
[18221180](https://atcoder.jp/contests/tenka1-2012-qualA/submissions/18221180)

intercalate （挿入する）という英単語もしらなかった。

## 2020-11-15
### [imos] ABC183D - Water Heater ★

問題みて、「座標圧縮がつかえるのでは」と思って書き始めてしまい、
当然 TLE になったのだが軌道修正できずに落としてしまった。

S, T にくらべて、N がはっきりちいさいわけではないので、座標圧縮は効果がない。

累積和、[imos 法](https://imoz.jp/algorithms/imos_method.html)を復習しておこう：
[18154200](https://atcoder.jp/contests/abc183/submissions/18154200)

## 2020-11-10
### ABC028D - 乱数生成

順列で考えると、全集合は N^3 個。

N 以下の数のうち、K より小さいものを A, K より大きいものを B とすると、

- (A, K, B) のパターン： (K-1) * (N - K) * 6 通り
- (A, K, K) のパターン： (K-1) * 3 通り
- (K, K, B) のパターン： (N-K) * 3 通り
- (K, K, K) のパターン：１通り

最初、リストの一番上のケースのみしか考えてなくて、入力例１で気づいた orz.

## 2020-11-09
### CODE FESTIVAL 2015 あさぷろ Middle A - ヘイホー君と最終試験

簡単だなぁと思いつつ、WA をだしてしまう。
K-1個の和がすでに十分なケース (コード中では $<verb>{t = r*k - sum0} が負になるケース）の考慮が漏れていて、k < n のときには結果的に拾われていたが、k == n のときに条件がもれて WA

引き算の結果が０以上になるとは自動的には保証されないことを気を付けるとか、
いくらか避ける方法はあったはず、かな。

提出例：
[18008350](https://atcoder.jp/contests/code-festival-2015-morning-middle/submissions/18008350)

## 2020-10-24
### ARC050B - 花束

ニブタンだと思ってとりかかったのに、めちゃめちゃ何度も間違えてしまった。
まず、判定方法をさくっと思いつけず。反省を込めて、以下解説文の説明とほぼ同じですが、書いておく：

K個の花束が作れるかという判定問題を考える。
花束をつくるためには、まず、赤い花と青い花が少なくとも 1 本ずつ必要なので、
赤い花と青い花を K 本ずつ減らす。赤い花束をつくるには、さらに赤い花が x-1 本必要なので、
赤い花束は $<verb>{(r-k) `div` (x-1)} 本つくることができる。
どうように、青い花束は $<verb>{(b-k) `div` (y-1)} 本つくることができる。よって、
$<verb>{((r-k) `div` (x-1) + (b-k) `div` (y-1)) >= k} かどうかを判定すればよい。

また、bisectRight の使い方を間違えたり（False < True であることに気を付けて使う必要がある）したのだが、二分探索くらいは、その場で書いた方がいいのかもしれない。

また、このくらいの難易度の問題では、run スクリプト（自作のチェックスクリプト）を使った方がよさそう。

実装例：[17606716](https://atcoder.jp/contests/arc050/submissions/17606716)

## ARC105A

解けたけど、B を決めたらAが決まる的に、B についてでの全探索にして、なんどかWA。
解説にあるとおり、A、B どちらも範囲がせまいので、両方について単純に全探索でよかった。
（このあたりのあたりをきちんとつけよう）

## ARC106C

１時間以上つかえたのに、WA をひとつ残してしまって通せなかった。

m >= n - 1 のときには -1 を出力すればいいのだが、n = 1, m = 0 のときが
この判定に引っかかってアウトだった。 m = 0 のときは n にかかわらず Ok だという
ある意味コーナーケースにひっかかった。

反省点は以下：

- 区間スケジューリング問題の確認。高橋君版が最適であることを確信をもって進められたらよかった。
- コーナーケースを丁寧にみる

また、Haskell で TLE になったので C++ に乗り換えたりしてしまったのだけど、
Haskell での TLE は、ループ条件がまずかったため、初めから i < 0 だったときに無限ループしていたのだった。TLE だからといって Haskell が遅いせいにしてはいけない。



## 2020-09-16
### 東京海上日動プログラミングコンテスト 2020 C - Lamps
ポイントが２つあった。ひとつは、１回のシミュレーションを累積和をもちいて
\(O(N)\) で処理すること。もうひとつは、それでも K 回やると \(O(KN)\) 
になるのをどうするか。

シミュレーションしないで済む方法があるのかなと思ったら、そうではなくて、
操作を一定回数以上行うと、すべての電球の明るさが N の状態に収束するので、
それ以上シミュレーションする必要がなくなる。

「シミュレーションしないで済む方法がある」以外の出口を思いつかなかったので、
こういう考え方もあるのか、と。

回答例：
[16789119](https://atcoder.jp/contests/tokiomarine2020/submissions/16789119)


## 2020-08-22
### ABC176D - Wizard in Maze

なんども submit したけど、TLE がとれず。最後 TLE いっこで結局通せなかった。

はじめ DFS で TLE になり、プレーンな BSF に変更。
近場から埋めることになるのでいいかなと思ったのだが、これでもまだ TLE。
歩いていけるコストの増えない移動と、ワープ先をまぜこぜにするのがいけないのかと
queue を毎回ソートするようにして、当然だめで、ならばと Priority Queue に任せてみたが、そこでタイムアウトでした。TLE がひとつ残っていた：
[16151035](https://atcoder.jp/contests/abc176/submissions/16151035)

行先は、いまいる場所と同じコストのものと、＋１のものの二種なので、
PriorityQueue などつかわなくても、dequeue で前者をあたまに、後者をおしりにくっつければよかった：
[16152946](https://atcoder.jp/contests/abc176/submissions/16152946)


## 2020-08-17
### ABC094D - Binomial Coefficients

\({}_n C_r\) が最大になるのは、\(\{A_i\}\) のなかから最大のものを n に、
nの半分にもっとも近いものを r に選んだ場合。
切り捨てで失敗したくなかったので、距離に Double を使ったけど、r の二倍が n により近いことを条件にすれば整数でいけたかな：
[16008154](https://atcoder.jp/contests/abc094/submissions/16008154)


## 2020-07-07
たなばた。なんかひさびさだ。すこしずつでも緑を。

### ABC148E - Double Factorial
今日はみてすぐこの回答を思いついたけど、以前わかんなくて解説みたやつかもしんない：
[15063034](https://atcoder.jp/contests/abc148/submissions/15063034)



## 2020-05-12
### Code festival 2017 qualA B - Flip
なんてことない全探索なのだが、[WA](https://atcoder.jp/contests/code-festival-2017-quala/submissions/13155514) をだした。
升目を探索するときの座標を y, x の順で書くことが多かったのだけど、
今回 solve x y と書いてしまって、かつ、関数の中では solve y x の順で呼び出してしまっていた。悪いことに、入力例に対しては顕在化せず。
それを直せば普通に AC:
[13155838](https://atcoder.jp/contests/code-festival-2017-quala/submissions/13155838)

## 2020-05-11
今週は、すこし真面目に C/D あたりをこなす。また、もういちどやった方がいいものに、
「（要復習★）」マークをつけてみよう。

### ABC110C - String Transformation (要復習★）

簡単に考えて、いい加減なプログラムを書いてしまった。

S から T への一対一対応表をつくればいいのだが、それには、Si -> Ti のマップと、
Ti -> Si のマップの両方を使う。というのも、一対一対応であるというのは、

- Si == Sj なら Ti == Tj かつ
- Si /= Sj なら Ti /= Tj

なのだが、後者は対偶をとって 「Ti == Tj ならば Si == Sj」と言い換えられる：
[13116832](https://atcoder.jp/contests/abc110/submissions/13116832)

## 2020-05-10
### 住友信託銀行プログラミングコンテスト 2019 E - Colorful Hats2

わからず解説をみてしまった。最初の i 人のなかで、同じ色の帽子をかぶっている人の
数を \(x_i\), \(y_i\), \(z_i\) とする。また、i 番目の人がかぶることのできる帽子の
かぶり方を \(T_i\) 通りとする。

$$<table>{ cccccccc
\hline
i & i=0 & i=1 & i=2 & i=3 & i=4 & i=5 & i=6 \\
\hline
\hline
\(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 \\
\hline
:caption 解説より具体例 (N=6 のケース）
$$}

次にかぶれる帽子は、\(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](https://atcoder.jp/contests/sumitrust2019/submissions/13015966)


### ABC167

簡単に反省点をメモ。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ほど足りないんだよな。

## 2020-05-09
### AGC023B - Find Symmetries

もしかして愚直にやんのかなといぶかしみつつ、
(A, B) の組み合わせが good なら (B, A) でも good なのでという程度の減らし方で
やってみたけど、当然 TLE。

![fig](figagc023b.png)

これでは、半分にしかならないのだけど、
解説にもあるとおり (A, B) が good なら (A+1, B+1) も good （上図も参照）なので、
(0,0) から (0, N-1) の範囲でしらべて、good だったものの個数を N 倍すればいい：
[12988326](https://atcoder.jp/contests/agc023/submissions/12988326)

## 2020-05-07
### Code Festival 2017 Final C - Time Gap
自力で書いたやつは、解説にある別解と同じ方法によるものだったのだけど、
[WA](https://atcoder.jp/contests/cf17-final/submissions/12917457)。

理由は左端の処理で、偶数番については、fmin 2 inf とすれば自然と \(d_0 = 0\) 
と \(d_2\) が比較されるのだが、奇数番は fmin 3 inf では、\(d_1\) と \(d_0\) 
が比較されないので、これが最小だったケースに WA となっていた。

これに気づかず、テストケースをもってきて判明。いわれてみれば簡単なミス。

その前にも、特別な点（高橋君）の扱いでまちがっていて、
これは入力例に助けられて気づいたりしている。うかつ。

提出例：
[12917832](https://atcoder.jp/contests/cf17-final/submissions/12917832)

### ARC069D - Menagerie 

またもや、端の処理が間違っていて WA をなんども出してしまった。
最初を決めるとあとは芋づる式に決まっていくので、
高々４通りを試せばいいという方針はすぐに思いついて、それを実装していったのだが、
自由度がなくなって、OK / NG が決まるのが末尾だけでなく、
末尾から二番目もすでに次が決まっているので自由度はない。

…というのを、ちゃんと考えずに書いてはいけないな。反省：
[12923222](https://atcoder.jp/contests/arc069/submissions/12923222)

## 2020-05-06
### ABC080D - Recording

必要な受像機の数は、高々３０台なので、３０台の稼働状況をシミュレートした。
各受像機は、何もしていないか、あるチャネルをある時刻まで録画している。
観たい番組を開始時刻でソートしておき、ひとつずつ、なるべく小さい番号の受像機に
わりあてる。最後に、最大で何台使うことになったか答えればいい：
[12902431](https://atcoder.jp/contests/abc080/submissions/12902431)

解説では、各時刻における台数を配列でもつやり方があった。
それも思いついたけどメモリと時間がかかりすぎる気がしてやめたんだよなぁ。

おれの、嘘回答なの、もしかして？

## 2020-05-04
### Aising 2019 C - Alternating Path
Difficult の 10 位で recommend されてたもの (difficulty = 1261)。
普通にとけたけど、結構時間がかかった (43分）：
[12821536](https://atcoder.jp/contests/aising2019/submissions/12821536)



## 2020-05-03
### ARC053B - 回文分割
奇数個しかないアルファベットの個数に着目して、その個数と同じだけ分割する。
そのとき、残りのアルファベットをいかに均等に振り分けられるかという問題。
そこで、なんか和分割みたいなことをしないといけないのかな、dp かな？
とあらぬ方向に迷い込んでしまった。

もっとシンプルに考えることができて、奇数個だったアルファベットが k 種類だったとすると、
残りの N - k 個のアルファベットで、\(\lfloor \frac{N-k}{2} \rfloor\) 個のペアを
作ることができる。

それらをなるべく均等に k 個の部分文字列に割り振っていくことを考えればいいので、
いちばん小さなものに割り振られるペアの数は \(\lfloor \frac{N-k}{2k} \rfloor\) になる。

したがって、求める答えは、

- N (k == 0 の場合）
- \(2 \ \lfloor \frac{N-k}{2k} \rfloor \ + \ 1\) 

提出例： [12703595](https://atcoder.jp/contests/arc053/submissions/12703595)

### ABC166E - This Message Will Self-Destruct in 5s

これが解けなかったのは少し悔しいけど、ここ７回くらい、悲惨なレートだったのに比べれば、やっとマシな感じになったかも（昨日はパフォ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](https://atcoder.jp/contests/abc166/submissions/12783033)

## 2020-05-02

ABC165 は A-B しか解けずに 434 パフォ（茶色の下の方）をとってしまった！やばい。

### ABC165C - Many Requirements

制約小さめだなぁとは思ったのだけど、全探索が思い浮かばず。
各項 1以上10以下で長さ10の数列を列挙したケース (\(10^{10}\) 通り) 
が頭をよぎってしまったのだけど、単調増加である場合は、まったくそんなオーダーにならない。

解説にあるとおり、\({}_{(n+m)} \textrm{C}_n\) であり、最大 (n=m=10) でも 184756
通りでしかない：
[12654296](https://atcoder.jp/contests/abc165/submissions/12654296)

### ABC165D - Floor Function

解説にあるようなことを復習しておくのはもちろんなんですが、
いくつかの小さなケースの挙動を手元で試して気づくなどできないとなぁ。

（未提出）

### ABC165E - Rotation Matcing

EDCBAABCDE のように数字の組をつくる（同じアルファベットの同士をペアに）と、
距離が 1, 3, 5, 7, 9 ... のペアが手にはいるな、というとこまで気づいたのだけど、
2, 4, 6 なども作るにはどうしたらいいんだ？

…ということを、あまり落ち着いて考えられなかった。

解説にあるように、数列を半分にわけて、前半は上述のようにして、
後半ではEDCBAxABCDE のようにとれば、こちらは距離 2, 4, 6, 8, 10 のペアがつくれる。

なるほどっていう。

（未提出）

## 2020-05-01
### ARC076D - Built?
最小全域木を求める問題なのだが、素朴に考えると経路の数が \(N^2\) になってしまうのと、
距離の扱いがややこしく感じられる。

というわけで、解説を読んだしまったのだが、ポイントは以下：

- 最小全域木を考えるにあたっては、距離が min(|a - c|, |b -d|) というのは、距離 |a - c| の経路と、距離 |b - d| の経路の２つが存在すると考えて差し支えない
- たとえば x 座標でソートして、i < j < k とならぶような３つのノードがあった場合、経路 i → k をつなぐコストと比較して、経路 i → j と経路 j → k の両方をつなぐコストは大きくならない。よって、i → k を直接つなぐケースは考える必要がない

これらから、点を x 座標でソートした列における隣接する２点をつなぐ辺と、同じように y 座標でソートした列いおける隣接する２点をつなぐ辺のみからなるグラフの最小全域木を求めればよい。こうすることで、辺の本数は \(\textrm O(N)\) まで減るので、
例えばクラスカル法を用いることで \(\textrm O (N \log N)\) 時間で解ける：
[12543960](https://atcoder.jp/contests/arc076/submissions/12543960)


## 2020-04-29
### 天下一プログラマーコンテスト 2012 予選C B - ロイヤルストレートフラッシュ

簡単かなと思いながら書いたのに WA が出て悩んでしまった。
違うマークがきたときだけでなく、番号が 2 から 9 のものも捨てるのが漏れてたんだけど。
要反省（このレベルの問題を多く解いた方がいいと思う）：
[12489267](https://atcoder.jp/contests/tenka1-2012-qualC/submissions/12489267)

## 2020-04-27
### ABC164D - Multiple of 2019

各桁の数字が a, b, c, d, e, ... であるような数字を abcde ... と書くとする。

$$<pre>{
abcdefghij ≡ m,
     fghij ≡ m,
$$}

であれば、

$$<pre>{
abcde00000 ≡ 0
$$}

となる。(abcdefghij = p*x + m, fghij = p*y + m とおいて引き算すればいい）

かつ、今回の剰余の法である 2019 は 10 と互いに素なので、さらに、

$$<pre>{
abcde ≡ 0
$$}

となる。

したがって、下の桁から桁数を増やしていったときの剰余を計算していって、剰余が同じになる箇所を i, j とすればいいので、その個数をしらべる。なお、０桁のとき、剰余は０とする：
[12410747](https://atcoder.jp/contests/abc164/submissions/12410747)





## 2020-04-23
### ARC097C - K-th Subtring

すべての部分文字列を列挙しなくても、早いものから（頭文字が 'a' のものから）
順番に Set に溜めていって、十分たまったら前から k 番目を出力すればいいなと思い、
それを実装したのだが
[TLE](https://atcoder.jp/contests/arc097/submissions/12236682)。
これでは、十分には探索数を減らせなかったよう。

うーん、なんか特別なアルゴリズムが要るのだろうかと解説を見てしまったのだが、
答えの部分文字列の長さは高々 k なので、この長さ以内に限って探索すればよかった：
[12236881](https://atcoder.jp/contests/arc097/submissions/12236881)


## 2020-04-21
### CODE FESTIVAL 2017 Final B - Palindrome-phobia

abcabcabc ... ab のようにできればいいなと気づいて実装したのですが、WA。
最後は abc, ab, a のいずれかで終わらないといけないという条件にしたのですが、
cbacbacba ... cbac とやってもいいので、条件はもう少し緩かった。
a, b, c は対称であることに気づくべきでした：
[12184362](https://atcoder.jp/contests/cf17-final/submissions/12184362)

## 2020-04-20
### いろはちゃんコンテスト Day2 - D 楽しすぎる家庭菜園  [最小全域木]

クラスカル法による最小全域木の基本っぽい問題。
ただ、速度制約がやや厳しく、入力列のソートに Seq.unstableSort をつかったのでは
間に合わなかった。お手軽で便利だったのだけど、面倒がらずに Vector の quickSort を使うべきか:
[12162471](https://atcoder.jp/contests/iroha2019-day2/submissions/12162471)

### ARC029C - 高橋君と国家 [グラフ、最小全域木の応用]

コストが、辺をつくるだけでなく、ノードに「交易所をつくる」場合の２種類がある。
クラスカル法を改造して、交易所をつくるのと舗装するのとどちらが得か、
なんてことを判断しながら辺をついかし、最後に連結成分に１つずつ交易所をつくればいいかな…
などと考えたのだけど、WA だった。

そうではなく、仮想的なノード X を追加し、「あるノード i に交易所をつくる」ことを、
２点 i-X 間をつなぐ辺で表現してやれば、最小全域木問題に帰着できる：
[12168778](https://arc029.contest.atcoder.jp/submissions/12168778)

## 2020-04-19
### ABC035D - トレジャーハント [単一始点最短経路問題、Dijkstra 法]

有向グラフに関して、ノード１から各ノードまでの距離と、各ノードからノード１までの距離の
両方が必要になる。

Warshall-Floyd でも解けるが、計算量が \(\textrm O(N^3)\) になってしまうので、
[TLE やら MLE やら](https://abc035.contest.atcoder.jp/submissions/12067157) 

帰りについては、有向グラフを逆向きにたどると考えると、
こちらも単一始点最短路問題になる。つまり、全経路（Warshall-Floyd）を解く必要はなくて、
２つの単一始点最短路問題を解けばいい。

…が、Bellman-Ford でやると、やっぱり 
[TLE](https://abc035.contest.atcoder.jp/submissions/12068155)

Bellman-Ford の計算量は \(\textrm O(|V||E|)\) で、dijkstra の方が速い。
閉路がないことがわかっている場合には、dijkstra で：
[12073938](https://abc035.contest.atcoder.jp/submissions/12073938)

### ABC061D - Score Attack, ABC137E - Coins Respawn [２頂点間最短経路問題、Bellman-Ford 法]

同じく単一始点最短経路問題をとく Bellman-Ford アルゴリズムを用いる問題。
だが、これらは終点もきまっている２頂点間最短経路問題なので、
この２点間にかかわりのない閉路は無視しなければならなかった点に要注意。
一度、これに気づかず
[WA](https://abc061.contest.atcoder.jp/submissions/12075753)。

[ABC137E](https://atcoder.jp/contests/abc137/tasks/abc137_e) の入力例３も見よ。

- [ABC061D - Score Attack](https://abc061.contest.atcoder.jp/submissions/12077234)
- [ABC137E -  Coins Respawn](https://atcoder.jp/contests/abc137/submissions/12077070)

### ABC163D 

解けたんだけど、バグって時間がかかってしまった。

等差数列の和、「２分の（項数）×（初項　＋　末項）」って覚えているせいで、
$<verb>{(r - l + 1) `div` 2 * (l + r)} とかやって答えがあわずに悩んでしまうなど。（切り捨て発生）

項数か（初項＋末項）のどちらかは偶数になるので、
$<verb>{(r - l + 1) * (l + r) `div` 2 } のように最後に割れば切り捨て誤差はでない。


## 2020-04-17
### ABC133C - Remainder Minimization 2019
最初にたてた方針であっていたのに、書き間違えからはまってしまった：
[11995794](https://atcoder.jp/contests/abc133/submissions/11995794)

- 書き間違え１： 右端は $<verb>{r'= min (l + 2020) r} が正しいのに $<verb>{r'= min (r + 2020) r} と書いてしまう
- 書き間違え２： $<verb>{r'} を用いるべきところで $<verb>{r} を使ってしまう

ともに、せっかくの計算量減らしが台無しになるのだが、手元では答えを間違うわけではないので気づかず。

「リストが遅いんかなぁ」、「ベクターでもだめか…」と明後日の方向にいってしまった。

反省。

## 2020-04-12
### ABC003B - AtCoder トランプ
なんてことないプログラムなんだけど、

$$<pre>{
 if elem x "atcoder@" 
 then check xs ys
 else False
$$}

とか書いていたら、hlint に $<verb>{x `elem` "atcoder@" && check xs ys} って書けばと教えてもらって、かなりすっきりした。

### AGC014B - Unplanned Queries [グラフ、LCM]

適当な頂点 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](https://atcoder.jp/contests/agc014/submissions/11766336)


## 2020-04-11
### 第２回ドワンゴからの挑戦状予選 B - 積み鉛筆
いいかげん、foldr を覚えたいと思った：
[11748054](https://atcoder.jp/contests/dwango2016-prelims/submissions/11748054)

foldr f v as は、cons を f に、[] を v に置き換えると考えるといいらしい。

$$<pre>{
1:(2:(3:[]))
1 `f` (2 `f` (3 `f` v)
$$}


## 2020-04-10
### Tenka1 2019 C - Stones

最初、なにやらヒューリスティックなやり方を思いついて実装したが
[WA](https://atcoder.jp/contests/tenka1-2019-beginner/submissions/11707042)

できあがりは、"..###" とか "....#" とか、境界が１つあって、それより左が '.' で右が '#'
のような形。境界が端にあるときには、すべて '.' とか '#' にもなる。

もとの文字列を、その形にもっていくのに必要な変換回数は、境界より左にある '#' と右にある
'.' の個数の合計なので、それぞれの個数をインクリメンタルに維持しながら、端から端までチェックして最小値を求めればよかった：
[11707189](https://atcoder.jp/contests/tenka1-2019-beginner/submissions/11707189)


## 2020-04-06
### CODE FESTIVAL 2016 予選C B - K 個のケーキ
貪欲法っぽく解いた：
[11601629](https://atcoder.jp/contests/code-festival-2016-qualc/submissions/11601629)

…が、これは \(\textrm O(1)\) で解けるみたい。解説読んで、考えよう（未）。

## 2020-04-05
### AGC011B - Colorful Creatures
解けたけど、もっと簡単になる（大きい方と小さい方で処理をわける必要はなく、後半のやりかただけで全部いけた）：
[11592184](https://atcoder.jp/contests/agc011/submissions/11592184)

### ABC161D - Lunlun Number [列挙]
最初、桁上がりの方向に列を成長させることを考えて、断念してしまった。

n + 1 桁の LunLun 数は、n桁の LunLun 数の末尾に、一桁付け加えることで作ることができる（付け加える数字の候補は、
元の数の末尾で決まる）。
このことを用いると、n 桁の LunLun 数が小さい順にすべて列挙されていれば、これを用いて、n + 1 桁の LunLun 数も列挙できる：
[11593990](https://atcoder.jp/contests/abc161/submissions/11593990)

## 2020-04-04

今日時点のしんちょく： 400 ACs, 93300 pt, Haskell では 101 ACs

### ABC112D - Partition [約数]
はじめ、なんかいい加減なコードを投稿してしまった。反省。

M の約数のうち、\(\lfloor \frac{M}{N} \rfloor\) を超えないものが答え。
これより大きいものはあり得ないし、これが答えとなるよう数列を具体的に構成できる
（N-1 個を D とし、残りを \(A_n\) にすると、これは D の倍数）：
[11476026](https://atcoder.jp/contests/abc112/submissions/11476026)

### ARC051B - 互除法 [互除法の回数とフィボナッチ数列]
\(\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 回となることがわかる。

出力を昇順にしないといけない$<fn>{なぜ？}のがわからず、WA してしまった：
[11478758](https://atcoder.jp/contests/arc051/submissions/11478758)

### Diverta 2019 D - DivRem Number [約数]
約数に着目して、\(\textrm O(\sqrt N)\) で解くというのは気づいたのだけど、WA。
もう少し丁寧に考えるべきだった。

\(N = k(M+1)\) の形になることから、M の候補は約数ひく１。
すべてについて判定すればよかった：
[11482338](https://atcoder.jp/contests/diverta2019/submissions/11482338)

### ABC085C - Otoshidama [k-1重ループによる全探索]
自信ないなぁと思いつつ、ヒューリスティックな探索を書いて 
[WA](https://atcoder.jp/contests/abc085/submissions/11485516) 
だった$<fn>{惜しいようにも見えるけど…だめですね、きっと}。

\(N \le 2000\) なので、3重ループで　x, y, z の値の決め方すべてを試す時間はないけど、
x, y を決めると z は一位に決まるので、二重ループですべての可能性を列挙可能：
[11485843](https://atcoder.jp/contests/abc085/submissions/11485843)

## 2020-04-03
### CODE FESTIVAL 2017 qual C C - Inserting 'x'
中心をみつけて真ん中から外側にみていこうとして、なんかバグってたらしく
[RE](https://atcoder.jp/contests/code-festival-2017-qualc/submissions/11452299)。
これはこれで、合わせられるべきかと思うが、外側から見ていけばより簡単に書ける。
以下、解説 PDF より抜粋：

- s の先頭文字と末尾文字が同じ場合 → s から先頭文字と末尾文字を取り除く
- s の先頭文字と末尾文字が異なる場合
 + s の先頭文字がx である場合 → s の末尾へx を追加する
 + s の末尾文字がx である場合 → s の先頭へx を追加する
 + s の先頭文字も末尾文字もx でない場合 → 答えは-1 である

こうして、x を追加した回数が答え：
[11452636](https://atcoder.jp/contests/code-festival-2017-qualc/submissions/11452636)

### ABC156D - Bouquet [mod p における逆元、二分累乗法]
大きな n に対する \(2 ^ n \ (\textrm{mod}\ p)\) や、逆元を用いる問題：
[11456949](https://atcoder.jp/contests/abc156/submissions/11456949)

### AGC017A - Biscuits [数列、偶奇]

はじめ、思考を放棄して bitmap を使った全探索だーというのを書いてしまって、
[TLE](https://atcoder.jp/contests/agc017/submissions/11461968)
$<fn>{提出するまえから TLE であることはわかったけど、記録を残すために提出}。

解説 PDF にある通りだけど、以下のように考えることができる：

数列に含まれる数字がすべて偶数だった場合、P == 0 のときの答えは \(2^N\), P == 1 のときは 0 

数列に奇数が含まれるとき、その数字１つに着目する。残りの数列に含まれる個数は N - 1 個。
残りの数列から選んだ数字の合計が奇数であれ、偶数であれ、着目した数字を加えるかどうかを適切に選ぶことで、偶数／奇数のいずれもつくることができる。
よって、この場合の答えは　P によらず、残りの　N-1 個の選び方の個数、つまり
\(2^{N-1}\) となる。

投稿したプログラム：
[11462263](https://atcoder.jp/contests/agc017/submissions/11462263)

## 2020-04-02
### ABC153E - Crested Ibis vs Monster [DP]
貪欲でいけるんかなぁ、でも、E 問題だしなぁ。制約（変数の範囲）は…、
というので dp にして回答：
[11431501](https://atcoder.jp/contests/abc153/submissions/11431501)

## 2020-04-01
### CADDi 2018 C - Product and GCD [素因数分解]
ニブタンで適当に…とかおもったんだが、N, P ともに最大 \(10^{12}\) という範囲が厄介で悩む。
素因数分解してしまえば、あとは簡単だった：
[11406708](https://atcoder.jp/contests/caddi2018/submissions/11406708)

### ABC084D - 2017-like Number [エラトステネスの篩、累積和]
Easy さすがに物足りなくて、Recommendations Moderate を、実験 hide にして、
20番目（Moderate のなかでは簡単なの）に取り組みように切り替え。

いまは解き方がわかったあとの実装力を訓練したいというのに、良い感じで合った問題だった。
ただ、今回は、ありものの組み合わせで、Primes を計算したあとに、それを用いて
isPrime 判定しているが、Primes の計算過程でできる配列を (filter せずに）そのまま
持ち入ればよかった。この点いまいちでした：
[11414269](https://atcoder.jp/contests/abc084/submissions/11414269)


## 2020-03-31
### ABC058C - 怪文書

おとといあたりから、Recommendation (Easy) をやっていってる。
使用言語を Haskell にしてから、実装力とアルゴリズム力の両方が不足しているんですが、
まずは前者を強化するのに、負荷の軽いのをさっさかやろうかと:
[11382372](https://atcoder.jp/contests/abc058/submissions/11382372)

んで、Hlint にこういわれました（↓）。以後きをつけます。

$$<pre>{
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
$$}


## 2020-03-30
### AGC009A - Multiple Array
貪欲。後ろから貪欲にというのはすぐ気づいたのだけど（配列を逆順にしたので処理は前から）、さいしょ、素朴に更新をかけてしまって TLE に。そうか、これだと \(\textrm O(N^2)\) か。というので、やり直して AC：
[11359075](https://atcoder.jp/contests/agc009/submissions/11359075)

## 2020-03-28
### ABC160E - Red and Green Apples
それなりに時間を残して書き始めたんだけど、確信もないまま貪欲っぽいのを書いて WA。
解説をみて、「あー、なるほど」となった。これは…。自分で思いつくかなぁ：
[11319293](https://atcoder.jp/contests/abc160/submissions/11319293)

[解説PDF](https://img.atcoder.jp/abc160/editorial.pdf)より：「元から赤色のリンゴを X 個以上食べることはないので、美味しさの大きい方から X 個以外は捨て
ます。元から緑色のリンゴを Y 個以上食べることもないので、美味しさの大きい方から Y 個以外は
捨てます。すると残ったリンゴからどのように X + Y 個のリンゴを選んでも、無色のリンゴを適切
に着色することで赤色のリンゴ X 個と緑色のリンゴ Y 個にすることができます。よって、残ったリ
ンゴを美味しさの大きい方から X + Y 個食べれば良いです。」




## 2020-03-25
### ABC032C - 列 [しゃくとり法]

昨日、蟻本の「しゃくとり法」のところ読んだし、やってみようと思って。
たかがしゃくとり法と思っていたけど、けっこうてこずってしまった$<fn>{ループが使えないから…}。

しゃくとり法の実装上の注意点として、「左端が右端を追い抜かさないように」というのが、解説にも書いてあるのだけど、$<verb>{solve} 関数を書いていて、\(k == 0\) のときにこれの扱いが面倒だなと気づいて、ゼロのケースは $<verb>{solve} の外で処理するようにした。

結果、それなりに簡潔には書けたとは思うが、書くのに時間がかかった：
[11190145](https://atcoder.jp/contests/abc032/submissions/11190145)

## 2020-03-16
### AGC003 B - Simplified mahjong

Difficulty = 1186

貪欲に。みたまま解いたけど、一回 TLE 踏んでしまった：
[10930676](https://atcoder.jp/contests/agc003/submissions/10930676)

## 2020-03-15

昨日の [パナソニックプログラミングコンテスト2020](https://atcoder.jp/contests/panasonic2020) は惨敗。40 もレートが下がってしまった。

というわけで復習。

### パナソニックプログラミングコンテスト2020 B - Bishop

盤の幅（または高さ）が 1 だと角行は動けない：
[10919896](https://atcoder.jp/contests/panasonic2020/submissions/10919896)

### パナソニックプログラミングコンテスト2020 D - String Equivalence

いくつも反省点あるけど、メジャーなものは、

- 標準形の条件をみぬけなかったこと
- 少し複雑な順列生成には dfs を使うといい

かな。文字列を後ろに伸ばしていくので、また Data.Sequence をつかった：
[10920257](https://atcoder.jp/contests/panasonic2020/submissions/10920257)


## 2020-03-12
### diverta 2019 Programming Contest 2 C - Successive Subtraction [数列]

Difficulty = 1221

これも、解説 PDF みてもピンとこず、動画みた。
操作に気を取られず、\(M = \pm a_1 \pm a_2 \cdots \pm a_n\) の形になることに着目、
あとは…（解説動画をみよう！）

実装には、また、Data.Sequence をつかった。\(\textrm O(n \log n)\) の sort （unstableSort の方が速い）もあるし、便利だ：
[10769906](https://atcoder.jp/contests/diverta2019-2/submissions/10769906)

## 2020-03-11
### M-SOLUTIONS プロコンオープン D - Maximum Sum of Minimum [木、BFS、Queue, Data.Sequence] 
Difficulty = 1236

解説 PDF 読んでもいまいちピンとこなかったのだけど、解説動画みたら、
PDF に書いてある通りだという…。
辺に書かれる数字がある数以上であることを保証しながら木を成長させていくには、
どうすればいいか？と考えると、求める muximum 値と構成方法の両方がわかる。

BFS $<fn>{別にこの問題では BFS である必要はないのですが} の 
queue を List で実装して、TLE をくらった。
Haskell ではキューがほしくなったら [Data.Sequence](https://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Sequence.html)
を使えということになっているらしい。両端キューとして使える。
つかった:
[10750861](https://atcoder.jp/contests/m-solutions2019/submissions/10750861)


## 2020-03-10
### ABC158E - Divisible Substring
剰余、素数の性質、など。
解説みないと解けなかった。みても、いくつか躓いたり。:
[10728035](https://atcoder.jp/contests/abc158/submissions/10728035)


## 2020-03-04
### ABC048C -  Boxes and Candies

貪欲法、difficulty = 1128 : 
[10519601](https://atcoder.jp/contests/abc048/submissions/10519601)

とちゅう、d の計算（$<verb>{let d = max (ai_1 + ai - x) 0}) で、
d の下限が ０ になるように…というので、下限のイメージでつい $<verb>{min} 
と書いてしまってバグるなど。ああ、頭が腐ってしまったのかと思った。

## 2020-03-03
### ABC080C - Shopping Street

まぁ、ふつうに、びっとで。
IOUArray や UArray をつかった。型注釈ないとコンパイル通らない…んですよねえ：
[10504123](https://atcoder.jp/contests/abc080/submissions/10504123)

## 2020-01-25

現在のすうじ：

AtCoder:

- Rating 1112
- 参加回数: 15

AtCoder Problems:

- Accepted: 335
- Languages: C# 296, C++ 19, Haskell 36

## 2020-01-22
### ARC062D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

dp かなぁ、状態数爆発しちゃうなぁと少し悩んで。
貪欲にいけばいいんじゃないのと書いてみたら通った：
[9668798](https://atcoder.jp/contests/arc062/submissions/9668798)

解説をみると、それすら必要なくて所謂 \(\textrm O(1)\) 解法がある問題だったもよう。
そういう勘もつけたい。

## 2020-01-19
### ABC152E - E - Flatten

Int ではなく、Integer をつかうとすっきりサクっと解けた。
これを期に、$<verb>{getIntegerVec} も用意しておくことにしよう：
[9643004](https://atcoder.jp/contests/abc152/submissions/9643004)

コンテスト当日に書いたもの（[9628302](https://atcoder.jp/contests/abc152/submissions/9628302), 380ms）より、上記の版の方が 1.8 倍ほど速い（208ms）点も要注意かも。正格版 $<verb>{foldl'} を用いたことと、多相の $<verb>{sum} ではなく、ベクタ専用の $<verb>{VB.sum} を用いたところが違う。

see also: [foldlを直す](http://tanakh.jp/posts/2014-04-07-foldl-is-broken.html)

### Keyence2020B - Robot Arms [区間スケジューリング問題]

「区間スケジューリング問題」（蟻本 p.43）そのもの。
終了時間の早いものからとっていく（貪欲法）。
状態としては、選んだ個数と、すでに選んだ仕事の終了時刻だけを持てばよい：
[9643837](https://atcoder.jp/contests/keyence2020/submissions/9643837)




## 2020-01-16
### ABC141D - Who Says a Pun? 苦戦中

Rolling Hash と二分探索でとくやりかたを書いてみたのだけど、どうにも TLE から脱出できない：
[9534064](https://atcoder.jp/contests/abc141/submissions/9534064)

この解き方にこだわるわけではないが、同様の方法での
[C#版](https://atcoder.jp/contests/abc141/submissions/7675416) にくらべてはっきり遅い理由は理解したい…が、てこずりそう。

いろいろ調べるなかで、今日わかったこと：

$<verb>{or $ map (<5) [0..]} は一瞬で停止するが、$<verb>{V.or $ V.generate 100000000 (<5)} は終わらない（V は Data.Vector.Unboxed）。
それもあって、明に停止するように $<verb>{or $ generate} に相当するような再帰関数 $<verb>{check'} を書いてみたのだが、
どうも、そういう問題ではなかった。