脳log[AtCoder: 2020-08-20～]

最終更新: 2020-08-24T19:08+0900

♪ [AtCoder] AtCoder Beginner Contest 175／D 問題 Moving Piece

コンテスト時間中には解けなかった。昨晩から苦しんで夕方に初の AC をもらった>「自分の提出」

 最初の提出 #15953114 (RE / TLE)

バグが２種類あったけど方針は間違ってなかった。

 バグ１：K が各巡回グループ(配列 A の要素)の要素数より大きいときの端数(K%A[i].size)の扱い。

巡回グループの部分列(スコア数列)の和が最大となるときを考える。部分列の最大長が K%A[i].size 以下となる範囲で和の最大を求めるより、一周少なく回って(A[i].sum １個分のハンディを背負って) K%A[i].size 以上 A[i].size 以下の長さで和の最大を求めた方が得する場合がある。

RE の直接の原因は、最初はゼロ除算を疑ったのだけど、Array#take の引数 k-1 が負になることだった。その値の出所が K%A[i].size。

 バグ２：１以上 K 個以下の連続する部分数列のうち和が最大となるものの求め方。

バグというよりパフォーマンス問題。Array#product で総当たりをしたので、間違いはないが時間がかかりすぎた。バグらせずに時間内に求める方法が最後までわからなかった。

 最初の AC #16057773 (729 Byte / 77 ms)

やっとバグ２がとれた。総当たりの方の、間違いではないが時間のかかる方法と答えをつき合わせてデバッグをした。

こうやって振り返ってもさっぱり参考になることが書いてないね。実装が難しかった、しかない。

 「Ruby によるすべての提出(実行時間昇順)」

現在の２番目のタイムが 95 ms。区間の最大値ということでセグメントツリーの使用は一応考えたんだよ。だけどこのときのこれが頭を離れなかった>「追加する要素との大小関係によって、待ち行列の末尾から、永遠に最大要素(最小要素)としての順番が来ない要素を追い出す」。おかげで 77 ms。

理想的にはこんなふうにすっきり鮮やかに解きたいね>提出 #16033967 (581 Byte / 175 ms)

普通に累積和の配列から k 要素を切り出して最大値を取り出してる(ss[_1 + 1, k].max)。回路長の３倍の長さの累積和配列を用意してるのがよくわかっていない工夫か(ss = (1 .. 3*l).each_with_object([0]){|j, o| o << o.last + Cs[lp[j%l]]})。

ss[l] が回路全体のスコアの和。0...l の範囲の１点を始点にして長さ k(+1) の部分列を切り出す。k = mi[K, l + K%l] だから、最大で [l-1+(l+l-1)+1] の要素にアクセスする。長さは 3l 必要。 ma[0, ss[l]] によって回路全体のスコアの和が正か負かの場合分けを省略している。

Array#max を分岐と見ることもできるかもしれないけど、場合分けをしてそれぞれに固有のスペシャルな式を書くより、Array#max, Array#min を含んでいようとも１つの統一された式を書きたい。実に自分好みのスクリプト。「if 文が嫌いである。(20181029)」

そうだそうだ、自分は長さ k の部分列の始点を負のインデックスにすることで仮想的に配列の長さを倍にしたのだった。小賢しい。まあ、それでは長さ 2l にしかならないから、3l が必要な「場合」は配列の加算(a+a)をしている。このやり方をとる限り場合分けを解消できないね。

最終更新: 2020-09-03T17:14+0900

♪ [AtCoder] AtCoder Beginner Contest 174／C 問題 Repsept

時間内に B 問題までしか解けなかったので今日の日記は C 問題。AGC の C なら解けないのは残念ながら当然だけど、昨日あったのは ABC で、C 問題は 300 点問題だ。嘆かわしい。

解るような気がしながら解らなくて、でもやっぱり解りそうな気がするという堂々巡りを繰り返すだけで考えがさっぱり焦点を結ばなかった。具体的には 7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた。

 提出 #15651178 (AC / 306 Byte / 136 ms / 14428 KB)

 提出 #15663806 (AC / 294 Byte / 118 ms / 14508 KB) ※無駄を省いて整理したもの

布団の中でも考えていて眠る前に AC が出た。だけどまだ解らない。このプログラムが停止するかどうかさえ自分には不確かだ。

たどり着けるならK回目までにたどり着くので「K回目までにたどり着かなかったら到達不能と判断」でもよかったか

うん、これが解らない。

K の余りをとるなら余りの種類が K 種類しかないのはわかる。同じ余りが出たら以降が循環ルートに入るのもわかる。K+1 回目以降の余りが必ず既出なのもわかる。わからないのは、自分が提出したスクリプトでははっきりとわかる形で K の余りを求めていないところ。たぶん変数 k に配列７の要素( 0 以上 9K 以下の値)を足して 10 で割ったあとの k の値がそれっぽいから、この k の値が既出かどうかをチェックする方法があると思う。

でも問題に用意された入力について言えば、答えが出そうな K からは必ず答えが求まっているようではある。それは必然なのか偶然(出題者の作為)なのか。

 Ruby によるすべての提出

他の人の提出を見ると明らかに自分だけ*おかしなことをしている(嬉しい)。え？ 停止条件さえ判れば(※自分には判らない)、数列を順番に K で割るだけでいいの？ (※桁が大きくなりすぎるので余りにだけ注目する必要はある)

たぶんやっていることは実質的に同じで、一方が難読化されているというだけなのだろう。問題の理解がこんがらかっているからスクリプトもそうなる。過去に２回くらい日記に書いてるけど、アホの子は自分で問題を難しくする。(問題の本質、抽象化された実質が理解できないから、無駄や回り道がなくせないという意味)。

 「おかしなこと」の説明をば

1. 与えられた K の１の位の数字を見る。
2. １、３、７、９なら掛ける数を(１から９から)選べば１の位に７が作れる。
3. 作りました。１の位の７はもう無視します。(K にある数を掛けてできた数の)１の位ではないところに７か７ではない数字が残ります。
4. 次はそれに、K に(０から９の)何を掛けたものを足せば末尾に７が作れるかを考えます。
5. 以下３へループ。
6. ３から５は要は K に何を掛ければ７の列になるのか、１の位から順に決定していこうという手順。筆算をイメージしながら。
7. たぶん、運が良ければ、もしくは不思議な法則に従って、掛けてできた数字のどの桁も７になることがあるでしょう。
8. 全部で７がいくつ作られましたか？ というのが答え。

 「7,77,777,7777,... という数列を規定するルールを、どのように捉えれば解きやすいか考えあぐねていた」

「レプユニット数」という概念があるらしい>「[AtCoder] ABC 174 C – Repsept | ヤマカサの競技プログラミング」 そういえば問題名が Repeat でも Respect でもなく Repsept だ(今初めて読んだ)。

 逆元？

この問題の２つの解法というのは、逆元とか割り算を含む式の余りについて理解を深めるチャンスだという気がするんだよね。何か関係がありそう。以前解けなかった問題>「階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。」

(別の問題の解説だけど)これも理解の手がかりにできそうな雰囲気。雰囲気しかわからぬ……

公式解説は累積和だね、横一列を1回の掛け算で済ます方法

僕の解法は「単純に2で割れないから逆元を使った難しい解法になる」と言われてた

抽象的に考えすぎて難しいだけでは。11ぐらいの小さい数で試したことがあれば難しくなく思いつけると思う

最終更新: 2020-08-15T20:50+0900

♪ [AtCoder] AtCoder Beginner Contest 173／F 問題 Intervals on Tree

コンテスト中に解けなかった(問題文を読むところまでいかなかった)問題に挑戦。

「連結成分」っていうのがわかんないよね、まず。出力例１の解説を読むに、頂点集合が辺で繋がれたいくつの部分に分かれるかを数えるみたい。

 考えたこと

1. 頂点集合は考え得るすべての通し番号から作られる(１～２、１～３、２～７など)。頂点番号と木の構造に関連はない。
2. 頂点集合ごとに Union-Find するのはどう考えても間に合わない。
3. LCA が高速に求められたらいけるだろうか。頂点集合に含まれる任意の２頂点をすべて試していたらどう考えても間に合わない。
4. トポロジカルソートして割り振った番号と実際の頂点番号を見比べて何かわかるだろうか。わかんない。
5. 木を構成する頂点を「決まったやり方で並べていったら(20200607p01.02)」連結成分が配列の連続する部分として見出せるだろうか。そんなにうまくない。
6. 木ってどこが根とか決まってたっけ？ どのノードでも根になれる？ 葉でも根になる？ なる。
7. 一番考えやすいのは、葉が単独で連結成分を構成するとき。葉Cと親Pのあいだに辺があるような(=CとPが共に頂点集合に含まれるような) L,R の選び方が L<=[C,P].min && [C,P].max<=R だから、その否定。(追記：これは嘘。実装中に気がついたがこれだと頂点 C が頂点集合に含まれないケースが紛れている)
8. 大元の根(※勝手に１つ決めます)に一番近いノードに連結成分を代表させることにすると、あるノードCを根とする連結成分がカウントされるかどうかはノードCと親とのあいだに辺があるかどうかでわかる。
9. すべての連結成分(=任意のノードを根とする連結成分)について、それがカウントされるような L,R の選び方を数えよう。

 提出 #15106396 (AC / 307 Byte / 351 ms / 35716 KB)

スクリプト化にあたって一番考えたのって、重複組合せの求め方だった。最初 N×N にして間違っていて、仕切りを置く場所を考えるんだったような、と思い出すのに時間がかかった。そして最終的に補集合ではなく目的のものを直接数えられることがわかって無駄になった。

あと、ちょこざいなやり方だとは思うけど、C と P の大小で場合分けをしたくないなと思って符号を利用した>[(c+1)*(p-c),(p-c)*(c-N),].max。あ、カンマが余分。これは「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」が最後まで見抜けなかった恨みである。

こうしたら最後の計算で根(c==0)の場合を例外扱いしないで済む。

P[0] = N # 0 を根にする。N は計算のため。

p (0...N).sum{|c|
	p = P[c]
	[(c+1)*(p-c),(p-c)*(c-N)].max
}

 「Ruby(2.7)によるすべての提出」

ワンライナーとかわけがわかりません＞＜

あ、これ？ 「閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。」 木のどの部分を切り取っても木だろうし、木なら頂点数と辺の数は N 対 N-1 に決まってるので、頂点数と辺の数のずれの大きさがそのまま森を構成する木(連結成分)の数というのは、まあ、言われたらそうかもね、という感じ。

言われなきゃわからないし、なんなら、連結なグラフで頂点数と辺の数の比が N 対 N-1 ならそれは木だというのも、最初からなんだか化かされてるような気がしてる。

最終更新: 2020-07-09T19:18+0900

♪ [AtCoder] AtCoder Beginner Contest 160／D 問題 Line++

コンテスト中に解けなかった問題に再挑戦。(C 問題まで11分で終わらせてそこで力尽きていた。そんだけ時間を余らせてなぜ解けない？)

距離を求めるのに頂点の分類が必要だったのだけど、分類して組み合わせを網羅して距離を計算することができなかった。

今回は頂点を２次元座標に配置することを思い付いて、そうすると組み合わせの網羅や距離の計算が if 文ではなくデータを中心に構成できたので、解答の提出にまで至った。

 提出 #14892703 (AC / 1842 ms / 14560 KB)

N の上限が 2000 だから N×N(=400万)のループは TLE のおそれがあり、実際に 2 秒制限ギリギリだった。提出一覧を見たところ 100 ms は切れないみたいだが 500 ms くらいは普通に切りたい感じ。

• 距離を求めるのに頂点を３つか４つにクラス分けすれば直接計算できるのではないか
• クラスに属する頂点は連続する値を持っていて、求める距離も連続する範囲に分布するのではないか

というあたりでもうちょっと。

atcoder.jp/contests/abc16… すべてのiをBFSで最短距離出すところまではすぐ思いついたけど分岐する場所の計算がわからなくて敗北した

BFS とは思いもよらなかった。たぶんグリッドでなくほぼ直線だったからだろう。そういう先入観でプランＢが見えなかった。

 提出 #14909026 (AC / 66 ms / 14388 KB)

期待以上に速くなった！ ２桁ms！

• Ruby(2.7)によるすべての提出(実行時間昇順)
• Ruby(2.3)によるすべての提出(実行時間昇順)

すでに書いた通り頂点を４つにクラス分けして、始点４クラス×終点４クラスの場合に距離 k の頂点ペアがいくつになるかを計算した。計算は定数時間なので全体で k(=1..N-1) に比例した時間。

L[n][k] が主な道具。n 頂点で直線を作るときに距離 k の頂点ペアがいくつあるかを返す。

C[n][k] は n 頂点の円に対応する。頂点X,Yを除外する-4,-2 がアドホック。

k=1 の場合は例外。他と同じ式に組み込めなかった。

300 ms 台の人の十分に速くてシンプルな提出を見た>#14717011。長さ N の二重ループだった。ありうる２通りの距離のうち短い方を採用するだけだった。これをコンテスト時間中に書きたかったね。まあ、あとからでも書けなかったんだけど。

「２頂点間の最短パスは短絡辺を通るか通らないかのどちらかである」ということが最後まで見抜けなかったからなんだけど、それでも、何らかの方法で答えにたどり着きたかった。

たぶん Python のこの提出(#11387294)が自分と似た方針で同じようなコード構成だと思う。難しくてよくわからんけど。

最終更新: 2020-07-05T23:55+0900

♪ [AtCoder] AtCoder Beginner Contest 172／D 問題 Sum of Divisors

コンテスト全体については順当に、冴えない結果であった。あまり書くことがないので１つだけ。

 「D 問題への Ruby による提出(実行時間昇順)」

他が概ね 1000 ms ほどかけているところ、１つだけおよそ半分の 515 ms で済ませている>提出 #14757268。

ループでは他と同じ式を使ってるんだけど、半分に割って足しているところが鮮やか。足し算の背後にある論理がわかりません。

N/2+1 から N までの数は掛ける２をするだけで N を超えてしまうので、その数自身しか数える必要がない、というあたりかな。ループの中の計算が必要ない。

こんな手の込んだことをしていながら提出時刻も早くて、Ruby の中では５番目なんだよね。一方の自分は、C 問題で脳死の愚直手続きスクリプトを書いていた>提出 #14743690。脳死のまま清書>提出 #14788308。ステートメントを減らそうとしてやりすぎた>提出 #14788890

 脳死といえば……

D 問題にも最初は脳死状態で挑んでいた。こういうスクリプト。

1. N 要素の配列を 0 で初期化する。
2. 1..N のそれぞれに対してそれ自身と倍数に対応する配列の要素を +1 する。
3. 最後にその配列を使って K×f(K) (K=1..N) を計算して合計する。

でもサンプル３が親切にも N の上限値で、このやり方では時間がかかりすぎることに気付かせてくれた。さもなくばずぼらと拙速の代償として TLE を１個拝領していたことだろう。

 「[AtCoder 参加感想] 2020/06/27:ABC 172 | maspyのHP」

D 問題。問題と格子点の関連がさっぱりわからなかったのだけど、ループでシミュレートしてるΣ計算に N の一般式を与えようとしたときに、Σの中に整数除算があるから、反比例のグラフと軸のあいだの格子点の数に興味があるの？ その前に、k*N/k*N/k を約分したり分解したりはできない？

 「ABC172D - 西尾泰和のScrapbox」

ところで、この縦に足す方法では、半分から先はどうせ1つしかないのにループを回して一つずつ足してしまう。ここを斜めに足せばループは半分で済む。しかしどうせ斜めに足すなら… 左上までしっかり斜めに足す。そうするとループの回数はルートNのオーダーになる。

画像が見えない(scrapbox も CSS を切らないと読めない)。まだ「斜めに足す」がわからない。√N のオーダーになるとは他所でも読んだが、わからなかった。

k*(N/k)*(N/k) の、N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる(それとΣの区間も変化する)とか、そういう話なんだろうか。いや、どう書いてあるかはざっと読んだんだけど、読んだだけで解れば世話がないわけで……(あとでスクリプトにして確かめよう)。

 スクリプトにして提出したら 997 ms だったものが 68 ms になった。(比較のため Python だと 32 ms)

しかし明らかにもっとすっきり書く方法がありそうなんだよな、っていうかそれはすでに Python スクリプトとして示されてるんだけど、理解できないのです。

自分がやったのはすでに書いた通り、「N/k が１になるものだけを特別扱いするのでなく、２になるもの、３になるもの、４、５……で分けると定数係数としてΣの外に出せる」ということを利用して、k=1..N のループについて前から計算すると同時にループの反対側にある N/k==k (※)となるケースを計算して両端からループを進めようということ。繰り返し回数は 1,2,3,...,N/3,N/2,N の半分になるはずなんだけど、中間地点がどこにあるのか、全長がいくつになるのか、わかりません。

でもまあ、√N のオーダーになってるみたいだから、N=a*a だとして、1,2,...,a-1,a(=N/a),N/(a-1),...,N/2,N なんでしょう。

 整数への切り下げがなければ

m=N/k; n=N/(k-1) なのを利用して 68 ms のスクリプトのループの中の式を s+=N*(N+1)/2; s+=k*m*(m+1) と整理できそうなんだけど、そうするとこれまたどこかで見たような式(と定数)でさらに整理できそうな雰囲気があるんだけど、m と n の関係は通分したり約分したりできる関係ではたぶんないんだよね(答えが合わないから)。

 「AtCoder Beginner Contest 172 D - Sum of Divisors - Crieit」

図がわかりやすい。オーダーをちょっとずつ改善していく構成が付いて行きやすい。そして最後に見逃せないこれ>「なお、O(N^1/3)の方法もあるらしいです。」

格子点のやり方がこのオーダーらしい。さっぱり想像がつかない

じゃあね、せっかくリンクを張って紹介してくれた先(「格子点の数え上げの高速化 - memo」)を読みましょうよ、って話なんだけど、高速化云々より前に格子点がどのように関わってくるのかがまず知りたいよね。

 「格子点の数え上げの高速化 - memo」

まずここから(わかんない)。

1 から n までの約数の個数の総和（つまり、y=n/x の第一象限内の格子点の個数）は 2 \cdot \left(\sum_{i=1}^{\lfloor{\sqrt{n}}\rfloor} \left\lfloor\frac{n}{i}\right\rfloor\right) - \lfloor{\sqrt{n}}\rfloor^2 などを用いて計算することが多く

• y=n/x と y=x の交点が (√n,√n)
• y=n/x は y=x を軸にして対称
• x=1..√n の範囲で y=n/x と y=x のあいだにある格子点を数えて２倍する？ (たぶん y=x 上の格子点を一度だけ数えるよう気を配るのが面倒くさい)
• x=1..√n の範囲で y=n/x と x 軸のあいだにある格子点を数えて２倍して、重複して数えた (1,1)から(√n,√n)を対角線とする正方形領域の格子点を引く

 「考え方」

• 曲線上にある格子点が列挙できたら
• 隣り合う格子点間を結んで斜辺とする各台形内の格子点を計算で求めるだけでいい
• 斜辺上にある格子点にだけ注意してね(「傾きが既約分数の場合」)
• 最初のステップの列挙には Stern–Brocot tree が使えるよ

 「求め方」

• わかりません。ニュートン法みたいな試行を繰り返すの？ むしろユークリッドの互除法？

 ループをまたいで式を整理した。

• Ruby 提出 #14878990 (137 Byte / 66 ms / 14296 KB)
  • 前の版 提出 #14847505 (157 Byte / 68 ms / 14320 KB)
• Python 提出 #14879054 (145 Byte / 29 ms / 9096 KB)
  • 前の版 提出 #14849513 (168 Byte / 32 ms / 9108 KB)

それというのも Python の方には２桁msの提出が１ページ以上もあって、オーダーは変わらないしブレもあるだろうとはいえ、28 ms と 32 ms のスクリプトのあいだには明らかに式の複雑さに差がある。

 「Python によるすべての提出(実行時間昇順)」

※ 実行時間昇順で並べたときだけ自分の 32 ms の提出がリストされない。降順だったり提出時刻だったりでソートすれば現れる。消えているときは代わりに他の人の 32 ms の提出が２回リストされている。

32 ms の１つは自分のだが、28 ms は例えばこれ>提出 #14788253。平均タイムからして明らかに速い。

未だ及ばずながらだいぶ迫ったのではないか。

 これで最後。

最後に÷４するのにループの中で無駄に×４してるのが気になったので。

• Ruby 提出 #14942722 (141 Byte / 65 ms / 14304 KB)
  • 前の版 提出 #14878990 (137 Byte / 66 ms / 14296 KB)
    • 前の前の版 提出 #14847505 (157 Byte / 68 ms / 14320 KB)
• Python 提出 #14944808 (151 Byte / 26 ms / 9148 KB)
  • 前の版 提出 #14879054 (145 Byte / 29 ms / 9096 KB)
    • 前の前の版 提出 #14849513 (168 Byte / 32 ms / 9108 KB)

これを最適化というのではないか。この問題でしか意味のないループになった。少なくとも自分は式の意味を、途中からは理解していない。

実は最終版の while ループの中身は一番最初の 997 ms の提出とそっくりになっている。戻ってきた。

 Python のこの提出 #14841471

Ruby で書くとこんな感じ。

N = gets.to_i
p (1..Math.sqrt(N)).sum{|k|
	n = N/k
	k*n*(n+1)-k*k*k
}

違いを見比べると -k^3 がループの中にあるか外にあるかの差なんだろう。Wikipedia による と \sum_{i=1}^nk^3 = \left(\frac{n(n+1)}{2}\right)^2 らしい。

k*[n*(n+1)-k*k] からは、何か、意味が読み取れそうな気がするね。数学力があれば見えるんだろうか。数学力があれば意味を保ったまま易々とたどり着けるんだろうか。

 結局これでいい。

ループ後のつじつま合わせの正体が -\sum{k^3} だとわかったので……

N = gets.to_i
s,k,n = 0,1,N
while k<=n
	s += k*n*(n+1)
	k += 1
	n = N/k
end
s -= (k*(k-1)/2)**2
p s

最終更新: 2020-07-09T19:28+0900

♪ [AtCoder] AtCoder Beginner Contest 157／D 問題 Friend Suggestions

 成長の記録

• ３月１日 提出 #10470513 (WA と TLE)
• ６月21日 提出 #14507234 (AC / 432 ms / 54116 KB)

WA(Wrong Answer)の記憶なんてないまま新鮮な気持ちで挑戦したら普通に解けた。過去の提出を見直してみたらまあ、解答の構成がびっくりするほど瓜二つ。

では二者の分かれ目はどこに？

 友達の友達ネットワークの把握 (WA の理由)

WA の方はすべての人について一度だけ、その友達リストを処理している。AC した方は深さ優先探索で再帰的に処理している。なぜ再帰が必要か？

ある人 A と B が友達で、また C と D が友達であるとする。この時点で２つの友達グループがある。ここで A と C の両方と友達である E さんを処理するときに、A と C と E を繋ぐだけでは不十分で、すでに A や C とグループを作っていた B と D の所属グループまで更新しなければいけない。これをするためには配列を通り一遍に処理するだけではダメで、友達グループを記録した配列を何度もなめなめするか、再帰的に処理をする必要がある。

今ではこういう処理を Union-Find と呼ぶことを知っているし、グループの大小を管理することで書き換え処理が軽減できることも知っている。検索したらこれは序の口で、まだまだ奥が深いらしい。読んでないよ>「素集合データ構造(Union-Find)」「UnionFindTree に関する知見の諸々 - noshi91のメモ」

 例えば ARC097 の D 問題 Equals

自分の提出 #8121358 (AC / 310 Byte / 340 ms / 16252 KB)

何も考えず小さいインデックスにグループを代表させている。

betrue12 さんの提出 #2497462 (AC / 1004 Byte / 315 ms / 15116 KB)

rank(木の高さ)の小さい方を大きい方に接続している。

インタープリタ型言語は基本的に書けば書くほど実行に時間がかかるものだし、一般化して構造化すれば無駄が生じる。多く書いてそれが速いなら、アルゴリズムが優れていることに他ならない。

ところで、つい先月の新しい提出にすごいのがありますね。「Ruby(2.3)によるすべての提出(実行時間昇順)」

• tamura2004 さんの提出 #13758236 (AC / 915 Byte / 291 ms / 12292 KB)

  1. UnionFind クラス唯一のインスタンス変数 @data 配列の初期値は -1 であり、これはすべての要素がサイズ１のグループを作っていることを意味している。def size(a); -@data[find(a)]; end @data ひとつでグループとサイズの両方を記録している。
  2. unite メソッドでは @data[b] = a によって b グループを a グループに併合している。事前の比較により a グループの方が b グループより小さくないことが保証されている。しかし同時に行っている @data[a] += @data[b] の意味がわかりにくい。これは @data のもう一面、大きさを合計している。
  3. find メソッドの再帰停止条件は @data[a] < 0。負になるのはルートに対応する要素の値で、ルートにぶら下がる要素は 0 以上の値で他の要素をポイントしている。

  @data 変数ひとつであれもこれも済まそうなんて、なんてケチで欲張りなんだ。

 必要なのは中身ではなくサイズ (TLE の原因)

コンピュータで処理するものなのだから、現実的制約は無視できない。集合演算と整数の引き算(+α)のコストの差。十分過ぎて必要のない情報にコストをかけてはいけない。

 「成長の記録」とか見出しをつけたけど……

引き合いに出した ARC097 の D 問題の AC 提出は去年の10月のものだった。３月時点ではそれを糧にできていなかったのだな。

さらに言えば ARC097 の D 問題には AC 提出の前に１つ TLE になった提出があったのだけど(#8121130)、TLE の原因がグループを表現するのに集合を使っていたから。３月の提出が TLE なのと同じ理由。まるで成長していない……(それどころか WA まで)。去年の10月は TLE のままで終わらなかったのが偉くて、30分くらいかけてグループの中で一番小さいインデックスにグループを代表させることにしたらしい。それがどうして３月に生きなかったのか……。

しかし今日の日記を書く過程でさらに省メモリかつ高速なスクリプトへの手がかりを見つけられたのはもっけの幸い。わずか２日での進歩である。

• ６月23日 提出 #14633111 (AC / 338 ms / 17688 KB)

tamura2004 さんの提出を参考に。同じ問題に対する#10479576ではなくて、さっき引き合いに出した#13758236の方。

出力形式も変えたけど、ジャッジがスペース区切りと改行区切りを区別しないらしいのは kotatsugame さんの何かの提出で知った。これって kotatsugame さんの記事なんだけど……「AtCoderで実行時間0msを狙う - Qiita」

「どうしても1ケースだけ1msかかってしまう……せや！テストケース特定したろ！」「ちょっとくらい……探索サボってもバレへんか」「進む方向を定めるのに、ベクトル(sin(r),cos(r)) (r=0,...,99)を使っています。根拠はないです。」

「根拠はないです」やあらへんでまったく。ゴルファーでもあるこんな人がジャッジの細かい仕様を知らんはずないんだよなあ。

それに問題を読み直したら「答えを空白区切りで順に出力せよ」と書いてあって、たしかにスペース区切りの出力例は出力形式の一例に過ぎないといえる。

最終更新: 2020-09-01T19:43+0900

♪ [AtCoder] AtCoder Beginner Contest 157／E 問題 Simple String Queries

 成長の記録(２回目)

コンテスト本番では問題文を読むところまでたどり着けなかったし、仮に読んでいても TLE は免れなかったろう。

しかし今や蟻本でセグメントツリーについて読んだので何の問題もない。適切なデータ構造を扱えますか、というだけの問題である。それと時間内に実装できますか、という……(BITを使おうとしてた時間を含めて３時間くらいいじくってた)。

提出 #14702134 (AC / 835 Byte / 449 ms / 39004 KB)

セグメントツリーを初めて実装したのがこのとき>20200610p01。今回は更新があったのと、ツリーを根からたどったのと、２の冪乗になるように詰め物をしなかったのが初めてのこと。

提出 #14702414 (AC / 774 Byte / 350 ms / 38728 KB)

最初の提出では本を見ながらそれにならって値を根からたどって取得したけど、そうしなければいけない理由はなかったのだった。以前の雰囲気実装と同じく葉から始めて値を取得するバージョンがこれ。速いよね。fn メソッドをインライン化したらもうちょっと稼げると思う。

提出 #14702882 (AC / 708 Byte / 333 ms / 38948 KB)

fn メソッドをなくしたけどあんまり変わらない。ループの中で多重代入というのが影響することも知ってるけど(20200428p01.08.01)、表記の簡潔さはゆずれない。

ST#[]= メソッドのために１個だけ詰め物をしたけど効果がなかったので(#14702766 RE)、詰め物の意味はない。消し忘れ。

スクリプト言語での popcount は二進文字列化して "1" を数えるものが多いみたいだった。高々26ビットだということがわかっているので log2(32) セット(=５組)のビット演算で済ませる魔法があるらしいし、そういう提出もあった。その他にも色々と『ハッカーのたのしみ』で紹介されている。ループを回してるのは芸がないね。

• Ruby 2.3 によるすべての提出(実行時間昇順)
• Ruby 2.7 によるすべての提出(実行時間昇順)

 Python によるこれらの提出。提出 #14610743、提出 #10774518。

内部データサイズが単なる 2N に見えるのが不思議。添字の扱い方はヒープに見えるけど、２の冪乗じゃないと階層が崩れて右が左に左が右になりそうなものだ。さっぱりわからん。

蟻本の著者の一人のスライドを見つけた。

• 実際には，この実装なら n が 2 の累乗でな くても動作する

  値の更新の方はこのままではダメで，同様の 手法で再帰関数で書けば OK

• ただし，配列サイズは MAX_N * 2 - 1 では 足りない – MAX_N * 4 取れば十分

まだわかりません。それに Python による fold 関数とスライドにある query 関数は引数の数が全然違うんだよね。片方は再帰ですらないし。

 追記@2020-09-01 「Segment Tree のお勉強(1) | maspyのHP」

一方の提出ご本人による記事である。「いわゆる非再帰実装」「N = 2^n を仮定しない」 これこれ。ありがたやありがたや。

最終更新: 2020-06-15T23:25+0900

♪ [AtCoder] 第二回 アルゴリズム実技検定 過去問

 自分のすべての提出

第三回まで過去問をやったけど(20200607p01、20200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)

 L 問題。清書しようとしたらバグに苦しめられた。

• 最初の AC 提出 #14164516 (AC / 1293 ms / 93824 KB)
• 清書した AC 提出 #14183943 (AC / 870 ms / 61964 KB)

ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。

二分木におけるLCA

木の構造が定まっているので、bit演算で計算できる。

こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、１つか２つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。

 せっかく清書したけど

他の人(Ruby では２人いる)の提出を見ていたら不備に気がついた。

B,BL = A.map.with_index.to_a,1<<A.size.bit_length
H = [nil]*(BL-1) + B + [B[-1]]*(BL-B.size)

こんな感じで配列 A のビット長をもとにしてヒープのサイズを決めてるけど、例えば A のサイズが２のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。

例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。

 値の取得を最下段から遡ってやってるけど

これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。

更新を遅延させるとか、考えてもみなかった。

それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、０から連続する離散値だっていう。

必要になるまで考えないでいいことは考えない方針で。

 図を見てたらまだ理解が不十分で無駄なところがあった。

上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。

右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。

具体的なコードは次で。

 まとめ

単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。

 L 問題。Python で速い人の提出 #12961808 (279 ms / 61868 KB)

すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。

自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。

もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。

D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。

最終更新: 2020-06-09T19:05+0900

♪ [AtCoder] 第一回 アルゴリズム実技検定 過去問／K 問題 巨大企業

答えを出すだけなら簡単。社長を頂点とするピラミッドを遡るあいだに上司として出くわすかどうか確認するだけ。こういう問題は好き。逆にいつまでも数が合わない数え上げ問題は嫌い>禁止された数字への自分の提出。そもそもサンプルへの答えがいつまでも一致しないから、提出に至らないスクリプトが山ほど隠れている。

簡単ならどこが問題か。

 最初の提出 #14088806 (RE と TLE)

N の上限が15万だから、そして組織が非効率の極み直列15万階層だったなら、１つのクエリに答えるために15万マイナス１回階層を上らなければいけない。クエリは最大10万個ある。

そこは一応読めていたので、社員ごとに社長から何階層下にいるかという情報をメモしておいて、社員間の階層の隔たりと同じ回数だけ上司をたどれば答えが出せるようにしていた。でも TLE と RE。最悪の場合はやっぱり15万マイナス１回たどらなければいけないのだから、TLE はまあ当然。

 ２番目の提出 #14089327 (RE)

社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど。

それで TLE はすべてなくなった。１度だけ15万マイナス１階層をたどってしまえば、あとはすべてのクエリに定数時間で答えられる。

しかし TLE はどれも RE に変わっていた。最初の提出からかなりの数存在しているこの RE は何だ？ RE ってだいたいはヌルポだからよくある配列の範囲外アクセスが原因だろうと、考えるのを後回しにしていた。しかし目を皿のようにして調べてもその可能性はなかった。

 ３番目の提出 #14090337 (AC / 394 ms / 22832 KB)

再帰呼び出しをやめてスタック変数を……というと意味が違う。スタック構造を持つ変数をスタックの代わりに使うようにしたら通ったので、呼び出し階層が深すぎたのが RE の原因だった。最悪で15万マイナス１階層は深すぎるだろうなあ(最初から読んでおけ)。

 ４番目の提出 #14102282 (AC / 394 ms / 21500 KB)

• N 回繰り返す前処理のループで if を取り除いた。
• if を取り除いたことでスタックを社長で初期化するときに検索がいらなくなった。一石二鳥。
• 変数 T,L,R は一列に並べた組織構造(T)と、そこに張った社員ごとのインデックス(L,R)という役割だったのだけど、実は T は配列である必要がなくカウンタ変数で十分だった。(RDB でもインデックスに情報がすべて載っていて表がいらないケースがあるよね)

しかし実行時間は変わらず。「Ruby によるすべての提出(実行時間昇順)」を参考にすると、

• 回答の出力を一行ずつではなくまとめた方が速い。(システムコールを減らす、の類だと思う)
• スタック(変数)に一度に要素を詰め込まない方がたぶん速い。
• p メソッドが puts メソッドより遅いかもしれない。

ということが言えると思う。他に差がつく要素があるだろうか。

最終更新: 2020-06-26T13:37+0900

♪ [AtCoder] 第三回 アルゴリズム実技検定 過去問

 自分のすべての提出

やはり解けたのは K 問題までだった。ただし第一回と違って途中で１問落としたりはしていない。もうひと踏ん張りで80点を超えて上級だけど、残された問題の予想される難しさと裏腹に考える時間が残ってないんだよなあ(本番じゃないので途中でお風呂に入って本を読んだりしていたけども)。

第一回、第三回に共通する問題の傾向として、数学的応用的な要素が抑えられていて、愚直に効率的なコードが書ければ解けるものが選ばれている印象。よく知らないけど、一般的なお仕事コーディングに寄せていこうとしてるのかな。基礎的な知識とその初歩的な運用に漏れ抜けがないことを確認しようとしてるのかな。(緑色以下のコーダーには保証できることがない、というツイートを見かけたので。このへんとか>https://mobile.twitter.com/chokudai/status/1274756588624965632)

 L 問題 スーパーマーケット

• 提出 #14129871 (C++ / AC / 778 ms / 17904 KB)
• 提出 #14129916 (Ruby / TLE / 4272 ms / 61804 KB)

Python で解けることは運営元で確認してるらしいので(⇒)、Ruby でも方法はあるはずなんだよなあ。

タイムだけちらっと見た>Ruby でのすべての提出。提出数は４つで、ユニークユーザーは２人。2689 ms < 2726 ms < 2747 ms < 3735 ms。やっぱり方法はある。

TLE のケースはメモリの食い方が特異的に大きい。ざっと 1.5 倍。他のケースを見ると、必ずしもタイムとメモリ消費量のあいだに比例関係があるわけではない。メモリの割に時間がかかるのは M が大きいんだろう。TLE ケースは M も大きいんだろうけど、特に N と K が大きそう。K が大きくても配列の shift はポインタのインクリメントで済むようなので(Ruby-1.9の array.c で確認)、あまり影響がない。delete_at(1) を [1]=[0] and shift に置き換えたら一部速くなったから、やっぱり shift は問題ない(提出 #14129916→提出 #14130610)。N が大きいと……、M 回のループで４回ずつ行う二分探索の時間に影響する。N は棚の数だから商品数(メモリ)と商品の検索(時間)の両方に響く。問題が「手前から ai 番目までにある商品を見た後、見た商品のうち最も消費期限の値が大きいものを選んで棚から取って購入します」だから、棚を選ぶ検索は避けられない。方法があるとしたら、予めうまいことソートしてしまってループの中では検索しないか、４回を２回に減らすか……。

 M 問題 行商計画問題

 提出 #14141040 (Ruby / TLE)

半分以上がTLE。ACも17個あるからやり方は間違ってないと思う。しかし PAST の問題が考察よりも実装重視の傾向を持っている以上、TLEに甘んじるわけにはいかない。でも無理ぽ。

 提出 #14144878 (C++ / WA)

TLE がすべて WA か AC になりました。C++ のちから。TLE の陰に WA が隠れていたということで、やり方が間違っていた。

 提出 #14145227 (C++ / AC / 1695 ms / 74616 KB)

Visited フラグを立てるタイミングを誤っていたのと、訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた。

この問題を Ruby で、試験時間内に解けるなんてことがある？ ちなみに現在 Ruby で AC 提出はない>Ruby によるすべての提出。

ところで、1695 ms は C++ 最遅だった。C++ を使うなら２桁msで解けるらしい。

 問題名で検索した。

さっき「訪れなければいけない街と街のあいだの移動コストを計算するときに、訪れなければいけない別の街を通ってしまう場合の考慮が抜けていた」と書いた。その対策として、関心のない街を迂回するルートを２街間の最短経路として採用するようにした(たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは２本以上の２街間最短ルートの組み合わせとして現れてくるので。

でもこのステップで求めるものを、２街間の移動コストに加えてその際に通過する街と定義したなら、もっと速くゴールにたどり着けていたかもしれない。

解答は２パートに分かれているが、どうやら後半は幅優先探索ではなく DP でやるものらしい。もちろんその方が最遅より速くなるだろう。

でもまだ……。一度通過した街に戻るのにも移動コストがかかるから、状態や遷移には現在位置が関わってくる。それをベルトコンベヤ式に取り扱って答えにたどり着けるイメージが湧かない。二次元の遷移が解らない。

 色と認定の関係

https://mobile.twitter.com/atcoder/status/1273915562989502465

 現在 M 問題で唯一 AC を獲得している Ruby による提出 #14152776

気がついたこと

• 「(たぶんルートなしにした方が良かった)。もし他の街を中継するルートの方が結果的に低コストなら、そのルートは２本以上の２街間最短ルートの組み合わせとして現れてくるので。」と書いたが、あれは嘘だった。

• 注目している K 地点間の移動コストは K*(K-1)/2 通りを調べるのではなく、K 通りを調べるのが良さそう。

  終点を K 地点に限って試行回数を増やすより、終点を N 地点から限らず試行回数を K 回に留めるということ。

• 後半はワーシャル-フロイド法に見える３重ループ。

  ただし街と街を結ぶ中継地点(一番外側のループ)は街ではなく経由地のリスト。

最終更新: 2020-06-18T09:50+0900

♪ [AtCoder] AtCoder Beginner Contest 006／D 問題 トランプ挿入ソート

ちょっと日記に書きたくなるような、適度に歯応えのある問題だった。問題は、例えば

2 4 6 1 3 5 

のような数列が与えられたときに、

1 2 3 4 5 6

のように昇順に並べ替えるためには、いくつの要素を移動する必要があるか、その最小を答えるというもの。

 1. 連続する２要素に注目して増加しているか減少しているか見てみたら？

例えば、「2 4 6」「1 3 5」の並びは２要素間の関係において増加しているのでそのまま温存して答えにできるのではないか、逆に、「6 1」の並びは減少しているので必ず介入して解消しなければいけない。

しかし２つの増加列の関係に注目すると、「2 4 6」と「1 3 5」の位置関係が前後しているために、 2 と 4 と 6 の３要素または 1 と 3 と 5 の３要素を移動しなければ答えになりそうにない。

 2. 数列全体から最長の増加列(※要素は連続してなくていい)を１つだけピックアップしたものが答えの一部になるのでは？

たとえば初期数列が以下の通りだったら、

5 6 7 1 2 3 4 8 9

できるだけ長くなるようにピックアップした増加列は「5 6 7 8 9」と「1 2 3 4 8 9」の２本で、最長は６。

移動せずに済ませられるのが６要素で、他は必ず(ちょうど挿入ソートがソート列の中に挿入先を探して移動するのと同じように)移動させられる。仮に長さ６の増加列が２本あっても、移動せずに済ませられるのは６要素だけ。

 3. どのようにして最長の増加列の長さを知るか。ツリーを作る？

たとえば、以下の初期数列に対して、先頭の要素から順に継ぎ足して木を作るとする。

1 3 2 5 4 6

しかしこれは網羅してないながらすでにして冗長。(画像ソース：verbose graph.dot)

ここが思案のしどころ。

1. ある要素の後ろにいくつの要素が続くかは、その要素の値によって決まる。
2. だから 4 と 5 と 6 が複数回出現しているが、最も深いところの１つ以外は無用。
3. くっつけられる場所を見つけるために、そのうちのどこにくっつけるのが最善かを知るために、都度都度葉を根まで(あるいは根から葉まで)たどるのはいかにも無駄。
4. 知りたいのは深さだけ、それも最大の。中途半端はいらないし、経路もいらない。
5. どの枝がどれだけ伸びうるかは 1 に書いた通り。さらに言えば値は小さいほど良く、小が大を兼ねる。
6. 深さごとに最善の要素(最小の値)を１つ記憶しておけば足りる。
7. たとえば上の画像に対応する作業配列は [1,2,4,6] になる。２番目の深さにおいて最善の要素は 2 であり、その他の 3, 4, 5 の後ろが 2 の後ろより長くなることはない。

8. 新しい要素は作業配列の末尾に付け加えられたり、既存の要素をより小さい値で置き換えたりする。

   数列を先頭から処理するときの作業配列の変遷：[1] → [1,3] → [1,2] → [1,2,5] → [1,2,4] → [1,2,4,6]

 提出 #13936266 (AC / 227 ms / 4348 KB)

提出一覧を見ると 227 ms というのはいかにも遅い。

「Ruby による提出(実行時間昇順)」

ちらちらスクリプトの中身を見てると、二分探索の使用が目につく。それで気をつけて作業配列を見てみると、どの時点でもソート済みの状態が保たれているようだった。

できるだけ増加列の長さを伸ばしたいから、作業配列の末尾から更新位置を探していたし、更新位置が見つからない場合も想定していたけど、どちらにも無駄があった。位置探索はソート済みなのを活かして対数時間で済ませられるし、書き込む位置は必ず見つかる。

たぶん値の重複のあるなしで二分探索の使い方が変わるけど、この問題では重複なしが制約に含まれている。最近「bsearch_index の使い分けが見事」と評したのはこの提出>#13393878。lower_bound とか upper_bound とか -1 とか。Ruby には区別がないけど。

 提出 #13936659 (AC / 41 ms / 2556 KB)

凡人は一足飛びに答えにたどり着いたりはしない。しかしたどり着ける難易度ではあり、さらには提出した後でも発見があった。思わず日記に書きたくなる楽しさ。

 AtCoder Beginner Contest 165／F 問題 LIS on Tree

特になんということもなかった。作業配列を深さ優先探索のあいだ使い回しするだけだった。

 提出 #14435898 (AC / 707 ms / 259260 KB)

問題名で解説記事を検索してみると、LIS(※) に関して色々な方法があるなかで、自分が唯一知っている方法がぴたりとはまる幸運があったと言えそう。

※トランプ挿入ソートの解説記事を読むといやでも目に入るよね>LIS。ストレートな知識問題だって書いてるところがあったけど、知らなくても解けるし、むしろ問題を通して教えてもらえる、ありがたくも教育的な問題だった。

最終更新: 2020-07-10T21:58+0900

♪ [AtCoder] AtCoder Beginner Contest 006／B 問題 トリボナッチ数列

「Ruby による提出(実行時間昇順)」

２番目が 60 ms のところ、１番速い提出が 16 ms で済ませてしまっている。いったいどんな魔法を使ったのか、読んでみた。

 提出 #1163397 (nejiko96 さん / 16 ms / 4732 KB)

といっても、require 'matrix' して pow(power 累乗) して mul(multiply 乗算) してるだけに見える。優れたコードはストレートで無駄がない。あえて mul を定義しているのは途中で mod を取りたいからなのかなんなのか。

require 'matrix' には NArray や NumPy で得られるような恩恵はないと思う。累乗の高速化手法に掛け算の回数をおよそ log2(N) 回に減らす方法があって、最初の掛け算で２乗を作り、次に２乗と２乗で４乗を作り、という感じに倍々で N 乗に迫っていく。

途中の式がどんな掛け算と足し算と係数になるか想像もできないけど、トリボナッチ数列の第 N+3 項を求めるための N 回の計算を約 log2(N) 回に縮めるための行列であり、pow メソッドであるのだと思う。

これぞ線形代数って感じ(すくなくとも自分がイメージできる範囲の)。

 Tribonacci Numbers - GeeksforGeeks

素朴な手法から順番に紹介されている。1.再帰 2.配列メモ 3.三変数使い回し 4.行列の累乗

1. A simple solution is to simply follow recursive formula and write recursive code for it,
2. Time complexity of above solution is exponential. A better solution is to use Dynamic Programming.
3. Time complexity of above is linear, but it requires extra space. We can optimizes space used in above solution using three variables to keep track of previous three numbers.
4. Below is more efficient solution using matrix exponentiation.

 蟻本にはすべてがあるような気がしてくるな。

実際は自分の到達点の低さの反映に過ぎない。

最初に読んだときは動的計画法のラッシュで頭がパンクして「もういいです……」と本を閉じた。

その次に開いたときは実装したことのあるグラフアルゴリズムの登場に気をよくしていたところで、ここからが中級だ、と新しいチャプターが始まって、「もう無理です……」と本を閉じた。

182ページのコラムから

もっと高速な漸化式の計算

実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう。

最終更新: 2020-05-31T18:32+0900

♪ [AtCoder] NOMURA プログラミングコンテスト 2020／C 問題 Folia

こんな非道な仕打ちがあるだろうか。

AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC WA AC AC AC AC AC AC AC AC AC AC AC AC AC

最初の提出(#13737796)が MLE と WA であって、コンテスト終了30秒前で MLE の解消はできたのだけど、ひとつだけの WA が WA のまま残ってしまったと。

 提出 #13742470 (WA)

600点問題は解ける解けないの山が最初にあって、どちらかといえば時間をかけてもほとんど解けないのだけど、それだけに恨めしい。

 N よ！ お前か！ 提出 #13747866 (AC / 91 ms / 22960 KB)

N の制約「0≤N≤10^5」 0 以上

 leaf の複数形は leaves です。

どうしても完全丸ぱくりになるので提出する気がなくなったけど、N=0 の場合を特別扱いせずに対応できるようにループの中身を半分ずらしたり、配列 B を後ろから前から往復して値を埋め込んでいる処理を２種類の累計値を管理するだけで済ませたりできる。そうすると最後の答えを出すのに sum メソッドもいらない。

最終更新: 2020-05-26T21:01+0900

♪ [AtCoder] AtCoder Beginner Contest 168／F 問題 . (Single Dot)

解説PDFが奮ってる。これが全文。

x 座標・y 座標それぞれを重複を除いてソートし，十分なサイズの2 次元グリッド上に各線分を刻 み込んでからBFS すれば，O(NM) 時間となって十分間に合います．

座標値(-10^9 以上 10^9 以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ。

さらにこんな工夫も。「F問題は座標圧縮してグリッドグラフ上のBFSにしたいんだけど、こんな感じで、線の幅(=0)のマス目を仮想的に作ってあげると、面積は4倍になるけど、線がマス目の塗りつぶしで表現できるかららくちんになるよ。 pic.twitter.com/ZpX0hxGQjC」

そんなこと知らずに、重なってる線分を連結して、交点を列挙して、閉路(多角形)を見つけ出して、包含関係を判定して、多角形の面積の引き算で求めようとしてた。しかも閉路の列挙に関するバグが取り切れなくて完成しない。完成しても間違いなく TLE(Time Limit Exceeded) だし。

 C 問題が理由で「余弦定理」がトレンド入りしていたらしい。

名前が出てこないと検索も何もできないよね、この前の「逆元」「モジュラ逆数」みたいなもので(20191118p01)。自分は弧度法への変換だけして Ruby の Complex クラスに投げた(polar, 引き算, abs)。組み込みクラスなので使ってあげよう。

 F 問題。最初の提出 #13402510 (WA)

方針を教えてもらっても実装できるかどうかは別問題なわけで……。座標のグリッド化に際して線分の端点を切り詰め忘れて大量の WA。

 ３番目の提出 #13404210 (TLE)

２番目の提出はデバッグ出力を消し忘れて全部 WA だった。デバッグ出力を標準エラーに出すようにするといろいろ捗るらしいが。

線分の切り詰めバグを修正したら WA だったものがすべて AC か TLE になった。メモリ使用量が百数十MBを超えるテストケースがすべて TLE になっており、AC ケースのメモリ使用量は概ねそれ以下。無限ループ内でメモリリークでもないと思うから、単純に時間が足りないだけだと思いたい。

 現在 Ruby で AC してる人が一人だけいる！

555 ms！>「すべての提出 - AtCoder Beginner Contest 168」

 やったぜ！ #13406078 (AC / 2489 ms / 50112 KB)

diff をとらんとわからんくらいの微修正で全部 AC。バグはなかった。

TLE になった手法はこのときの成功体験を再現しようとしたものだった>20191006p01。たぶん今回は問題の規模が大きすぎて裏目に出たんだろう。

Ruby で２人目の AC なのは嬉しいけど、こちらは 2489 ms もかかってるんだよなあ。ソースコードも長いし、メモリも余計に使ってる。早期に INF を判定して終了すれば一部のケースで速くなるかもだけど、最悪ケースの改善にはならないんだよなあ。事前にデータを作り込むんでなく、インテリジェントなアクセス関数を通して仮想的なデータにアクセスする手法ならレイテンシは下がりそう。スループットも下がりそうではあるが。そんなこんなより面積４倍のオーバーヘッドが効いてるんかなあ。

 面積４倍を解消しても…… 提出 #13413181 (AC / 1460 ms / 22892 KB)

555 ms は驚異のタイムだよなあ。移動可能判定を検索でやってるのがまずダメなんだけど(メモリ使用量は減った)。

Python の AC 提出一覧がこちら>「すべての提出 - AtCoder Beginner Contest 168」 ほぼ一人の独壇場なんだけど、タイムの縮みかたがエグい。2488 ms から始まって 131 ms に至る。

「[AtCoder 参加感想] 2020/05/18:ABC 168 | maspyのHP」

 面積４倍でも

さっきの提出は一から書き直して面積４倍確保を解消したけど、面積４倍のグリッドを作ったままでもグリッド線上を飛び越えて移動するようにすればデメリットは解消する。牛がグリッド線上にいる場合にだけ注意すれば。

 Ruby で 555 ms の人のスクリプトを読んだ。

特別な工夫は見つけられなかったけど、必要のないことはやってない印象。bsearch_index の使い分けが見事。

翻って自分のスクリプト。o を埋めたり、Infinity を埋めたり、座標丸め関数を４方向分用意したり、各グリッドの面積をすべて事前計算して記憶したり、省けるなら省きたいところに文字数と処理時間とメモリを費やしている。未熟で不安があるから冗舌になる。『テスト駆動開発』(ケント ベック)の表現を借りれば「ステップを刻む」「歩幅は変えられる」。今の自分は細かく刻まなければ進めないということ。

 提出 #13454965 (AC / 474 ms / 43092 KB)

ぱくりです。写経。見比べて書いたわけではないけど、アイデアが同じなら同じになるでしょう。後で見たら PyPy3 で速い提出も同じ道具立てだった。

接続してる線分をまとめたり、交点のない線分を取り除いてからグリッドを作りたい気持ちがあるけど、見込まれる処理の重さに比して改善する度合いが入力依存でゼロになるとあって、何かのついでで棚ぼた的に交点一覧とグリッド座標化された線分一覧が手に入らないかなと夢想してる。

最終更新: 2020-10-29T15:09+0900

♪ [AtCoder] AtCoder Beginner Contest 167／F 問題 Bracket Sequencing

 わからない。提出 #13147757 (WA)

解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。(追記) 13日の現在はPDFもあるみたい。

これを読んでも間違っているとされている定義のどこに問題があるのかわからんのだよね。果たしてそれで解けるものか。>「競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ」

 まだわからない。提出 #13156522 (WA)

正規表現の ? を * に変えたことで、AC は増えたけどまだ WA がある。

こういう生成スクリプトでテストした結果、最初の提出で使用した正規表現パターンに問題が見つかった。

def puts s
	re = /(?<p>\(\g<p>?\))/ # バグあり。提出 #13147757 より。
	re = /(?<p>\(\g<p>*\))/ # 意図通り。提出 #13156522 より。
	t = s.gsub(re,'')
	print "#{t.empty?}:\t#{s}\t#{t}\n"
end

L,R = '('*5,')'*5
10.times{
	puts L+((L+R).chars.shuffle.join(''))+R
}

LR = '()'
10.times{
	puts 10.times.inject(''){|s,| s.insert(rand(s.size+1),LR) }
}

そうするともう、提出したスクリプトは完全に自分の意図通りに動作しているはずなんだけど、WA がある。書き間違いではなく、考え違いがある。

 そっか、)( 型の s を連結する順番によって結果が変わる。

)))( と )((( の２つの s があるとき、連結のしかたによって )))((( が残る場合と )( が残る場合に分かれる。)( を残した方が 'Yes' と答えられる確率が高くなる。

 提出 #13158713 (AC / 1014 ms / 16076 KB)

 バグがありますよ。)( 型の文字列が１つだけのときに必ず No と答えてしまいそう。

今現在 Ruby で一番速い提出は 498 ms だ。>すべての提出 - AtCoder Beginner Contest 167

再帰ありの正規表現(※矛盾した表現)を使ってる時点で勝ち目はない。左括弧の数が負になれないのに気をつけながら、左括弧と右括弧を対消滅させながら、左括弧と右括弧がいくつ残るかを数えればいいんだろうけども。

 問題はそこではなかった。>提出 #13160001 (AC / 821 ms / 14380 KB)

しかたない、省メモリを売りにしていこう。>すべての提出 - AtCoder Beginner Contest 167

ソートを必要としてないあたりで(※)ちょっとは有利を得てもよさそうなもんなんだけど、トップの提出はソート対象を )( 型に限るなどしてる。※ループ内で２要素のソートもあかんか？

 これが限界>提出 #13174623 (AC / 533 ms / 14308 KB)

 ちなみに

( 型の文字列を最優先に、)( 型のうち ( 優位のものを優先的に、最後に ) 型を、という感じで連結していくのがストレートな解答らしい。

３つの型の文字列を統一的にソートすることもできるし、)( 型だけソートしてもいい。

自分はどれもソートしてないんだけど、)( 型の中から１番目と２番目に条件のいい文字列をピックアップするための比較演算()( 型の文字列１つにつき１～２回)が重くてソートした方が速い。

 @2020-10-29 提出 #17712418 (AC / 391 Byte / 377 ms / 19604 KB)

(ゴルフ勢を除けば)わりと短くてそこそこ省メモリで今のところ Ruby で一番速い。すべては正規表現エンジンとそれを使う gsub のちから。

やってる内容は最初の AC と変わらない。入力をがばっとひとまとめに処理するようにしたのと、最小２要素を取り出すのに一度全体を配列に蓄えてから min メソッドを使うようにしただけ。

最終更新: 2020-05-29T19:43+0900

♪ [AtCoder] AtCoder Beginner Contest 165／D 問題 Floor Function

数弱さんには厳しい回だった。E 問題は読む時間さえなかったので今日の日記は D 問題。次の整数式を考察するだけ。

x*A/B - x/B*A

A を掛けてから B で整数除算するか、B で整数除算してから A を掛けるかという違いで生じる値の差について。その最大。

 1. x が大きいほど大きいんじゃないの？>提出 #12618779

違います。B を周期として第一項と第二項が一致します。A がその周期に与える影響はよくわかりません。

ちなみに B の上限は 10^{12} のため周期全体をテストすることはできません。>提出 #12633357

 2. x が B の倍数マイナス１のとき第二項の整数除算で切り捨てられる値が最大になるんじゃないの？

• →引き算される第二項が相対的に小さくなる
• →全体として大きくなる

たぶんその通り。だけど説明を端折った N との関係がわかんなかったのと、A と B の因数によって第一項と第二項で周期 B の位相がずれていくんじゃないかという気がしたので探索した。>提出 #12640433。でも錯覚。位相がずれるなら「B を周期として第一項と第二項が一致します」が嘘じゃんねえ。

Ruby で提出している他の人は、提出の早さも実行速度も優秀だった。>すべての提出 - AtCoder Beginner Contest 165

 B 問題 1%

実は B 問題で15分近く詰まっていた。瞬殺できないとあせる。最初は(もはやうろ覚えの) log を使って計算していた。

X = gets.to_i
p ((Math.log(X) - Math.log(100)) / (Math.log(101) - Math.log(100))).ceil

でも大まかにしか数字が一致しない。同じかちょっと小さい数字になる。俺が log を忘れているか浮動小数点数の誤差か(近い数字の引き算とか良くないのでは？)これの影響じゃないかと>「(複利、小数点以下切り捨て)」。複利の計算をするごとに切り捨てなければいけないのでは？

B 問題なので手続き的に解いても TLE にならないのはわかっていた>提出 #12601266

 C 問題 Many Requirements

実は C 問題でも30分近く詰まっていた。A 数列の総当たりでいこうと決めるまでに制約条件を総当たりしようとしていて、他の制約にまったく制約されない孤立した制約条件の扱いをうだうだ考えていた。

再帰をループにするとかの効率を考えずにちゃっちゃと書いただけなので、提出へのリンクはなし。

上手い人のゲームプレイ動画と AtCoder の解説 PDF のあいだの共通点。多様性のなさ。へたくその動画の方がバラエティに富んでいて見ていて面白くさえある。間違え方というのは本当に千差万別で、ありとあらゆる機会を逃さずに、そう来るかと予想もできない脱線をする。たったひとつのゴールに向かう限られたルートに収斂していくということがない。

当人にとっては面白くもなんともないので、B 問題、C 問題に詰まらないような世界線に乗っていきたい。

 あ、この問題ってそういう見かたができるのか。>小数部を分離

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

とはいえ、高度な問題を解く時に、「floorが出てきたら整数部と小数部に分離して式変形！」って結構大切な考え方なので、Dみたいなのを出さないと、後半問題で突然そういう数学力が応用状態で問われることになるので、そのあたりの塩梅がむずかしいよね。

x が固定小数点数で小数部が５桁なら、x - x/100000*100000 が小数部分になる。……という話ではない？ D 問題を解くときの話？

以前にもはっとさせられたことがあった。

kを使った場合のコストは、k-1以下のすべてを使ったコストより高い

これって要は 100000 > 11111 (２進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは（書き換えた要素の数によらず）2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて２進数で考えてみて初めて了解できることだったりする。

「一を聞いて十を知る(20200508)」ってこういうことだと思う。賢い人は「いやそれって同じことだから一の内に入るのでは？」と思うかもしれないけど、全然違うのである。

そして自分が AGC022C 700点問題 にまるで歯が立たない理由には、列挙された要素の数とそれらを煮詰める段階の深さに関係があると思ってる。「理解が及ぶ広さ、深さ、早さに優れ(20200508)」という風に書いたけども、そうでない自分は頭の中で抱えきれないし、整理して外に出して部分ごとに解決することもできない。

アストロノーカやテラリアですでに知ってるんだけど、ツリー状にねずみ算式に倍々に増えていく要求リソースの全体を把握すること、並列に進行する精製過程をストールさせないように需給を絶えず調整すること、このサプライチェーンの階層がある程度以上になると(たぶん３くらい)完全にお手上げになってしまう。そういう能力がない。

「たぶん３くらい」 深さが３、二分木なら葉の数８までしか脳内で扱えないんです。

 「アルゴリズム格言」

ちょっと検索したら「銀の格言」としてこんなのが列挙されてる。

• 攻めは銀、受けは金
• 銀は千鳥に使え
• 桂頭の銀定跡なり
• 銀は成らずに好手あり

つまりはこういうことなんでしょう？

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

「この問題だったらこうするだろ」って感じに無意識にやってることってめちゃめちゃ多くて、その「無意識」を言語化して列挙するだけでもめちゃめちゃ有効だと思うのよねえ。

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

「chokudaiのアルゴリズム格言1000」とか作って、こういうのをひたすら列挙しまくると、格言の組み合わせだけで良い感じに解ける問題がたくさんできそうだな、と思っていて、アルゴリズム名とは別レイヤーで浸透させたいな、ってちょっと思ってる。

「解説なんかだと、正しいルート以外はすっ飛ばされちゃう」というのがまさしく今日書いたことで(20200502p01.04)、解説PDFよりも「競技プログラミングの強みと「典型力」について - chokudaiのブログ」という思考の跡が見えるブログ記事の方が自分には有用となる理由。アルゴリズム格言に期待する理由。