最終更新: 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 バージョンと比べて、思ったより短くはならなかったけど速くはある。何より各ステップが単純でバグらせにくいと思う。
この単純さは、旅費が最大になる目的地の候補を予め２つに絞っているところから来ている。すなわち、直径(の１つ)の両端に位置する２つの街。
仮に木の中心がある辺にあるとしよう。すべての街が辺のあちら側かこちら側かに二分される。どの街をスタート地点に選んだ場合でも、中心を経由して、中心から最も遠く半径分だけ離れた街を目指すのが最も高くつく。中心を経由しないパスについては、中心に寄り道をするパスを想定して比較材料にすると、最も高くつくケースより安くなることがわかる。