脳log[AtCoder: 2021-12-10～]

最終更新: 2022-01-03T13:27+0900

♪ [AtCoder] JOIG 2021 過去問／F 問題 デジタルアート (Digital Art)

D と E についてはここに書いた>20211206。A,B,C については ABC-C までの難易度帯という感じで特に何ということもなく解けたので書いていない。最後に F 問題が残っていた。

 考え方

色ごとにその色を完全に覆い隠せる矩形を考える。矩形は左上座標と右下座標で特徴付けられる。面積 S を超えない範囲でどのような矩形を選べばできるだけ多くの色を隠せるだろうか。

 制約

グリッドの一辺は最大 1000 なので、グリッド上の点は最大 100 万個。いくら面積 S を超えない範囲でできるだけ大きな矩形のみを考えるとしても、グリッドから２点を選ぶ組み合わせは１メガ×１メガに近い数になる。これは制限時間１秒で扱える数ではない。

色数の上限が 256 に抑えられている。256 の３乗は約 1600 万だから、Ruby の場合、定数倍が 1/2 とかなら３乗がなんとかなるかな、という雰囲気。

 どうやる？

二次元累積和であるとか「Range Set Query」が思い浮かんだけど、どうにも(知っている)定型の処理に当てはまらない。

矩形の左上座標と右下座標を探索することが許されるなら、色を、その色を囲う左上座標と右下座標のそれぞれでソートしておくことで、うまく探索してマッチングして数を数えられると思う。

色を特徴付ける矩形の左上角と右下角の組み合わせを選ぶ 256 の２乗通りでは答えを漏らすのでよろしくないが、４辺を選ぶ 256 の４乗通りは許されない。困った。

 どうした

矩形の縦の長さを固定して横方向に尺取りをした。

 提出 #27751046 (75/100 点 / TLE×9)

最後の小課題９のケースもいくつか通ってるので惜しいのかと思ったけど、実は遅いケースは 10 秒とかそこらかかっていた。

４重ループです。上辺について 256 通り。底辺について 256 通り。右辺と左辺について尺取りが 256×2 ステップ。その最深部で矩形に出入りする色が 256 個。だめじゃん。

 提出 #27751294 (TLE×9)

定数倍の改善。Array#minmax の呼び出し回数を節約した。650 ms が 350 ms になるレベル。

 提出 #27752007 (TLE×9)

定数倍の改善。上辺と底辺に関する第一第二ループを Array#repeated_combination(2) で横着せずに、尺取りっぽく遷移して重複する処理を減らした。550 ms が 450 ms になることもあるし、変わらないこともある、という変化。

 提出 #27772767 (TLE×1)

ついに来た！ TLE は残り１ケース。

改善したのはやっぱり定数倍だけど、上辺に対する底辺の選び方を、尺取りの幅でグループ化して最も高さが大きくなるものに代表させることで、尺取りの回数が大幅に減った。

もうひとつ。ループをイテレータではなく while 文で書き直すことで Ruby の場合かなり速くなるんだけど、それに加えて、答えの候補を求めるループの途中で暫定的な答えにアクセスできるようになったのも大きかった。それにより答えを更新する可能性がない場合に最内ループをスキップすることができた>or ain.size<=max。

 提出 #27797091 (100 点 / 935 ms)

これも定数倍の改善。インチキをした。底辺を尺取りの幅でグループ化する部分が

i1s = I1s.group_by{|i1| i1<i0 ? 0 : [S/(i1-i0+1),W].min }

だったところを、次のようにした。

I1s.shift while I1s[0]<i0
i1s = I1s.chunk{|i1| [S&1|S/(i1-i0+1),W].min }.map{|_,as| as[-1] }

S&1| ってなんですかね？

とにもかくにも、(１差の偶数と奇数を同一視することで)４重ループのうちの２番目のループの回数が節約できたのはとっても効いた。

想定解法は３乗もしくは３乗＋logとかのもっとスマートなアルゴリズムを使っているのだろうか。それとも Ruby は想定外だからさっさと Crystal や C++ で出し直すべき案件だったのだろうか。3 MiB オーバーの入力ファイルを読み込むのにも、つまりはスクリプトの１行目の処理を終えるまでにということだけど、１秒しかない時間のそれなりの割合を使っているのだよね。

 デジタルアート解説 (PDF)

想定解法は上辺と底辺を固定しての尺取りだった。やり方は間違っていなかった。その計算量が O(HW+A^3) だというのがわかっていなかった。実際は A^3 でできていたのか、それとも何かおかしなことをして A^4 にしてしまっていたのか、どっちだろう。

ちょっとおかしなことをしていた。AC 提出の最内ループのこの部分。

	ain.reject!{|wj0| wj0<=j1 }

尺取りから出て行く色を見つける部分で、尺取りの中にある色の全体を都度スキャンしていた。

尺取りの右がある座標に至ったときに入る色と、尺取りの左がある座標に至ったときに出る色は、それぞれの合計が最大で 256 個であり、一度の尺取りを通して合わせても 512 個という定数にしかならない。ある座標で入る色と出る色をそれぞれリストしておいて、ある座標に至ったときにそれらの色が尺取りの中にあるかどうかを確かめるべきだった。

このように>joig2021_f.rb27。あるいは最初に TLE をもらった提出 #27751046 のように>20211210p01.05。

だけどたぶんこれは TLE になる(OS が違うけどローカルで測定している)。定数倍の影響が大きすぎるのではないか。最後の TLE をクリアしたとどめの一手だって、尺取りのステップ数を随時削減することによる定数倍の改善だった(S&1| だけでは足りなかったのだ)。やはり Ruby で満点を取ることは想定されていないと思う。

日本情報オリンピック 第2回女性部門（JOIG 2021/2022） から「情報オリンピックに初めて参加する方は、出題形式・勉強法・講習会などに関する情報をまとめた「情報オリンピックの勉強法」をご覧ください」とリンクされていた(JOIの)ページから。

JOI 本選

本選は 2 月に実施されていて、4 時間で 5 問に取り組みます。上位者は春合宿に招待されます。

本選では二次予選と比べて難しいアルゴリズムの知識や、そのアルゴリズムを与えられた課題に適用させるための高度な発想力が問われます。

JOI 春季トレーニング合宿 (春合宿)

春合宿は IOI 日本代表を決めるための代表選抜会です。3 月に実施されていて、4 日間連続で毎日 5 時間の競技に取り組みます。上位 4 人は IOI 日本代表として派遣されることになります。

なお、春合宿で使えるプログラミング言語は C++ のみです

本選の後に春合宿があり、「なお、春合宿で使えるプログラミング言語は C++ のみです。」 そうなのね。

最終更新: 2021-11-12T21:42+0900

♪ [AtCoder] AtCoder Beginner Contest 226／E 問題 Just one

解けなかった。

 提出 #27107258 (WA×9 / AC×24)

これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が８の字になっていたりして輪っかが１つではないケース。

しかしそれをどうやって検出するのか解らなかった。

 提出 #27118298 (AC)

これはコンテスト終了後の提出。さっきの WA 提出では UnionFind で閉路の検出(だけ)をしていたのだけど、もうちょっと細かく、ノード数と辺の数の両方がわかるように記録をつけた。

辺の数がノード数より１だけ小さい連結成分は木であり、辺の数はこれが最小。辺の数とノード数が同じ連結成分はループが１つとオプションで突起をいくつか持っている。辺の数がノード数より多い連結成分は複数のループを持っている。

題意を満たせるような連結成分は３種のうちの１つだけ。他の２つが存在すれば答えはゼロだし、適合する連結成分のみが A 個あったなら答えは 2.pow(A,998244353)。

ここまで考えがまとまるのに２時間かかってるんだよなあ。

 なもりグラフ

なんか「なもりグラフ」という名前があるらしかった。調べようとしたらゆるゆりの人と名前がかぶってて検索性が悪かったのだけど、別に間違ってはいなかった。なもりを検索してなもりが見つかるのは当然。

chokudai(高橋 直大)🍆@chokudai

F問題の由来です。（N頂点N辺の連結なグラフを「なもりグラフ」と呼ぶ人がいるのもこれが理由です。） https://t.co/saSTvA1lep

F 問題って、AGC の F 問題「Namori」じゃないですかー(やだー)。赤 diff の精進は 10 年後も手つかずの見込みですから。

これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が１つあるだけだけど、10 年後は。

最終更新: 2021-10-26T00:58+0900

♪ [AtCoder] AtCoder Beginner Contest 224／D,E

D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。

 D 問題 8 Puzzle on Graph

全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。

 提出 #26768646 (TLE×1 / over 4 秒)

 提出 #26770107 (AC / 2275 ms)

欠けてる数字を９番目の要素にするのがちょっとした Tips. TLE 解消の決め手にはならなかったんだけど。

現在の状態からありうる次の状態(のうち初出のもの)をすべて候補にするという意味で感覚的に全探索と書いたけど、そういうのは幅優先探索と呼ぶらしかった。

 E 問題 Integers on Grid

時間は１時間ほど残っていたのに、結果的に１時間と 10 分が AC までに必要だった。

 提出 #26776942 (TLE×18)

D 問題の TLE×1 と違って全然惜しくない。どこの処理量が膨れ上がるかとソースを眺めてみると、遷移のための辺を逐一処理しているところがダメ。

遷移の方向は A の小さい方から大きい方に決まっているので、A の降順に遷移可能回数を数え、行と列にその回数をメモしておけばいい。今後この行(この列)から遷移先を探すものがあるならメモした回数だけ遷移できますよ、というメモ。A の降順に処理しているから参照したメモはいつでも有効。

ああいや、A の値が等しい別の点が書き込んだメモを参照しないようにだけ注意が必要。この辺の呼吸は珍しくないので心得たものである。

 提出 #26781610 (AC / 1230 ms)

あと 10 分あればなあ。

 提出 #26786787 (AC / 708 ms)

不要になった処理を消し忘れてた。

レートはちょっとだけ上がってる☞。しかしもっと上がりたかった。

最終更新: 2021-11-23T22:07+0900

♪ [AtCoder] AtCoder Regular Contest 120／C 問題 Swaps 2

精進ですよ。水 diff だけど難しい(まるで水 diff が簡単かのような……)。考えがまとまるまで１日かかった。

 問題の操作

隣接２要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。

1. ある要素 Ai を右に(左に)いくつか移動する。
2. たとえば右に５移動するなら、移動先の値は Ai-5 になる。
3. たとえば右に５移動するなら、飛び越された５つの要素が、移動先に空きを作るためと移動元の空きを埋めるために、１つずつ左に移動している。
4. 左に１移動した５つの要素は値を +1 する。

 ポテンシャル

Ai の値は移動に伴って変化しているように見えるけど、実のところ位置に応じて決まった値をとっているに過ぎない。どういう値をとるかは、最初に位置 i で値 Ai をとっていた、ということで決まる。

A 数列の各要素が位置１でとる値をその要素のポテンシャルと呼ぶことにする。ポテンシャルから要素の位置を逆引きできるようにインデックスを作成しておく。

 B 数列

B 数列をスキャンしながら、要求するポテンシャルを計算し、該当する要素を A 数列の先頭に近いところから貪欲に引っぱってくる。

引っぱってくるに際していくつの要素と位置を交換することになるかは BIT で転倒数を管理することで数える。というか、知る必要があって管理している数字が転倒数と呼ばれている、が順序として正しい。

 提出 #26732769 (AC / 561 Byte / 491 ms)

難しい。これが水 diff ってどうかしてる。ちなみに Swaps の１はこれ>「Swaps」。黄 diff です。解けるまで９か月寝かせました(20191111p01→20200826p01)。２は１日寝かせただけで解けたんだから、妥当なのか？

最終更新: 2021-11-15T21:43+0900

♪ [AtCoder] エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）

大反省回。未だに ABC で ABC の３完敗退を繰り返していることに驚きを隠せない。今回がそうだしついこの前の ABC219 もそうだった>20210918。ついでに言うと３年以上前の第２回参加回もそうだった☞。まるで成長していない……。戒めとして普段はとばす A 問題から振り返る。

 A - Four Digits

20 年前の自分だったら N の常用対数から N の桁数を求めてくっつける 0 の数を決定していた。

だけどとある WSH 関連の掲示板で、十分な数の 0 をくっつけてから必要な文字数だけ切り出す方法を知った。

 提出 #26434564 (AC / 25 Byte)

他の人の提出を見ると 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。なんだかこれを底にすることで累乗が掛け算になったり曲線が直線になったりして性質を変えずに扱いやすくなったりするらしいんだけど、そういうのは(文系学部に分類されるらしいことを少し前に知って驚愕した)経済学部の人に任せておきたい。

 B - Failing Grade

コメントのしようがない。スクリプトを読んで。

 提出 #26437560 (AC / 63 Byte)

 C - Swiss-System Tournament

制約が小さいので愚直にシミュレーションをすれば良い。

解答を作成するのに 20 分かけたのが良くなかった。出力フォーマットを勘違いしていて、求められているのが順位で並べた人番号だったのに、人番号順に順位を表示しようとして余計な手間をかけ、余計な手間を実装するのにもやけに手間取ってしまった。

 提出 #26449288 (AC)

 D - Between Two Arrays

解けなかった。シンプルな DP。直前の項がとった値ごとに場合の数が記録してあれば、現在の項において取り得る値と場合の数が数えられる。それがわかっていて解けなかった。

1. 提出 #26458829 (WA×15)
2. 提出 #26459583 (WA×15)
3. 提出 #26461168 (WA×15)
4. 提出 #26493159 (WA×15) 一夜明けて今日も WA

もうね、「なんでなん？」という感想しかない。これが違うなら正解が正解ではないと言い張ることしかできない。

 提出 #26493304 (AC) Range を等価な Range で置き換えました。

制約の下限が 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 としてのアイデンティティを奪われている。この仕様を知らなかったわけではない。ただ、認めがたい仕様なので自分では絶対に使わない仕様なのであり、意識の外だった。

 E - Red and Blue Tree

D 問題を諦めたのに E 問題もコンテスト中の提出は叶わなかった。

やることははっきりしている。できるかどうかは別としてやるだけの問題。

「木において辺とは頂点集合を左右に分けるもの」だと前回の ABC に関連して書いたばかり。ある辺について注目したとき、A_i と A_{i+1} が異なる集合に属していれば A_i から A_{i+1} への移動に際してこの辺を通るのでカウント +1。

A_1 から A_2,..., A_m へと移動するとき辺ごとに何回通るかが数えられたら、今度は R−B=K を満たすような塗り方(辺の選び方)を数える。一度も通らない辺は青でも赤でもどっちでもいいので除外してあとで掛け合わせる。

 提出 #26470241 (WA×4 / TLE×3 / AC×37) 昨晩の提出

原因は想像だけど、頂点集合の管理に 1000 ビットのビットフラグ×1000 を使って TLE。後半で謎の DP をして WA。

 提出 #26494106 (AC / 1050 Byte / 183 ms)

頂点集合の管理に UnionFind を使うことを思い出した。後半の DP はシンプルになって、辺を赤く塗った場合と塗らなかった場合を一緒くたにハッシュ表に詰め込むだけ。

1050 Byte は書き過ぎかなと思ったけど、他の Ruby での提出も軒並み 1001 Byte, 2162 Byte, 1019 Byte, 1776 Byte だったから別に突出してはいなかった。

 F - Expensive Expense

前々回の ABC で見たのでこれを全方位木 DP と呼ぶことを知っている。そのときの経験でとりあえず根をとっかかりにすればいいことも知っている>20210928p01.01。根っこの特殊性は親がないことで、(子から親へ処理を積み上げているにも関わらず)親を参照しなければ求められない答えも、根に限れば求まる。そうすれば根を親に持つ子の答えも求まる。以下同様。

木 DP は処理の流れさえできあがれば、葉という一番単純で考えやすいところから差分で処理を積み上げていくと答えになるのでやりやすい。差分の部分の式が難しいことがあるし(20210909)、子のマージが難しいこともあるけど。

 提出 #26495540 (RE×5)

順調にジャッジが進んで行っていたのに最後の最後で次の一群のテストケースに阻まれた(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 になりそうだなーと疑っている部分はある。

 提出 #26495783 (AC / 602 Byte / 1310 ms)

ABC が 12 時間のコンテストなら ABCDEF の６完も不可能ではない！(慰めはいらねーよ)

ゴルファー以外では Ruby で唯一の AC だった tinsep19 さんの提出 #26477920 を読んだ。

どうやら参照すべき日記を間違えていた。先月の 28 日(20210928p01.01)ではなくて、今月の 4 日(20211004p01)を参照すべきだった。全方位木 DP ではなく木の直径を解法とすべきだった。そっちの方が簡潔になるから。

関連問題である ARC022-C「ロミオとジュリエット」のスライドに２通りの解法が書いてあったらしいのをある参加者のブログで読んでいたが、わざわざややこしそうな全方位木 DP で木の直径を求める方法を知りたいとは思わなかったのだった。

知らずに実装していたし、知っていたのに(理解が浅くて)簡潔な手法を選べなかった。

振り返れば E,F がやるだけの問題だったこと、全方位木 DP、木の直径、どれも前回と前々回の ABC を彷彿させるものだった。どちらも復習はばっちりだった。その結果が３完とは泣かせる。

 提出 #26528881 (AC / 587 Byte / 1032 ms)

DFS ２回で直径を求めるバージョン。全方位木 DP バージョンと比べて、思ったより短くはならなかったけど速くはある。何より各ステップが単純でバグらせにくいと思う。

この単純さは、旅費が最大になる目的地の候補を予め２つに絞っているところから来ている。すなわち、直径(の１つ)の両端に位置する２つの街。

仮に木の中心がある辺にあるとしよう。すべての街が辺のあちら側かこちら側かに二分される。どの街をスタート地点に選んだ場合でも、中心を経由して、中心から最も遠く半径分だけ離れた街を目指すのが最も高くつく。中心を経由しないパスについては、中心に寄り道をするパスを想定して比較材料にすると、最も高くつくケースより安くなることがわかる。

最終更新: 2021-11-04T10:11+0900

♪ [AtCoder] AtCoder Beginner Contest 221／F 問題 Diameter set

精進ですよ。おとといあった ABC の F 問題。

コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの２のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。

木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。

木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので１本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。

たとえば直径が偶数の時、直径の中心には頂点が１つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に２つあるなら、２つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、２つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は１つ。

たとえば直径が奇数の時。直径の中心には１本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が２つあるなら、２つの辺の中点が本来の……(略)。だから中心は１つ。

色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ２つの頂点を考える)。同じ頂点の先にぶら下がっている２点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ？という話になる。そんなものはない。

ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。

配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が１度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。

 提出 #26353562 (AC / 750 Byte / 725 ms)

８問目の黄 diff AC。これより上は橙が１問だけだから、かなりのレア度なんだ。

ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。

 木の直径

さっき書いた。

木の直径については知っている。(中略)。証明は知らない。

木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の１点を始点に選んで最も遠い頂点を求める１回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。２回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。２回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。

 ある問題

さっき書いた。

木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。

エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい！(嘘です。調子乗りました)

最終更新: 2021-12-21T16:21+0900

♪ [AtCoder] AtCoder Beginner Contest 220／F,E

昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は５完６完を狙いたいところなんだけど、ABCD を 17 分４完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか？

 F 問題 Distance Sums 2

こちらが先に解けた。やり方はすぐにわかる。１か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を１つ決めると木に深さという概念が生まれて、根の深さを０にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。

 提出 #26188321 (AC / 572 Byte / 573 ms)

木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。

 E 問題 Distance on Large Perfect Binary Tree

83 分間合わないサンプル２を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。

しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。３つくらい勘違いポイントがあった。組み合わせを半分(それとも２倍？)扱いしなければいけないのはどういうケースか(同じ深さの２頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。

 提出 #26199345 (AC / 203 Byte / 167 ms)

余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。

愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点１つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。

E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。

最終更新: 2021-09-30T13:08+0900

♪ [AtCoder] AtCoder Regular Contest 127／A,B

 A 問題 Leading 1s

制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x は 11111 であるかプリフィックスが 111110 であるかのどちらか。f の値ごとに N 以下の範囲にそういう x が何個あるかを数える。桁数を固定すれば数えやすい。提出 #26096008

競プロ典型90問「025 - Digit Product Equation（★7）」の簡単バージョン。

 B 問題 Ternary Strings

頭の中がぐちゃぐちゃで解けなかった。終了直前の提出がこれ>提出 #26101512 (1 WA)。

とってもくやしいことに、１文字書き換えたら通りましたとさ>提出 #26105189 (AC)。２行目の N==1 を L==1 にしただけ。なんだよもー。もーもーもー。

一応考えたことを。最小化したい最大値の先頭の桁は２で決まっている。その後ろに０から N-1 までの N 個の数を３進数で表記したものをくっつける。これが２から始まる N 個の数。０から始まる N 個の数と１から始まる N 個の数は、桁ごとの制約を満たすようにテキトーに決める。これだけ。なんで書けへんの？ 他の人の提出を見ると tr で 0,1,2 をローテーションするのが簡単そうだった。簡単にできることをすごく難しく考えていた。

驚いたことに、このふがいない有様でレートは上昇しているのである(☞)。どれだけ低いレートに甘んじているかわかろうというもの。

最終更新: 2021-09-23T19:26+0900

♪ [AtCoder] AtCoder Regular Contest 126

昨日の ABC に続いて今日は ARC があった。

昨日と同じく ABC の３完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの？どうなの？)

 A 問題 Make 10

脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785。

 B 問題 Cross-free Matching

LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。

LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02。

LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。

 C 問題 Maximize GCD

最初にサンプルの３にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。

次に GCD について。砂で隙間を埋めるように１ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか？

1. 考えてる途中でなぜか +1 の他に -1 の操作もできるつもりになっていて WA>提出 #25992664。
2. -1 の操作に対応した部分を削除して AC>提出 #25993948 (1248 ms)。
3. C 問題も B 問題同様、制約と入力がガチガチに厳しくないのに助けられている。余分な log を削って 943 ms>提出 #26017330。

どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が２×N になってもオーダーは変わらないけど、ループを２本に増やすことに無意識の抵抗があるらしい。

 D 問題 Pure Straight

残っていた 20 分で愚直解だけ>提出 #25995534。

RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。

最終更新: 2022-02-17T12:53+0900

♪ [AtCoder] 第七回 アルゴリズム実技検定 過去問

第四回までの日記>20201111p01。

課金ユーザーじゃなくてごめんね。@atgolfer1 に流れてきたツイートを見てはじめて問題が公開されていること、第七回が行われていたこと、終了していたことを知ったよ。

 A - チェックディジット

やるだけ。提出 #24382962

 B - 蒸気圧

小さい方を選ぶだけなんだけど、10 分以上切り捨てたり余りを取ったりして悩んでいたのは内緒。提出 #24383193

 C - 入力チェック

Ruby なので 10 進 100 桁はなんの障害でもなかった。提出 #24383281

 D - 書き換え

５つのパターンをじっと見れば最終結果に影響するような文字の取り合いがないことがわかる。提出 #24383341

 E - 青木君のいたずら

探索が許されていることと操作が１回に限られていること、それと遷移が足し算ではなく掛け算だという点が違うけど、問題の形としては ARC122 の C 問題 Calculator を思い出した>20210612p01.03。これが解ければ ARC122-C も解ける！

提出 #24383572

 F - ダブルブッキング

スケジューリングの問題だけど、求められているのが最適化ではなく判定だという点で、最も簡単な部類。提出 #24383711

 G - べき表現

20 分考えた。

どんな正の整数でも、テキトーに選んだ正の整数を基数としてその冪乗の和で表せるのは当然だけど(N 進数ってそういうもの)、使える数字が 0 と 1 と -1 に限定された 3 進数ではどのように事情が異なってくるか、という問題。

2×3^x = 1×3^{x+1} - 1×3^x

という感じで、2 を -1 に置き換えてから次の桁にツケをまわしていくのがいいでしょう。提出 #24384055

 H - 折れ線グラフ

解けてないよ。制約が小さいから探索していいのだろうけど、それでも 100 の 100 乗になるようなバカな探索は許されない。私はバカです。

 @2021-11-15 TLE→AC

上限の揃った制約が DP だと告げている。それも３乗の。まだ８問目だからって雑な探索で解けるとなめてかかっていたのではないか？

1. 提出 #27281059 (TLE×4) 腰を据えてもこれである
2. 提出 #27281255 (AC / 476 ms)

なだらかな折れ線グラフを書きたいのだから、遷移先の幅は自ずと限られる。(W = A.sum/[N-2,1].max+1 -2, +1 はテキトー)

 I - ほくろ

「ABC-D 虐殺三銃士」のひとつ「Congruence Points」を思わせる問題だけど、両目の位置を手がかりに確定した情報が得られるところが優しい。

図形問題は行列や複素数に計算を丸投げしがちなので、これは自分で式を書いた。25 分かかった。提出 #24392172

 J - 終わりなき旅

「強連結成分分解をしよう」がキーワードだった競プロ典型 90 問の 021 - Come Back in One Piece（★5）がすぐに思い浮かんだんだけど、深さ優先探索を２回するんだというアルゴリズム解説は何か所かで読んでたんだけど、これは 17 問ある★５問題のうちで解いてない３問の１つなのだった。

雰囲気は掴んでいたので雰囲気で書いた。提出 #24393748。細部が詰められてなくて無駄があるかも。競プロ典型 90 問のおかげでアルゴリズムの顔見せだけは済んでいたので、今度は実装するところまでこぎつけた。

 K - 急ぎ旅

理解が甘くて 1 TLE。実装ミス(< にすべきところを <= にしていた)で 1 WA。AC はこれ>提出 #24424698。

最短経路問題ならダイクストラ法なんだけど、満足度と所要時間の２つを考えなければいけないのをどう考えるか。所要時間が最短であることが第一で、満足度の高さはその次に考慮すればいいだけなんだけど、だけど、「満足度について、同じ都市を 2 回以上経由してもその都市の景観は 1 回しかカウントしません」という文言がちょっとひっかかるよね。経路を記録して重複を排除しないといけないの？(それには無視できないコストが……)

もちろん負の移動時間はないから、同じ都市を２度訪れる経路が最短になることはない。だけど次の２つのようなパスで所要時間の合計が同じになる場合をどのように扱うか迷った。

都市 M に着いたときの満足度の総和は明らかに２、３、４を経由してきた経路の方が大きくなるんだけど、もう一方の経路は M のあとで７、８、９を経由することで取り返すことができるかもしれない。M に着いたときの満足度の低さを理由にして一方のパスを捨てていいのかどうか。

実は上の図には嘘があって、上の図のような状況の実際は下のようになっている。

これは１と M とのあいだの最短所要時間と、M と N とのあいだの最短所要時間がどちらも１つの値に決まることからわかる。最短経路であるどの２つのパスを取り上げても、分岐と合流を繰り返す第３のグラフのような関係になることが納得できたら、ある都市に最短で到着する経路のなかから最大の満足度を記録するのでいい。

 L - たくさんの最小値

セグメントツリーなんだけど、最小値を持っているインデックスをどうやって列挙するかという問題。

最小値の記録と添字の記録をセグメント木と配列で分担しようとして TLE を出したり(提出 #24408482)、セグメント木の実装ミスで大量の WA を出したりしつつ(提出 #24412768)、三度目の正直で AC>提出 #24413254。

セグメント木を上から下に下るのって苦手。(根っこが上です。逆にすると頭が働かない)

 M - 分割

全部を分割した状態から始めて、損をしない範囲で統合していくのかなと思ったけど、並べ替えができなくて境界が入り乱れるのを、どう整理して扱えるのかわからない。

とある赤亀コーダーさんによると全体でこの M が一番難しかったらしい。

 N - モノクロデザイン

昨日これの簡単なバージョンを解いたよ>「B - すぬけ君の塗り絵 2 イージー」(提出 #24414821)。

二次元累積和かなと思うんだけど、ABC203-D Pond も競プロ典型 90 問の 081 Friendly Group（★5）もまだ解いていない。二次元累積和って累積和の累積和とは違うんだなー、という感想を持ったのは覚えてるけど、よく思い出せない。

 O - コンピュータ

O 問題が解けたのは初めて。

入力を圧縮したり累積を記録したりして計算量を削減するのは、競プロ典型 90 問の 089 - Partitions and Inversions（★7）ぽいなーと思った。

以下は考えたこと。

1. ある B より後ろにあって、前にある B と同じかそれより小さい B は無視できる。
2. だから N 個の入力は、B の増加列といくつかの A を足してまとめたもののペアとして圧縮できる。
3. 最終日までに得られる報酬の総額は決まっている。コンピュータに支払う金額をどれだけ減らせるかという問題。
4. 十分な資金があるなら明らかに B の最大値と同じ値段のコンピュータ１つだけを買うのが最適。
5. しかし資金が足りない場合は目の前の障害(B)を超えられるだけのコンピュータを買って、目先の報酬を得るようにしなければいけない。
6. なんですかね、貧しさ故に最適な選択ができないって、現実ですか。保険とか追証とか宝くじとか。
7. 複数の買い方。障害(B)が１、２、５、６、９と並んでいるときに、１を買って５を買って９を買うのがいいか、２を買って６を買って９を買うのがいいか。局所的な判断では決まらないので貪欲法は使えない。
8. 迷うたびにキューを伸ばすと爆発するので DP っぽいなー。
9. N^2 のループは許されていないので、すべての i についてそれより後ろにあるすべての要素を処理対象にすることはできない。
10. i<j<k とする。コンピュータはできるだけ買わないのが正解だから、ある i と j がともに k にある障害を越えるというとき、j から k への遷移が i から k への遷移より得するということはない。
11. i を通過する時点ですでに k を超えられるだけのコンピュータを買う資金があるのだから、到達地点が同じ k なら j で足踏みする価値がない。
12. j で足踏みする価値は k より遠くへ(k を超えて一足飛びに)到達できる可能性にある。
13. という感じであとはがんばってコーディングする。提出 #24429839
14. .each_with_index.each とか謎なことしてる……。幸いにしてこれは無駄なだけで害はないけど、部分的な修正を繰り返すとこういう風に、(通して書き下したときにはありえない)謎なバグを仕込みがち。

最終更新: 2021-07-19T22:56+0900

♪ [AtCoder]AtCoder Regular Contest 123／C 問題 1, 2, 3 - Decomposition (+ B + A)

悔しいなあ。手も足も出ない方がまだあきらめがつく。

 提出 #24373137 (WA×20 / RE×12 / AC×2)

１時間かけてコンテスト終了直前に投げた。サンプルすら通っていないけど、５つあるケースの最後の１つの答えが違っているのに気がついていなかった。ダメダメである。

RuntimeError の原因は Array#compact が false を取り除いてくれていないのに気付かずそのまま min メソッドを呼んだこと。

Wrong Answer の原因は比較して小さい方を選ぶべきところで、勝手に優先順位を付けて先に値が得られた方を選んでいたこと。それともう１か所(b+(d-1)%10 の %10 が完全に余計)。

プログラムの型は Send More Money と同じ>20210412p01。桁を見て、キャリー(ボロー)を伝えて、最後まで矛盾なく桁が確定できるかどうか。それを k を増やして条件を緩和しながら最小値を探った。

答えの上限が５だと見抜いていたところは偉いと思うんだ。なぜ５かといえば、項数が１ならある桁に関して作れる数字が 1..3。２なら 2..6、３なら 3..9、４なら 4..12、５なら 5..15 ということで、最初に 10 種類の数字が作れるのが５項の和。0..4 の数字を作ろうとすると繰り上がりが不可避なのが制限だけど、それは隣の桁で吸収できる。６以上に項数を増やしてもできることは増えない。

 提出 #24375535 (AC)

ほとんど違いませんよ。でも A から F まで６問ある中の３問しか相手にしていないのに、時間内に完成させられないんだなあ。

実行時間から判断するにだいぶ無駄が多いみたいだけど、制約に苦しめられてたったひとつの解法、たったひとつの記述を探らないでいいってすばらしい。

 B 問題 Increasing Triples

ただの貪欲。提出まで 15 分>提出 #24363550

 A 問題 Arithmetic Sequence

AC まで 2 WA、33 分。どういうこと？ 10 分時点で９割５分は完成していた>提出 #24355415。デバッグ出力を消し忘れてるのと、入力を勝手にソートしてるのがいけない。列(Sequence)は順序付き！(知らないわけではない。括弧と波括弧に使い分けがありそう？ それは知らない)

AC>提出 #24361099。ほとんど違いませんよ(２回目)。

最終更新: 2022-01-25T19:28+0900

♪ [AtCoder]AtCoder Beginner Contest 210／E 問題 Ring MST (+D 問題)

A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで４完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。

 提出 #24322478 (RE×11 / AC×19)

30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、３分岐のうち２つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の２択ではなく AC/WA/RE の３択にするテクニック。WA がなかったということで、中身のある２分岐にミスはなさそう。

 提出 #24337207 (AC / 273 ms)

複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。

 D 問題 National Railway

DP です。１行目から行ごとに考える。

1. ある行について。処理済みの地点に建てた駅からこの行この列に至る最小のコストを記録することにする。
2. その次の行にて。各列 Aij の費用を払って駅を建てたとする。前の行の j 列に記録されたコスト(の先にある地点)をもうひとつの駅として、建設費用を計算する。
3. 建設費用の最小値が答え。

罠があるとすれば、同じ行から２つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。

 提出 #24314328 (AC / 559 ms)

m1 が同じ行内からもう１駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。

その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。

ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。」で問題文が締められているのだけど、２、３回読み直したよね。え？ どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。

最終更新: 2021-07-14T01:38+0900

♪ [AtCoder] 競プロ典型 90 問／083 - Colorful Graph（★6）

たいへん厳しい。解説１、解説２、解説３、解説４。

解説を読めば半分全列挙と同じように、汎用的な手法であるが故に問題から解法を見出そうとしても出てこないタイプの問題と解法だったと言えるのではないか。

以下は解説を読む前の提出。

 提出 #23928493 (TLE×9 / 同じ内容) ※TLE×4 に改善できる

クエリを先読みして頂点ごとに関連するクエリ番号をためておき、メインループは辺について繰り返すことにした。メインループの中ですることは辺が結ぶ２頂点が持つクエリ番号列のマージ。色の伝播を担うのが辺だということと、現在の色を決めるのは直近のクエリだということに着目した解法。

解説１にも書かれているように、これは特定の頂点に辺とクエリが集中したときに処理時間をオーバーする。とはいえこの提出のマージ部分は不必要に時間をかけている。２つのクエリ番号列の長さの和に比例した時間ではなく、二分探索を繰り返してもう少し(＜コレ)ましな時間にできる。その場合の TLE は(おそらく)４つ(random_challenge のうち２つと random_clique ２つ)>typical90_83_TLE4？.rb27。

 提出 #23932276 (TLE×8 / 同じ内容)

この問題の悩みの種は、クエリに応じた色の変化を隣接ノードに「通知する」ことも、逆に隣接ノードに現在の色を「問い合わせる」ことも、制約から許されていないということ。

ここで、親にだけ通知してみるのはどうだろうと考えた。隣接ノードの数は N のオーダーになりかねないとしても、親であれば１つに決めていい。問題は親の決め方で、この問題のグラフは木ではない。

この提出ではノード番号が小さいものを親の側にあるとした。いきなり「親は１つ」ではなくなっているがしかたがない。だからこその TLE×8 なのだ。

 提出 #23933074 (TLE×5 / 同じ内容)

所与のノード番号を利用するアイディアはお手軽に過ぎたので、今度はちょっと手間をかけて深さ優先探索で親子関係を決め、閉路が見つかったときに限り余分な親を追加することにした。残る TLE は５つ。

テストケースをダウンロードしたら、TLE になっているのは random_clique と名付けられた全２ケースと random_kill と名付けられた全３ケースの合計５ケースだった。自分の解法に弱点があり、そこを見事に狙い撃ちされたといったところか。定数倍の改善では全然間に合わない。

 提出 #23996165 (TLE×2 / 同じ内容)

閉路が見つかったときにどちらをどちらの親にするかは好きに決めていい。親の数を比べて親の数が少ない方に他方を親として追加することにしたら、random_kill と名付けられた３ケースの TLE が解消した。

残るは random_clique が２ケース。random_kill が特定の１、２ノードに辺が集中していたのに対して、この２つのケースはまんべんなく多くの辺が伸びている。クエリに応答する負荷が全体的に底上げされていて逃げ場がない。

 提出 #24004617 (TLE×2 / 同じ内容)

クエリの先読みをしたらメインループの前準備で探索のためのスタックがいらなくなった。クエリに関与しない頂点は無視していいし、入力された辺も片方向だけ記憶しておくのでいい。どちらをどちらの親にするかを決める

# P[v].size は親の数。Qn[v] はクエリで参照される回数
if P[a].size*Qn[a] < P[b].size*Qn[b]

という判定はメインループの負荷をよく反映していて気が利いてると思う。すべてクエリ先読みの効果。でもダメ(TLE)です。さっきの TLE×2 からはローカルで 12 秒が 7 秒になったけど、ならジャッジサーバーでは良くて 5 秒だろう。制限は 3 秒。