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

最終更新: 2021-10-24T17:45+0900

♪ [AtCoder] 第二回全国統一プログラミング王決定戦予選 - AtCoder／C 問題 - Swaps (再)

読んだ眺めた>「競プロerのための群論 (swapと順列と対称群) - little star's memory」

数学の用語で何か抽象的なことを言ってるなーということと、Swaps と Moving Piece の２問(だけじゃないけど)が取り上げられているということはわかった。

Moving Piece は先日解いたので(20200820p01)、以前解けなかった(20191111p01) Swaps も解ける気がした。

 提出 #16248329 (AC / 403 Byte / 283 ms)

もちろん今日も AC に至るまでに WA を出した。それも前回と全く同じ入力に対して同じように誤った答えを出した。前回書いたスクリプトはひとつも参考にしなかったにも関わらず、構成も結果も瓜二つなのは、書いた人間が同じだからですね。同じところに留まっている……。

• 今日の WA 提出 #16245473 (402 Byte / 279 ms)
• 去年の WA 提出 #8390069 (464 Byte / 274 ms)

 デバッグ

前回と違ったのはテストケースが利用できたこと>「atcoder_testcases > nikkeiqual_2019 > C」

今回のような Yes/No 問題の場合、間違った方法ででたらめな答えが出ても２分の１の確率で AC になってしまいデバッグが捗らない。そのような場合に(テストケースなしでも)使える手法をひとつ思い付いた。

 提出 #16245274 (TLE)

スクリプトの真ん中に sleep (※引数なしなら永眠)を仕込んで、前半部分の Yes/No 判断に誤りがないかを確かめた。結果は TLE と AC のみだったので、前半部の判断は間違っていない。

 提出 #16245473 (WA)

予想外の WA (TLE なし)だった。これは後半部の No を sleep に置き換えたものなのだけど、１つも TLE がなかった。１つもないというのは(入力とバグり方がコラボした)偶然の結果なのだけど、偶然でもなんでも無条件 Yes は明らかなバグだ。

こんな感じで TLE(sleep) や RE(ヌルポ、０除算、変数名タイポ)が Yes/No ではない第３、第４の答えとしてデバッグに利用できると思った。こういう(アナーキーな)考え方ってゴルファーが得意としてそうだよね。常識だと思ってそう(違うんですよ)。

 バグ

わかってみれば些細なことで、思えば去年もインデックスの扱いに確信が持てずに試行錯誤をしていた。どうして B 数列が予めソート済みではないという、そのひと手間で穴にはまるのか、何度でも。

つまり、A 数列の初期配列と B 数列の初期配列。A 数列のソート済み配列と B 数列のソート済み配列。A, B 両者の扱いが対等なこれら４つは脳みその中に居場所が確保されていた。しかし、B 数列の初期配列をソート済みとする、と条件を整えたときに A 数列の初期配列がどうなるか(ソート済みではないし、元の初期配列とも異なる)、という概念が脳みそからすっぽり抜け落ちていた。A, B の対称部分に気持ちを良くして、差異に向ける目がなかった。去年も、今回も(初めは)。

 去年の借りを返す 提出 #16278383 (AC / 445 Byte / 199 ms)

「去年の WA」を完成させたもの。必要以上に慎重だった(見極めが甘く無駄だった)二分探索がないぶん、冒頭の AC 提出より速い。

 考察(おまけ)

前回の日記に全部書いてある(あれで全部だった)。ひとつだけ付け加えるなら、「逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など」の「など」でごまかした具体例の３つ目。

ソート済みの B 数列に異なる値を持つ隣接要素 B[i] と B[i+1] があって、B[i] < A[k] <= B[i+1] となる A[k] が存在しないときも、A 数列のすべての要素にあるべき位置が存在するとは言えなくなる。(A 数列がソート済みなら B[i] < A[i+1] を確かめるだけでいい)

最終更新: 2021-08-15T23:54+0900

♪ [AtCoder] 第二回全国統一プログラミング王決定戦予選 - AtCoder／D 問題 Shortest Path on a Line

余勢を駆って前回２つの WA であっさり引き下がっていた D 問題に再挑戦した。これも C 問題と同じ 600 点問題。

 提出 #16254983 (AC / 387 Byte / 402 ms)

実は区間の片端に着目した貪欲法で解けるんですよ、というのが目から鱗だったスケジューリング問題そのままだった。どこにそう書いてあったかは忘れた*。

前回の WA 提出 #8424473 を見ると、今と同じことは考えていたことがわかる。C 問題の場合にも言えるけど、そこで結果を分けたものが何か。考えたことを過不足なく言い換えることと、バグなくコードに置き換えること。それができるかどうか。

それはどうやったらできるようになるんですか？ という問いは、どうしてそこで間違えたんですか？ という問いと対になる。わかりませんよ。ワーキングメモリが足りないんじゃね？(テキトー) こういうとき脳筋は手を動かして慣れるしかない。そうすればより少ない脳のリソースで解けるようになったり、型通りの手法で解けるようになったりして、うっかりや見落としで間違えることがなくなる(という期待)。

 去年の借りを返す 提出 #16288240 (AC / 319 Byte / 375 ms)

区間のどちら端に着目するか。冒頭の AC 提出では L のソート順に処理していたが、「前回の WA」では R でソートしていた。それを完成させてみたら、冒頭の AC 提出で使用していた Array#slice! と Array#insert という、配列に対して呼び出すにはやや気が引けるメソッドが、Array#pop と Array#push という配列に相応しいメソッドに置き換わっていた。二分探索も３回から２回に減っている。Swaps の場合もそうだったけど、AC に至りさえするなら部分的には過去の方が優れてるのなんでだろう。

 解説記事を読んでもわからないので自分で書く。

グラフとか最短経路とかコスト０の辺を張るとかわからへんねん。

R でソートするバージョン(#p02.02)。

1. RC を、ある地点(R)に到達する最低コスト(C)を記録したリストとする。R が同じならコストの低い方を記録する。R についても C についても昇順(２要素の比較において R が大きければ C も大きい)。リストは最初空で、R の昇順に伸長していくこととする。
2. 区間 [L,R] から R までをコスト C で繋ぐ場合を考える。

   1. RC を二分探索し、最初に L かそれより後ろに到達する要素を見つける。より遠くに到達する要素はより高コストなので「最初」を見つける。

      見つからない場合は断絶があるということでありパスする。R の昇順に RC に要素を追加しているのであり、今後 [L,R) の区間に到達する辺は現れない。R に到達する辺があとから追加されることはあるが、C が負ではないのでパスで良い。

   2. 見つけた要素のコストを加算して C′とする。辺を追加することによりコスト C′で R に到達できることになる(始点は問わない)。
   3. RC に記録されている C′より高コストの要素は用済みであり取り除く(RC がコストの昇順であることを利用する)。処理時点で R が最遠到達地点であり、それより近くに高コストで到達することに価値がないから。
   4. ペア [R,C′] に記録する価値があるなら RC の末尾に追加する。
3. ということの繰り返し。

ひょっとしたらこれも DP (動的計画法) の一種かもしれないけど、わからんけど、自分が頑なに DP の用語を使わないのは、それを言ってもメリットがないから。

一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、４要素の配列でまかなえることの発見が。

これもそう。DP の核心は何を記録して遷移するかであり、それがわからないのに、「あ、これ DP だ」ということを言っても問題が解けない。むしろそれを言うことで何かわかったつもりになることが目眩ましになって問題に集中できない。過去に何度かそういう失敗をして、DP だということは言わないことにした。dp という変数名も自分にとって何も説明していないので使わない。

DP の一語でなく、配る DP、集める DP まで区別できるとまた違うのかもしれないけど、自分はそれらを識別しない。

 @2021-08-15 ARC026-C 蛍光灯 が同じ問題だった。

どちらがどちらと同じと言うかはまあいいや。

 提出 #25085547 (AC / 295 Byte / 269 ms)

速いでそ>「Ruby によるすべての提出」 それ以前に提出が少なすぎる……。

最終更新: 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 メソッドを使うようにしただけ。