Rubyが他の言語に比べてときどき遅くなることがある理由を聞かれたら、私なら「もしも〜だったら」を筆頭の理由に挙げます。 Rubyの実装では、プログラムを実行するときに「もしもこうだったら、ああだったら」を考えるのに多くの時間を費やします。足し算のたびに「オーバーフローしたらどうするか」、メソッドを呼び出すたびに「メソッドがモンキーパッチされていたらどうするか」、コードの1行1行で「トレースが有効にされていたらどうするか」といったことを判断しなければなりません。」 型付けによってプログラマが違反に対するペナルティを引き受けるから、Ruby は高速で突っ走ってくれ、と指示するモードが欲しくなったりする。Ruby で導入されつつある型はそういう用途ではないらしいけど、「シェイプ」が期待に応えるという話。ペナルティはありません。■これも読んだ。「Async Ruby - Bruno Sutic」 すごく楽しみな機能。「
A word of notice: Async does not get around Ruby's Global Interpreter Lock (GIL).」という前置きの解釈がわからないし、なんなら直訳も理解してないけど。共有リソースにアクセスすると全然 async にならないよ、ってことなら想定内だけど、デッドロックしない/させないやり方は想像できない。Fiber についても知らない。最後にこう書かれてるし、サンプルのチョイスもこの通りなので、「
Async's strongest point is scaling network I/O operations, like making or receiving HTTP requests. Threads are a better choice for CPU-intensive workloads, but at least we don't have to use them for everything anymore.」、自分には使い道がないかもしれない。それでも「
but ～」には同意するほかない。
最終更新: 2021-10-26T00:58+0900
D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。
全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。
欠けてる数字を９番目の要素にするのがちょっとした Tips. TLE 解消の決め手にはならなかったんだけど。
現在の状態からありうる次の状態(のうち初出のもの)をすべて候補にするという意味で感覚的に全探索と書いたけど、そういうのは幅優先探索と呼ぶらしかった。
時間は１時間ほど残っていたのに、結果的に１時間と 10 分が AC までに必要だった。
D 問題の TLE×1 と違って全然惜しくない。どこの処理量が膨れ上がるかとソースを眺めてみると、遷移のための辺を逐一処理しているところがダメ。
遷移の方向は A の小さい方から大きい方に決まっているので、A の降順に遷移可能回数を数え、行と列にその回数をメモしておけばいい。今後この行(この列)から遷移先を探すものがあるならメモした回数だけ遷移できますよ、というメモ。A の降順に処理しているから参照したメモはいつでも有効。
ああいや、A の値が等しい別の点が書き込んだメモを参照しないようにだけ注意が必要。この辺の呼吸は珍しくないので心得たものである。
あと 10 分あればなあ。
不要になった処理を消し忘れてた。
レートはちょっとだけ上がってる☞。しかしもっと上がりたかった。
最終更新: 2021-11-23T22:07+0900
精進ですよ。水 diff だけど難しい(まるで水 diff が簡単かのような……)。考えがまとまるまで１日かかった。
隣接２要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。
Ai の値は移動に伴って変化しているように見えるけど、実のところ位置に応じて決まった値をとっているに過ぎない。どういう値をとるかは、最初に位置 i で値 Ai をとっていた、ということで決まる。
A 数列の各要素が位置１でとる値をその要素のポテンシャルと呼ぶことにする。ポテンシャルから要素の位置を逆引きできるようにインデックスを作成しておく。
B 数列をスキャンしながら、要求するポテンシャルを計算し、該当する要素を A 数列の先頭に近いところから貪欲に引っぱってくる。
引っぱってくるに際していくつの要素と位置を交換することになるかは BIT で転倒数を管理することで数える。というか、知る必要があって管理している数字が転倒数と呼ばれている、が順序として正しい。
難しい。これが水 diff ってどうかしてる。ちなみに Swaps の１はこれ>「Swaps」。黄 diff です。解けるまで９か月寝かせました(20191111p01→20200826p01)。２は１日寝かせただけで解けたんだから、妥当なのか？
最終更新: 2021-11-15T21:43+0900
大反省回。未だに ABC で ABC の３完敗退を繰り返していることに驚きを隠せない。今回がそうだしついこの前の ABC219 もそうだった>20210918。ついでに言うと３年以上前の第２回参加回もそうだった☞。まるで成長していない……。戒めとして普段はとばす A 問題から振り返る。
20 年前の自分だったら N の常用対数から N の桁数を求めてくっつける 0 の数を決定していた。
だけどとある WSH 関連の掲示板で、十分な数の 0 をくっつけてから必要な文字数だけ切り出す方法を知った。
他の人の提出を見ると printf かそれに類するメソッドを使うものが多かった。Ruby で最初に提出した人は rjust を使っていた。目的にぴったりのメソッド(rjust)がある以上、それを使うのが最善だった。
こういうこと。
L = lambda{|n| Math.log10 n } # 正整数 n の常用対数
D = lambda{|n| L[n].floor+1 } # 正整数 n の桁数(10進表記)
p [D[99],L[99]] #=> [2, 1.99563519459755]
p [D[100],L[100]] #=> [3, 2.0]
p [D[101],L[101]] #=> [3, 2.0043213737826426]
学校で対数を習っても理解が伴わないと計算問題はできてもこういう風に実用できなかったりする。Project Euler の 62 問目を二重ループで解いたりもする>20110308p01.02。
実はまだよく分かっていないのは自然対数の底 e。なんだかこれを底にすることで累乗が掛け算になったり曲線が直線になったりして性質を変えずに扱いやすくなったりするらしいんだけど、そういうのは(文系学部に分類されるらしいことを少し前に知って驚愕した)経済学部の人に任せておきたい。
コメントのしようがない。スクリプトを読んで。
制約が小さいので愚直にシミュレーションをすれば良い。
解答を作成するのに 20 分かけたのが良くなかった。出力フォーマットを勘違いしていて、求められているのが順位で並べた人番号だったのに、人番号順に順位を表示しようとして余計な手間をかけ、余計な手間を実装するのにもやけに手間取ってしまった。
解けなかった。シンプルな DP。直前の項がとった値ごとに場合の数が記録してあれば、現在の項において取り得る値と場合の数が数えられる。それがわかっていて解けなかった。
もうね、「なんでなん？」という感想しかない。これが違うなら正解が正解ではないと言い張ることしかできない。
制約の下限が 0 なのは知っていた。知っていたしそのせいで Range の終端が -1 になることがあるのもわかっていたが、終端が始端よりも前にある「空の Range」で切り出した部分配列が、「空の配列」ではないことがあるだなんて想像だにしなかった。これは Ruby の罠である。こういうことだ。
range1 = 0..-1 # これで WA range2 = 0...0 # これで AC p range1.size #=> 0 p range2.size #=> 0 array = *0..9 p array[range1].size #=> 10 p array[range2].size #=> 0
配列の切り出しにおいて Range は単なる添字のペア [0,-1] として扱われている。Range としてのアイデンティティを奪われている。この仕様を知らなかったわけではない。ただ、認めがたい仕様なので自分では絶対に使わない仕様なのであり、意識の外だった。
D 問題を諦めたのに E 問題もコンテスト中の提出は叶わなかった。
やることははっきりしている。できるかどうかは別としてやるだけの問題。
「木において辺とは頂点集合を左右に分けるもの」だと前回の ABC に関連して書いたばかり。ある辺について注目したとき、A_i と A_{i+1} が異なる集合に属していれば A_i から A_{i+1} への移動に際してこの辺を通るのでカウント +1。
A_1 から A_2,..., A_m へと移動するとき辺ごとに何回通るかが数えられたら、今度は R−B=K を満たすような塗り方(辺の選び方)を数える。一度も通らない辺は青でも赤でもどっちでもいいので除外してあとで掛け合わせる。
原因は想像だけど、頂点集合の管理に 1000 ビットのビットフラグ×1000 を使って TLE。後半で謎の DP をして WA。
頂点集合の管理に UnionFind を使うことを思い出した。後半の DP はシンプルになって、辺を赤く塗った場合と塗らなかった場合を一緒くたにハッシュ表に詰め込むだけ。
1050 Byte は書き過ぎかなと思ったけど、他の Ruby での提出も軒並み 1001 Byte, 2162 Byte, 1019 Byte, 1776 Byte だったから別に突出してはいなかった。
前々回の ABC で見たのでこれを全方位木 DP と呼ぶことを知っている。そのときの経験でとりあえず根をとっかかりにすればいいことも知っている>20210928p01.01。根っこの特殊性は親がないことで、(子から親へ処理を積み上げているにも関わらず)親を参照しなければ求められない答えも、根に限れば求まる。そうすれば根を親に持つ子の答えも求まる。以下同様。
木 DP は処理の流れさえできあがれば、葉という一番単純で考えやすいところから差分で処理を積み上げていくと答えになるのでやりやすい。差分の部分の式が難しいことがあるし(20210909)、子のマージが難しいこともあるけど。
順調にジャッジが進んで行っていたのに最後の最後で次の一群のテストケースに阻まれた(06_n_eq_2_00.txt, 06_n_eq_2_01.txt, 06_n_eq_2_02.txt, 06_n_eq_2_03.txt, 06_n_eq_2_04.txt)。AC は近い。あそこが nil になりそうだなーと疑っている部分はある。
ABC が 12 時間のコンテストなら ABCDEF の６完も不可能ではない！(慰めはいらねーよ)
ゴルファー以外では Ruby で唯一の AC だった tinsep19 さんの提出 #26477920 を読んだ。
どうやら参照すべき日記を間違えていた。先月の 28 日(20210928p01.01)ではなくて、今月の 4 日(20211004p01)を参照すべきだった。全方位木 DP ではなく木の直径を解法とすべきだった。そっちの方が簡潔になるから。
関連問題である ARC022-C「ロミオとジュリエット」のスライドに２通りの解法が書いてあったらしいのをある参加者のブログで読んでいたが、わざわざややこしそうな全方位木 DP で木の直径を求める方法を知りたいとは思わなかったのだった。
知らずに実装していたし、知っていたのに(理解が浅くて)簡潔な手法を選べなかった。
振り返れば E,F がやるだけの問題だったこと、全方位木 DP、木の直径、どれも前回と前々回の ABC を彷彿させるものだった。どちらも復習はばっちりだった。その結果が３完とは泣かせる。
DFS ２回で直径を求めるバージョン。全方位木 DP バージョンと比べて、思ったより短くはならなかったけど速くはある。何より各ステップが単純でバグらせにくいと思う。
この単純さは、旅費が最大になる目的地の候補を予め２つに絞っているところから来ている。すなわち、直径(の１つ)の両端に位置する２つの街。
仮に木の中心がある辺にあるとしよう。すべての街が辺のあちら側かこちら側かに二分される。どの街をスタート地点に選んだ場合でも、中心を経由して、中心から最も遠く半径分だけ離れた街を目指すのが最も高くつく。中心を経由しないパスについては、中心に寄り道をするパスを想定して比較材料にすると、最も高くつくケースより安くなることがわかる。