最終更新: 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 バージョンと比べて、思ったより短くはならなかったけど速くはある。何より各ステップが単純でバグらせにくいと思う。
この単純さは、旅費が最大になる目的地の候補を予め２つに絞っているところから来ている。すなわち、直径(の１つ)の両端に位置する２つの街。
仮に木の中心がある辺にあるとしよう。すべての街が辺のあちら側かこちら側かに二分される。どの街をスタート地点に選んだ場合でも、中心を経由して、中心から最も遠く半径分だけ離れた街を目指すのが最も高くつく。中心を経由しないパスについては、中心に寄り道をするパスを想定して比較材料にすると、最も高くつくケースより安くなることがわかる。
冷風を送り出すファンの回転数を抑えることで、室温を下げずに平均湿度を従来機に比べ約12％下げる。」 冷やすことが目的ではないけど除湿のために冷房運転をするからこういう制御になるんだけど、結果は室内の温度ムラを生む。除湿運転によりホットスポットができる。そうするとマッチポンプなんだよ。室温がコントロールできていると思うならあとは除湿ではなく送風を頑張るのがいいと思う。実はコントロールできていませんでした(だから暑い)ということが明らかになったりもするだろう。都合のいいことに消費者の多くは室内機のファンの音をエアコンが仕事をしている音だと思っていると思う。■すべての不満は部屋に対してキャパシティに余裕のあるエアコンを選ぶことで解消するのかな、と考えないではない。
最終更新: 2021-11-04T10:11+0900
精進ですよ。おとといあった ABC の F 問題。
コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの２のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。
木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので１本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。
たとえば直径が偶数の時、直径の中心には頂点が１つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に２つあるなら、２つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、２つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は１つ。
たとえば直径が奇数の時。直径の中心には１本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が２つあるなら、２つの辺の中点が本来の……(略)。だから中心は１つ。
色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ２つの頂点を考える)。同じ頂点の先にぶら下がっている２点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ？という話になる。そんなものはない。
ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。
配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が１度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。
８問目の黄 diff AC。これより上は橙が１問だけだから、かなりのレア度なんだ。
ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。
さっき書いた。
木の直径については知っている。(中略)。証明は知らない。
木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の１点を始点に選んで最も遠い頂点を求める１回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。２回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。２回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。
さっき書いた。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。
エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい！(嘘です。調子乗りました)
ボーナス込みの得点合計÷問題数 でソートして効率のいい方から総当たり(打ち切りあり。残りスコアの合計からと得点効率から計算する最小値更新の見込みから)。問題の解き方は問題群単位で全部解くか１問も解かないかスコアを満たせるだけ解くかの３パターンしかない。制約がたいへん控えめなので解法もバラエティに富んでいる印象>Ruby によるすべての提出。と思ったらほとんどがビット全探索で DFS が少々、といった感じ。DP はダメだったか。たしかに、全部解くか残スコア分だけ解くかの２択に対して p 回繰り返すループは、それが無理な制約ではないにしても無駄が多い。A space-separated list of URLs. When the link is followed, the browser will send POST requests with the body PING to the URLs. Typically for tracking.」 もちろん User-Agent たる Firefox はユーザーが望まない動作を行わないオプションを用意してくれるものと信じている。■まじであった。「Firefox 3 で対応が追加、但し既定では有効化されていない (browser.send_pings の設定で隠蔽)。」 けっこう古くからあったみたい。古すぎて、今でもこの設定が参照されているかは要確認だけど。
最終更新: 2021-12-21T16:21+0900
昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は５完６完を狙いたいところなんだけど、ABCD を 17 分４完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか？
こちらが先に解けた。やり方はすぐにわかる。１か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を１つ決めると木に深さという概念が生まれて、根の深さを０にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。
木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。
83 分間合わないサンプル２を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。
しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。３つくらい勘違いポイントがあった。組み合わせを半分(それとも２倍？)扱いしなければいけないのはどういうケースか(同じ深さの２頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。
余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。
愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点１つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。
E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。
最終更新: 2021-09-30T13:08+0900
制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x は 11111 であるかプリフィックスが 111110 であるかのどちらか。f の値ごとに N 以下の範囲にそういう x が何個あるかを数える。桁数を固定すれば数えやすい。提出 #26096008
競プロ典型90問「025 - Digit Product Equation（★7）」の簡単バージョン。
頭の中がぐちゃぐちゃで解けなかった。終了直前の提出がこれ>提出 #26101512 (1 WA)。
とってもくやしいことに、１文字書き換えたら通りましたとさ>提出 #26105189 (AC)。２行目の N==1 を L==1 にしただけ。なんだよもー。もーもーもー。
一応考えたことを。最小化したい最大値の先頭の桁は２で決まっている。その後ろに０から N-1 までの N 個の数を３進数で表記したものをくっつける。これが２から始まる N 個の数。０から始まる N 個の数と１から始まる N 個の数は、桁ごとの制約を満たすようにテキトーに決める。これだけ。なんで書けへんの？ 他の人の提出を見ると tr で 0,1,2 をローテーションするのが簡単そうだった。簡単にできることをすごく難しく考えていた。
驚いたことに、このふがいない有様でレートは上昇しているのである(☞)。どれだけ低いレートに甘んじているかわかろうというもの。
最終更新: 2021-09-23T19:26+0900
昨日の ABC に続いて今日は ARC があった。
昨日と同じく ABC の３完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの？どうなの？)
脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785。
LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。
LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02。
LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。
最初にサンプルの３にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。
次に GCD について。砂で隙間を埋めるように１ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか？
どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が２×N になってもオーダーは変わらないけど、ループを２本に増やすことに無意識の抵抗があるらしい。
残っていた 20 分で愚直解だけ>提出 #25995534。
RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。