脳log[AtCoder: 2020-07-01～]

最終更新: 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のブログ」という思考の跡が見えるブログ記事の方が自分には有用となる理由。アルゴリズム格言に期待する理由。

最終更新: 2020-06-15T20:02+0900

♪ [AtCoder] AtCoder Beginner Contest 164／E 問題 Two Currencies

日付のあたりに書いた通り解説PDFを読んで実装した。だけどあれ全然答えじゃないね。Chokudai さんのブログで以前読んだような、ちょっとひねってあるのをいかにして典型問題に落とし込むかというタイプの問題だったらしい。ある意味そこまで含めて典型では。でも一度も実装したことのないパターンだから「(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。」とだけ書かれても、～を状態とするってどういうことですか？

 提出 #12489199 (TLE / 2206 ms / 19760 KB)

Wikipedia の「ダイクストラ法」を読みながら雰囲気でPDFに書いてあった方針で実装しようとした。一応答えは出たがサンプル入力ですら一瞬の間を感じさせる激遅スクリプト。

N 個の頂点と銀貨の枚数を組み合わせて状態にするといっても、訪れなければいけない地点は依然として N 個のままなわけで、そのあたりの状態を集約する手つきが具体化できなかった。最終的に提出したスクリプトで「すべての地点を一度でも訪れた時点で完了」としたところとか、「銭なしの再訪に用なし」とコメントしたあたりがそうだと思うんだけど。

苦しんで何度か書き直すうちに原型を失いつつもすっきり書けて、プロファイルをとりながらの実行もすっきりだったから「どうだ！」と提出したら、AC の中１つだけが TLE で脱力。これ以上は無理ですよ。

この段階で他の人の提出を見た>「すべての提出 - AtCoder Beginner Contest 164」。

Ruby での全提出は１ページに収まるほどで、AC していたのは２人だけ。TLE 仲間の提出を覗いてみれば、自分が TLE になった入力(とサンプル)だけ AC していたりして、line_2.txt が何と癖の強い入力であることか。

 提出 #12498094 (AC / 205 ms / 14528 KB)

ダイクストラ法に立ち返らないといけないかと思っていたが、diff をとらないと判らないレベルのチューニングでなんとかなった。不思議。

要修正その１

M.times.map の .map がいらない。

.each の短縮形として .map と書くことがあるみたいだけど、.times (ブロックを受け取る)があるのでここではただの無駄。定数 E で map を受けていたときのなごり。

要修正その２

PQ#deq の変数名 max は min の誤り。

プライオリティキューが必要になるたびにこのとき(20190916p01)の max-heap を使った実装を書き換えて使ってるせい。必要になるのはほぼ min-heap。符号を反転させてそのまま使うのと手間はどっこいどっこい。

 ところで、Python (3.8.2) で今一番速いのがこれ>提出 #12430772 (140 ms)

すっごく読みやすいんだよなあ。何をやっているのか手に取るようにわかる(笑)。配列総なめが嫌だからって冗長なカウンター変数を用意するところまで。

自分に欠けていた工夫が２つあって、

1. ある頂点から出る辺を予めソートしておいて、除外条件に一度引っ掛かれば以降の辺をまとめて無視してる。
2. 効果のないちまちました両替をひとまとめにしてる。(ソートした辺がここでも役に立っている)

特に２番目は効果が大きいんじゃないかなあ。キューへの出し入れがボトルネックだから、エンキューをひとつ節約するごとにそこから波及する複数のエンキューが節約されるのは大きい。

それはそれとして、Python は AC だけに限っても５ページの提出があるのがうらやましい。傾向として判で押したように似たような提出が多くはあるが。理由のひとつはヒープ(データ構造)とかダイクストラ法とか、名前のついたアルゴリズムが簡単に利用できるところにある。

 Ruby (2.7.1) のこの提出>提出 #12467639

読めない記述がある。この行

  (v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]

演算子(に見えるがメソッド)をドット記法で呼び出せる(それが結合規則を変えるのでゴルフに使える)というのは読んだことがあって、たとえば 1&3 と 1.&(3) は同じ意味になる。でも &.& をどう解釈すればよいか。SM はただの数値変数だからブロック引数化の & ではないと思う。

他にもアロー記法だとか、暗黙のブロック変数(_1, _2 とか)だとか、Ruby 2.7 を読むには知識が足りない。ローカルにインストールしている Ruby 2.5 ではまだ使えない記法だったりする。まだ gem コマンドを一度も使ったことがないから、デフォルト添付ライブラリ(prime とか)の gem 化は歓迎できない？。

ブロック変数には悩ましいところがあって、.map(&f) とか .map(&:to_i) とか書けるときには積極的に書いていきたいんだけど、.to_i ではなく .to_i(2) を適用したくなると途端に .map{|_|_.to_i(2)} と書かなければいけなくなる。.to_i に 2 (と self)を予め束縛した関数がサッと(記述コストと実行コストなしに)利用できるといいんだけど、なかなかそうもいかないらしく、とりあえず .map{_1.to_i(2)} と書けますよ、ということ。たぶん。まだ試したことない。

 「メソッド呼び出しで `.' の代わりに `&.' を使うことができます。この形式でメソッドを呼びだそうとすると、レシーバが nil の場合は以下のように働きます。」

• 引数の評価が行なわれない
• メソッド呼び出しが行われない
• nil を返す

&.& が何だったかと言えば、nil テストを含んだ & 演算だったと。Swift とか C# にあるやつじゃない？ どっちも使わんしよう知らんけど。

 提出 #12550661 (AC / 154 ms / 14520 KB)

51 ms 縮まったけど本質的な改善ではないと思う(配列４とか比較が雑で適応が限られるし、ない方がいいかも)。シンプルさも失われていいことない。しかも Python (140 ms) に負けてる！ Ruby のバージョンが 2.3 から 2.7 になって、実行前のオーバーヘッドが 40 ms ほど大きくなったと思うんだよなあ(それでも勝ちたい。ユーザー数で負けても質で勝ちたい)。

 参考にされた！>提出 #12916854 (146 ms)

嬉しい！ 自分で解釈して手を動かして理解してる！ 立派！ 自分で好き勝手書くより他人の考えをトレースする方が難しいものよ。

タイムが縮んでるのはホットスポットである PQ#up_heap (PriorityQueue#update_heap_to_up) で配列アクセスを減らしてるからなんだろうか。キューが長くなるほど効果があると思う。

あと自分は意味まとまりのある変数群を一行で定義するために多重代入を多用するんだけど、実は字数が減るわけではないし、多重代入式に対応する配列値が作り捨てられているとしたら、もったいないことをしてる。

地味に変数の定義位置をずらして無駄な計算を減らしたりもしてる。自分は変数の定義をひとつにしたいがために効果のない値([0,0] とか)を使用して効果のない加算を実行してたりするんだけど、贅沢ではある。関連>20181029。

 改善点みっけ

(自分の提出だよ)

	z, y = ２[v]+a, ３[v]+a # z < y
	if z < s
		c, d = s < y ? X[v][s-a,３[v]] : [0,0]

X[v] が返す関数が受け取る引数２つ(s-a と ３[v])はその差だけに意味があるから、両方に a を足して、X[v][s,y] とすると引き算１つと配列アクセス１つが省略できる。そもそもが引数が２つある冗長性から生じた無駄であるな。

こういう楽しみがあるのはスクリプトならではなんだよなあ。C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。そこに性能を犠牲にせずに読みやすい表記を追求する余地があるとも見られるんだけど。

 即セルフツッコミ「C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。」

もう一度asmコードをよく読むと不要なはずの配列の初期化が走ってる模様. デフォルトcstrは空のはずなんだけどと自分のコードを見直すと、FpDblクラスだけ配列の初期化が入っていた.

うっかりいれちゃっていた模様. 削除するとgcc-7.5で13%高速化. おおこいつのせいだったのか. それでもclang-8より4%ほど遅いけど気がすっきりした. でも配列の初期化で1割変わるというのは(clangは速いだけに)何か変なことしてるのかな.

プログラマに指示されたらコンパイラは無視できない(こともある？ clang の場合をどう解釈する？)。結果に影響しない表面上はささいに見える違いが思わぬペナルティを生むことも。

 実装比較。この件>>20200428p01.07

• 提出 #13001464 (1349 ms) 自分のプライオリティキュー実装を利用した richvote さんの提出。
• 提出 #13001205 (1273 ms) 自分のプライオリティキュー実装を基にした？ yappy0625 さんの実装を利用した richvote さんの提出。

プライオリティキューの実装が違うだけで、メインループは共通して richvote さんのオリジナル。

richvote さんの提出は、自分が最初唯一の TLE を食らった line_2.txt という入力が際立って他のケースより速いため、明らかに異なる部分に着目して探索の優先順位を決めている。

それはさておいて、俺の目には２つのプライオリティキュー実装に違いがあるとは見えないんだけど、俺の書き方の方が遅いという傾向が間違いなくあるようだ。

loop{} と書くより while 0; end と書く方が速いというように、気をつけておくと得する書き方がまだあるみたい。だけどわからん。

 多重代入と代入

require 'benchmark'

N = 10_000_000
Benchmark.bm{|x|
	x.report('多重'){ N.times{ a,b,c = 1,2,3 } }
	x.report('代入'){ N.times{ a=1;b=2;c=3 } }
}

これを Ruby 2.5 で実行してみた。

> ruby25 a.rb
       user     system      total        real
多重  1.591000   0.000000   1.591000 (  1.585992)
代入  0.967000   0.000000   0.967000 (  0.969697)

多重代入遅いなあ。(bm メソッドを bmbm に変更してリハーサルを行っても同じ結果)

あと最近驚いて、確かめてみたら Ruby 1.8 の昔から一貫して同じ挙動だったんだけど、多重代入の評価順って、単純に右辺から左辺とか、カンマで区切られた左から右ではないみたい。次のスクリプトの実行結果に驚いた。

i, a = 0, [0,1,2] # 準備
i, a[i] = 2, i # どうなる？
puts "i=#{i}; a=#{a.inspect}" #=> i=2; a=[0, 1, 0]

最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？

多重代入は遅くて時々評価順が難しい、というのが現在の評価。

最終更新: 2020-05-06T23:27+0900

♪ [AtCoder] パナソニックプログラミングコンテスト2020／C 問題 Sqrt Inequality

コンテストの配点を見るに ABC 互換。B is for Beginner.

 まず間違えた。「提出 #10843998」

入力が整数なので戻り値が Float になる Math.sqrt は使いたくなかった。ふわふわした浮動小数点よりかっちりした固定小数点が好き。三角不等式みたいな高校時代に知ったような単語が思い浮かんだが関係するかは知らない。両辺を二乗して不等号が維持されるかどうかが気になった。すべてルート付きで正の実数だから大丈夫。

で、１つだけ WA(Wrong Answer)。

こういうことだ。ルート付きの元の不等式が成立するとき、両辺を二乗した不等式も成立する。でも逆は？ 二乗した不等式が成立することは提出したスクリプトで確認した。そのときルート付きの不等式はどうだ？

数学とは便利なもので、イメージが湧かなくても途中の式変形で同値関係さえ確認していけば答えにたどり着いた。実は二乗する操作を２回やっていて、２回目のチェックが疎かになっていた。「提出 #10855551」

とっても高校生向けだと思う。大学入試で同値関係の証明を求められるもんね。そのとき一方通行では道半ば。

最終更新: 2020-05-06T23:27+0900

♪ [AtCoder] AtCoder Beginner Contest 145／D問題 Knight

階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。もちろん階乗を計算しきってから余りを求めるというのは実行制限に引っかかるので無理。

 #AtCoder から見つけたヒント

モジューラ逆数っていうのがあるんですね、これはすごい pow(down,mod-2,mod) 昨日のD問題逆元の計算どうやればいいのかわからなくて1時間くらい経ってしまった

AtcoderのABC145D問題しっかり理解して頭の中整理してすっきりかけた気がする。Python3です。 pic.twitter.com/Dcs3IfoZ95

mod って演習込みでイチから習った記憶がない。「割った余りですよ」以上の理解がない。キーワードすら知らなくてググりようがない。

 キーワード

• 「逆元 - Wikipedia」
• 「モジュラ逆数 - Wikipedia」
• 「ユークリッドの互除法 - Wikipedia」
• 「ベズーの等式 - Wikipedia」

Ruby には Python と違って「冪剰余 - Wikipedia」が求められる関数が用意されていないみたいなので(※補足訂正)、拡張ユークリッド互除法を使う方の求め方を Wikipedia(ja) からコピペ実装した>https://atcoder.jp/contests/abc145/submissions/8508807。明日には理解できないとしても「モジュラ逆数」というものの存在くらいは覚えておきたい。

 現在 Ruby で最速の提出(55 ms)>提出 #8501110 - AtCoder Beginner Contest 145

速いからには変わったことをしてる。derive_inverse メソッドが理解できない。法のビットを利用しているみたい。理解できないのは本質を掴んでいないから、演繹が働かないからだろう。「冪剰余#さらなる最適化 - Wikipedia」を実装してるのだろうか、雰囲気的に。

pow メソッドを使って実装された derive_inverse がコメントアウトして残されている。

 Ruby で冪乗余

試したら Ruby 2.5 には冪乗余が求められる Integer#pow メソッドが用意されていた。2.6 の「数値関連のメソッドを実際に定義しているクラス一覧」には載ってなかったんだよなあ。Ruby 1.9 時点では pow メソッドはなかった。AtCoder の 2.3 でもまだないかもしれない。

 方法色々

つらつら眺めてると、require 'matrix' して lup.solve で勝手に方程式を解いてもらえるとか、require 'openssl' すると mod_inverse が利用できるとか、知らない方法が色々あるもんだ。でも LUP 分解が解らなければ見ても使うべきときが判らないし、知っても使えない。『[単行本] 平岡 和幸, 堀 玄【プログラミングのための線形代数】 オーム社』は中座してるし、『[単行本] ロナルド・L. グレアム, オーレン パタシュニク, ドナルド・E. クヌース【コンピュータの数学】 共立出版』もちょっと眺めただけ。若いうちに学校で広く浅くでも詰め込んでおくべきなんだよ。基礎がないと何も積み上がらない。