/ 最近 .rdf 追記 設定 本棚

脳log[2024-08-10~]



2024年08月10日 (土) [AtCoder] 今日は AtCoder Beginner Contest 366 があった。くるしい。■A 問題「Election 2」。T と A の大きい方が N/2 (切り捨て) より大きいかどうか。■B 問題「Vertical Writing」。すごーくめんどうくさいけど、まあまあ面倒が少ない実装ができたと思う。まず、短い行の末尾に * を補って全体を N 行 M 列に揃える。次に配列を transpose して reverse する。この時点でほぼ出力ができあがってるんだけど、各行末尾の * を取り除いてから出力する。■C 問題「Balls and Bag Query」。Hash で個数を管理してサイズを答える。カウント 0 になった要素は取り除く。■D 問題「Cuboid Sum Query」。3次元の累積和。具体的にイメージができないので、機械的に操作をする。うまく1次元の操作を2次元3次元に拡張できるといいね。行列計算がそうだしこの問題もそうだったけど、自分は必ず演算対象の次元数を勘違いしてエラーを出す。数値に対して配列のメソッドを呼んだりする。包除も機械的にやる。3つの次元について L を使うか R を使うかの2通りがあるので全体では 2^3=8 通りの累積和を足し引きする必要があるが、3つとも R を選ぶのが全体であり、そこから引いたり引きすぎたものを足したりするのだから、3個の R を選んだ場合をまずプラスにして、つまり奇数個の R がプラスで偶数個の R がマイナスになる。これはコンテスト終了後に AC が出たからわかったようなことを書いている。コンテスト中は飛ばして E をやっていた。D と E がどちらもたいへんなら配点の高い方に時間を使う。■E 問題「Manhattan Multifocal Ellipse」。D (入力値) の最大値が 100 万だということで、平面上のエリアを具体的に特定できると思った。X 座標と Y 座標を分けて考えるけど、それぞれプラスマイナス D の範囲に限ることができる。D×D は通らないけど、1つの軸を1つずつ走査しながらもうひとつの軸が効率的に数えられたらいい。(WA×1/TLE×5/AC×23) までは行ったんだけど、log の2乗は「効率的」ではないんだよなあ。でも尺取りをするのもたいへん。(WA×1/TLE×11/AC×17) の構造を崩して改善した結果がさっきの TLE×5 なのであって、さらにぐちゃぐちゃ書き直したくない。それが済んでも WA×1 が残る。■F 問題「Maximum Composition」。制約が小さい。K は 10 以下だし、(A,B) の組み合わせも 2500 通りしかない。ということは最大 20 万個の (A,B) には重複がたくさんあるのだが、K 個以上は K 個と変わらない。という感じでなんとなく状態数が少ないような気がしたからといって、メモ化再帰をするだけでは TLE になるのだなあ。コンテスト終了後に取り組んだけど TLE だった。■なんと ABC の3完だ。自分のすべての提出。いまもって E も F も AC が出ないのだから、D の AC が時間内か終了後かはどうでもいいよ。どっちでもだめだよ。■E 問題。AC 出たよ。提出 #56580497 (AC / 942 Byte / 642 ms)。一方の軸を走査しながらもう一方の軸について数えるのではない。それぞれの軸について独立に、座標を、距離の総和に変換する。あとは距離の列と列をソートして尺取りっぽく和が D 以下になる組み合わせを数える。そうしたら TLE が解消しただけでなくなぜか WA も消えていた。コードはほぼすべて先の2つの提出のコピペであって、なんの修正もしてないのに、謎だ。これで A から E まで AC が出たけど、100 分で5完の目がある問題セットではなかったな、というのが感想。D も E も実装が重い。かといって4完ではなく3完なのは全くの想定外。これまで2回くらい脳みそにクモの巣が張ってるって日記に書いてるけど、それってブレインフォグっていうんじゃあありませんか?(何かのせいにしたいだけ。キミはもともとそんなのだ)■F 問題。どうするのかなあ。引数が大きくなればなるほど A が作用する比重が B のより大きくなっていくのを利用して状態数を減らしたい気がするんだけど、A 対 B の2次元の表に線を引いてトップ K を選ぶことってできない。■D 問題の提出一覧を見てると、自分のが特に遅い。3秒制限ぎりぎりだから当然なんだけど、どこが遅いのか。3次元累積和の作り方が下手っぽい。自分のは余分にループが回っている。なにか標準的な手順があるのだろうか。自分はまず3次元空間を用意して、3つの軸について順番に一方向に寄せるように累積和を作成していった。無駄があるのは、3つのパスで順番に、1次元累積和の作成、2次元累積和の作成(1次元累積和のマージ)、3次元累積和の作成(2次元累積和のマージ)を行っていて、たぶん3つともに3乗の時間と空間が使われているところだと思う。どうもね、すでに更新済みの累積和を参照しながら1パスで3次元累積和を構築してる提出が多いみたい。それってややこしすぎません?


2024年08月09日 (金) BABY IN CAR と書かれたステッカーがぺたぺたと車に貼られるようになって久しいが、今日前を走っていた車に貼られていたものには THE BABY IN CAR と書かれていた。それを見て、えっと、自分は知らないんだけど、どの(どんな有名な)ベイビーが乗っているんですか、という疑問がぐるぐるとわき上がってきた。そうするうちに文字の横にある模様がノースフェイスのものだと気がついた。つまり、THE NORTH FACE をもじった結果として THE BABY IN CAR と書かれているのであって、元ネタありきだから、文字単体で見ると不自然なものになってしまっているのだなと納得したのだけど、どうだろうか、同意してもらえるだろうか。おかしなことを言っているだろうか。


2024年08月03日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#8(AtCoder Beginner Contest 365)があった。解けるはずの D を落として ABCE の4完。F も G も歯が立たず。■A 問題「Leap Year」。どんどんネストを深くしていくこともできるし、ガード節を並べるみたいにもできる。leap? メソッドを使うこともできたみたいだけど、仕様の異同を確かめるのも無視するのも避けたい。■B 問題「Second Best」。max_by メソッドに引数を渡す。■C 問題「Transportation Expenses」。二分探索をして下さいと言われているように見えて、実は二分探索は必要ない。だけど二分探索をしないことでタイムが縮んだりしなかったのは、最初に A 数列をソートしていたからだった。無駄にややこしい解法を選んだかもしれない。■D 問題「AtCoder Janken 3」。最初の提出が WA だった。表か裏の2択だと思ったけどそこまで単純ではなかった。そこで無駄に考えすぎて SS.SPP.PRR.RSS... という順方向の並びと S+R+P+S+.. という逆方向の並びの連鎖を考えなければいけない気がして、こんなん ARC でしょと困惑していたのだけど、実は直前の手が何であったかという3状態の DP なのだった。AC は終了3分後。初手を間違えたあとのデバッグと方向転換が苦手すぎる。■E 問題「Xor Sigma Problem」。ビットごとに累積和を考えるだけなんだけど、0と1を反転させるだけの操作ができないんですよ。なかなかサンプルが合わなかった。■すべて 35 ℃を超えている室温が悪い。自分のすべての提出。■■■精進@翌日。F 問題「Takahashi on Grid」。位置の管理を BIT でやりたいとはコンテスト中に考えていた。でも L..U の範囲から外れた点をぞろぞろと移動させる方法が思いつかなかった。一日経ってもう一度考えたら重み付き UnionFind で集団大移動ができる。だいたいの点は L か U というエッジに寄せられて集団を作るので、代表点だけを動かして代表点にコストを計上する。各点のコストは代表点からの相対。エッジに寄らない点はコストがかからない点なので、ありがたく無視する。手段がわかればあとはやるだけ。std::map がない Ruby ではいくつもの道具を組み合わせてクエリの集団を Y 座標でソートした状態を保たなければいけないのが面倒で間違えやすい。■提出 #56361608 (AC / 2193 Byte / 2675 ms)。お風呂でエアコーディングを済ませていたのでばっちり2時間半(!)で AC ですよ。どうやってこれをコンテスト時間内に完成させられるんだ……。sx<tx を勝手に仮定していただとか、Y 座標の移動コストばかり気にしていて X 座標の移動コストを忘れていただとかの細かいバグはすぐに修正できたけど、一番難しかったバグが重み付き UnionFind の Find 関数にあったもので、1時間以上苦しんでいた。重みを更新するのにあたって条件が必要だとは思わなかった(58 行目)。このバグがあってもサンプル3の1つのクエリ以外は答えが合うのが怖い。サンプルが仕事をしていてたいへん助かりました。あとは BIT を使うにあたって座圧をさぼったら2つのケースで最長 221 ms 制限時間をオーバーして修正に 20 分。どうやってこれをコンテスト時間内に完成させられるんだ……(2回目)。■F 問題。Ruby での提出一覧を見たらもう AC を出している人がいた。提出 #56324651 (hmmnrst さん / 1304 ms)。自分の倍早い。中身を見たら GridRange と SegmentTree という、自分とは違う道具立て。セグメント木は BIT のスーパーセットだということで共通点はあるけど、GridRange ってなんぞ?■セグメント木を昨日考えなかったわけではない。一度 L か U に寄せられた点は以降決まったルートを辿るわけで、中間をすっとばしてゴール地点 X=tx における Y 座標が1つか2つ求められる道理。それができるのがたぶんセグメント木。ゴール地点において Y=ty との差分をコストに計上するのも簡単。でもスタート地点 X=sx における Y=sy が扱えなくて行き詰まった。sy は L でも U でもない。それをうまくやる方法があるということなのかな。セグメント木に何を乗せるかだよな。クエリに答えるのに都合のいい情報。わからん。


2024年07月27日 (土) [AtCoder] 今日は日本レジストリサービス(JPRS)プログラミングコンテスト2024#2(AtCoder Beginner Contest 364)があった。先週(20240720)と似たようなことを書いてもいいかな。Ruby にとっては D 問題が難しすぎて TLE が解消できなかった。D と F を見比べて、F の方に見込みがあると思って F 問題に8割方集中していたが時間内には解けなかった。終了 11 分後に F 問題の AC が出た。あとちょっとで解けたと思えばこそ得点にならなくてくやしい。■A 問題「Glutton Takahashi」。サンプルの2で示されているのは親切だけど、そこそこ殺意の高い罠がありますね。全部食べたあとで気持ち悪くなるパターンがある。sweet\nsweet を検索していたのを修正して sweet\nsweet\ns を検索するようにした。■B 問題「Grid Walk」。やります。B 問題にしては実装が重め。グリッドのサイズが小さくても実装量が減るわけではないんだよね、当たり前だけど。そこんとこ承知してくれているかな?■C 問題「Minimum Glutton」。C 問題で DP か? と一瞬身構えたけど、最小値を求めるということで、2通りの貪欲法を比較するだけ。大丈夫です、最大値を求める DP 問題は E にあります。■D 問題「K-th Nearest」。二分探索してくださいという問題にしか見えなくて他に方法が思いつかないんだけど、制限時間3秒のところ、(1割増しの 3.3 秒ではなく) 3.22 秒かかって TLE だったので、220 ms ほどの高速化が必要。どうするの?■E 問題「Maximum Glutton」。C 問題の難しい版。甘さとしょっぱさの組み合わせを状態のキーにはできないけど、甘さとしょっぱさのどちらかと個数を組み合わせてキーにすることはできる。甘さをキーの1つにしたら、しょっぱさを最小化する DP をする。これもサンプルが教えてくれたんだけど、A 問題と同じ罠があります。同じ罠に落ちかけました。■F 問題「Range Connect MST」。どういう風に辺を引くことになるのか、イメージがしづらい。木なので本数は N+Q-1 本だと決まっている。それを最大 N×Q の組み合わせからどう選ぶと全域木になるのか。あれこれ考えてようやく納得できたのは、i=1..Q において、Li..Ri のあいだに連結成分が g 個あるなら、g 本の辺を引くのだということ。両手の 5+5 本の指を使って考えると、それで N+Q-1 本の辺が選ばれるようだったのでそう思った。答えが合わなくて時間内に提出できなかったんだけど、原因がしょうもなくて、貼り付けた BIT のイニシャライザにある初期化コードが今回は不要だと思って削除したけど、削除してはいけなかったという、そういう理由で答えが合わなかった。たとえばヒープだと、ソート済みの配列を内部データにする場合、初期化の必要がない。ソート列はそのままでヒープの要件を満たしている。だけど BIT の内部データは違うんだなあ。解ける問題だったなあ。1から数年前の自分なら解いていたなあ。■自分のすべての提出。最近ユーザー名の横に表示されるへの字。ノイズではあるんだけど、水色でもまだ 1500 台を維持しているなという慰めにもなっているもよう。■精進。D 問題。Q のループの中で二分探索をする中で二分探索を2回行って TLE を出していた。二分探索の上限を指定せずに TLE×11。上限を指定して TLE×7。最も内側にある2個目の二分探索を省けるときは省くようにして TLE×1。最内の2個目の二分探索を完全に省いて AC。これが 1765 ms なんだけど、Ruby で 627 ms で解いている人がいるんだよね。気になるけどネタバレは嫌だ。■D 問題。別解。提出 #56088391 (AC / 325 Byte / 340 ms)。log 1つでできると読んだので、k 幅のウィンドウを二分探索で置いてみた。判定条件は、右端の要素が初めて左端の要素よりも b から遠くなる瞬間。そのひとつ手前では逆に、左端の要素が右端の要素より b から遠くなっている。この両者を比較する。二分探索の高速化っていうと尺取りが定番なんだけど、だから昨日はその方面で TLE 回避策を考えたりしてたんだけど、この D 問題はウィンドウの幅 k がクエリごとに可変だから、尺取りはうまくない。今日の提出では同じ二分探索を使っていてあまり違いを感じないんだけど、よく見れば二重の log が一重に減っている。log 1つの差ってたしかにこれくらい微妙なものではあった。Pairs を解いていたときに書いている。「log ひとつの差ってちょっとした違いなんですよ。ちょっと見る角度を変えるだけ」。提出したあとでもういちどさっき読んだブログを読み返すと、まんま自分の提出がやっていることが書いてある。「初めて左端のが遠くなった場所を見つけてその一つ前も(存在すれば)候補なので比較して」。なんかよくわからんなあと思いながら読んでいたけど、実際今も「自分より1離れたもの同士を比較」「長さが1短い区間を考えて」「初めて右のが遠くなったら左のを付け加えてそれがそのまま答え」とかよくわからないんだけど、必要なことは一度読んだだけで頭の中に入ってるんだな! 自分では思い出せないだけで。


2024年07月20日 (土) [AtCoder] 今日は AtCoder Beginner Contest 363 があった。Ruby にとっては C 問題が難しすぎて解けなかったが AC を出している人もいる。精進が足りない。Ruby で通している人が1人でもいるなら自分も通せなければいけない。なんなら自分が最初で唯一の AC でありたい。E まで解いてから F と C を見比べて F の方に見込みがあると思って F に専念していた。その見込みは間違っていなかったが、TLE を出したあと誤った解法の実装にのめり込んでいる内に時間切れになった。実は関数に引数を1つ付け加えるだけで AC になったのだが、30 分ちかく時間を残していてそれに気がつけなかった。くやちい。■A 問題「Piling Up」。全パターンの差分を並べてもっともふさわしいものを選んだ。短い解答を見てみると、すべての基準値が 100 の倍数だということを利用していた。そういう法則がすぐに見抜けないし、見抜けるまで問題を読んでもいない。■B 問題「Japanese Cursed Doll」。ソートして P 番目なんだけど、昇順ソートして前から P 番目ではない。それを間違えていてもサンプル3を試すまでは答えが合うのが怖い。■C 問題「Avoid K Palindrome 2」。順列全列挙では間に合わなかった。どうやるの? C 問題で順列全列挙以外はやる気がないよ。■D 問題「Palindromic Number」。これぞ ABC の D 問題、緑 diff って感じの問題。実際の難易度が何色かはまだ知らないけども。順番に生成して 10^{18} 番目まで数えることはできないので、まずは桁数を決めて、桁数が決まったら先頭の桁から確定していった。■E 問題「Sinking Land」。UnionFind です。最大6桁の数字が 100 万個という入力はそれだけでけっこう重い処理。正確さを重視して富豪的に書くと AC と TLE のボーダーを超える可能性があるので、全体を通して最初から書き方を選んでいく……余裕があるといいね! グリッドの各マス+海用に1個の頂点を用意して、海抜の低い順に、自分より低い頂点とのあいだで結合する。海のマスを数えたら陸のマスが求まる。■F 問題「Palindromic Expression」。やるだけの問題だと思うんですよ。解けたはずだと思えばこそ悔しい。まず中心に N を置きます。これが最初から条件を満たしているならこれが答え。さもなければ、N を L*M*R で置き換える。L と R は左右対称でなければならず、M に対しては再帰的に同じことを繰り返す。2数の積で N を割っていくので、N≦10^{12} だから、L,R として列挙する数は 10^6 個程度に収まって許されそう。終了条件を N<[L,R].min**2 として愚直にやったら TLE だった。N や M に関して結果をメモしたら数は減ったけどまだ TLE だった。AC になった鍵は、A*B*C*D*E という状況で A<=B でなければならないと定めたこと。こういう方針自体は TLE が出た直後に考えて実装に取りかかってるんだけど、なぜか実装の途中で L が回文数でなければいけないという条件が加わっていて、その実装に忙殺されてしまっていた。なんでだよー。■自分のすべての提出。■F 問題。日記を読み返すと「なんでだよー」の答えが見つかるんだよなあ。L*M*R の L と R に関して、「L と R は左右対称でなければならず」と表現しているところに誤りの種がある。左右対称なのは L*M*R 全体なのであって、L と R について書くなら表現を改めて、「L と R は反転して一致しなければならず」とする方がよりふさわしいと思う。雰囲気で理解して細部がぼんやりだから途中ですりかわるんだよ。コンテキストが遠ざかったときに左右対称という断片に引っぱられて勘違いをする。■精進。C 問題。Array#permutation で N の階乗通りを列挙する代わりに、再帰関数で同じ文字を区別しないで列挙するようにしてもまだ TLE だった(#55827067)。X で読んだ通りに、1度しか出現しない文字を統合する前処理を施すことでさらに列挙数を減らすことができて AC になった。提出 #55827317 (AC / 536 Byte / 584 ms)。300 点問題にかけていいコストではない。同じ時間で D と E と F を解いたあとで初めてペイする。■■■D 問題。「N=19999のとき、正解が99999999(8桁)だけどコードが出す解が9999999(7桁)になっちゃうみたいですが通りはしました」と投稿している人がいて、試しに自分の AC 提出(#55797000)を実行してみたら 100000001 (9桁) になって、どちらでもなかった。投稿主の提出(#55831310)をコードテストで実行してみたら、たしかに書いてある通り7桁の9が出力された。正しい答えはなんなんです? Ruby の AC 提出2、3個で多数決をとったら、正しい答えは 99999999 (8桁) らしい。入力と出力の見た目には桁数が違っても維持されるパターンが見られるのだけど、自分の提出は N=100000 型とか N=999999 型では他と一致していても、N=19999 みたいな型の入力に対してはずれている。だって N=199 と N=200 の答えが同じなんだもん。サンプルの3を合わせるために ≦ を < に修正してから提出したのだけど、たぶん修正すべき場所が間違っていた。ザルなジャッジにお目こぼしされてしまったか。提出 #55833437 (AC)。after_contest はまだないみたいだけど修正版を提出。N=19...9 と N=20...0 っていうのは、出力の桁数が変化するという点でのコーナーケースみたい。テストケースにコーナーケースがなかったんだね。■E 問題。別解。提出 #55860799 (AC / 523 Byte / 707 ms)。UnionFind 解が #55800705 (AC / 524 Byte / 1629 ms) だったので、長さはほぼ同じなものの、時間は倍以上早くなった。別解は BFS。プライオリティキューすら必要ではなかった。■精進。「砂の城 (Sandcastle)」。E 問題と似た問題だと名前が挙がっていたので。提出 #55862476 (AC / 354 Byte / 578 ms)。たしかに、これも BFS だった。かなりシンプルに書けたと思う。


2024年07月17日 (水) 二三日は何日なのか問題。もちろんこれが問題になったことはない。自分としては、四六時中や四十九日、七十五日、三々五々から演繹するとニサンニチになるしかないと思うのだけど、実際にそうだったことがあるのを知っていることからもそう考えるのだけど、今 ATOK で明鏡国語辞典を引くと「しじゅうく‐にち【四十九日】〘名〙 人の死後四九日目に当たる日。また、その日に行う法要。七七日(しちしちにち)」とか書いてあって、これもうわかんねえな。いやホントはわかりますよ。「四十九日」「七七日」の2つと「四九日(目)」とでは使用時期にずれがある。辞典の言葉は収録される言葉よりも新しい。23 日を二三日と書くことの帰結として、10 月が一〇月になっていたのが先々週読んでいた小説。何を今更感しかないけども、そうなんだ、そりゃそうなるよな、だけど気持ち悪いな、その○はなんなんだ、漢字ではないよな、とひっかかってしまったのが今日の日記になっている。十月って書きたいよ。■ATOK で 10 を変換して出した一〇で使われているのは○ではなかった。U+3007 は「漢数字ゼロ IDEOGRAPHIC NUMBER ZERO」であり、U+25CB 「丸印,白丸 WHITE CIRCLE」とは異なる文字だった。〇が比較すると新しい字だけど数百年はさかのぼれるみたいなことが Wikipedia の漢数字のページに書いてある。お前漢数字なのか。漢数字とアラビア数字を区別して一方では位取り記数法を認めたくないっていうのは、単に好みや慣れや、旧弊に囚われているってだけなのか。自分はこれからも区別して用途を分けていきます。■用途を分ける(漢数字では位取り記数法を使わない)ことの別の一面は、「健康第1」とか「3位1体」とか「別の1面」とは書かないということ。算用数字を使うのは1、2、3と数を数える場面だけでいい。X と X+1 が可換な場合だけでいい。


2024年07月16日 (火) 子供の頃にスーパーボールで遊んだ記憶。今でも理解できないし説明できないのだけど、たとえば床に2バウンドさせて壁にぶつけるとする。1バウンドした位置から A の距離で2バウンドし、そこからさらに B の距離で壁にぶつかるとする。この A と B の距離(あるいは時間)の比率が跳ね返ったボールの跳ね方に反映されて、不等間隔の規則的な跳ね方を繰り返す。だったよね? おもちゃにも流行り廃りと技術や素材のアップデートがあって、今の子供はスーパーボールなんかでは遊ばないかなあと思ったので書いた。


2024年07月13日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#7(AtCoder Beginner Contest 362)があった。特に書くことはないけども参加記録として。自分のすべての提出。■A 問題「Buy a Pen」。3通りなのでどうとでも書きます。■B 問題「Right Triangle」。2乗のまま整数のまま三平方の定理で判定します。■C 問題「Sum = 0」。最初はすべて L に寄せて和の最低値を求めます。あとは和が負である限り、各組 R-L を上限として右に寄せていきます。■D 問題「Shortest Path 3」。辺だけでなく頂点にも重みがあって何かが変わるかなと考えたけど、普通に普通のダイクストラ法のままだった。■E 問題「Count Arithmetic Subsequences」。N の制約が 80 以下と非常に小さい。これだけ小さいと O(N) と O(logN) の差よりも定数倍の違いの方が大きくなりがち。80 の3乗が大した大きさでないことを確認して愚直3重ループを書いたら TLE が出てびっくりした。3重ループと書いたけど実は3つ目のループは再帰関数の中に隠れている。それって3重にとどまらないのでは? やばいのは公差が0のケースなのでそれだけ別で数えて AC。■F 問題「Perfect Matching on a Tree」。マッチングとかフローとか辺被覆とか点被覆とかはわかりません。「最大重み最大マッチング」てなんだったんでしょうか。まんまと「知らないキーワード、怖い」と G 問題に流れていっちゃったけど、この問題は難しいことは考えずに、木の中心で頂点集合を2つに割って組み合わせたらどうかなと思った。WA だった。この問題の何が問題なのかがわかっていないか、うまくできなかったか、どちらなのかもわかりません。とはいえ、うまくできていなかったのは間違いない。中心に頂点があるとして、中心から3本以上の辺が出ている場合が考慮できていなかった。■G 問題「Count Substring Query」。ミシシッピの s が足りないのが気になってしょうがない。なんでコンテスト中に辞書を引いてるんだ……。F 問題より見込みがあるかと先に考えていたけど、数を数えようとするとどうしても2乗の時間がかかりそうになる。接尾辞配列を使うだけみたいなツイート(?)を読んだ。その使うだけもできないのだから惜しくも悔しくもないけども、接尾辞配列とか完備辞書とか Trie とか、見て見ぬ振りをして実装せずに来たツケなのは間違いない。「SA-IS 法のメモ - まめめも」8割くらい読んだ。しれっと挟まれた翻訳者自らの宣伝だけど、その本はもう持っている。悲しいかな理解が追いつかなくて積まれているけども。SA-IS 法に話を戻すと、2割が完遂できなくて写経することしかできない。たとえ写経でもするべきなのかなあ(やらないつもり)。やると書いて、やる、有言実行メソッドと、やらないと書いて、やる、天邪鬼メソッドの両方があります。自分のモチベーションをより高める方を選んでどうぞ。■■■精進。F 問題。提出 #55644781 (AC / 1365 Byte / 636 ms)。やりたいことのイメージは合ってたみたい。中心で2つかそれ以上の頂点集合に分けて、異なる集合から1つずつ選んでペアを作る。それをどうやってうまくやるか。葉から処理を始めて、親にどんどん頂点集合を集約していく。その集合の大きさが過半数になってはいけない。最終状態がいくつか考えられる。わかりやすいのが、集約された結果ある頂点とその2つの子が残り、そのサイズとつながりが (N/2)-(1)-(N/2) である場合。左右の子から1つずつ頂点を取り出してペアを作ればいい。総頂点数の偶奇により中央に頂点がない (N/2)-(N/2) のパターンも考えられるがやることは同じ。もうちょっとわかりにくいのは、ある頂点が3つ以上の子を持っていて、どの子に軸足を移そうとしてもその瞬間に他の子が過半数の大きさの頂点集合を作ってしまう場合。最も単純なケースは、2から N のすべての頂点が頂点1につながるスター型のグラフ。頂点1を中央に据えて、他のどの子の頂点集合もサイズはたったの1だけど、どの2頂点もマージできない。そんな感じで頂点集合をマージできるだけマージして残った頂点集合の集合からペアを作るのが次のステップ。同じ集合の中からペアを選びさえしなければいい。だからプライオリティキューを使ってサイズの大きい頂点集合から優先して2つ選んでペアを作ることを繰り返した。もっと洗練されたうまいやり方と考え方が絶対にありそうだけど、AC なんやしまあええやろ(向上心のない怠惰な態度)。あと、自分が中心と呼んでいるものに重心という名前がついているらしいのは何か所かで読んで把握している。■■■F 問題。某週記を読みまして DFS 順でペアが作れると知った。DFS の行きがけ順(に限らない?)に 27 個ないし 26 個の頂点を A-M$N-Z と並べたなら、(A,N),(B,O),(C,P),...,(M,Z) のペアを作る(のだと思う)。ローカリティに注目すればなんとなくそれでいいような気がするし、逆に両端からペアを作っていくのがダメなのもわかる気がするが、いつでも絶対それで OK とはわからない。■自分の解答の後半のステップはプライオリティキューを使わないで、単純に入れ子配列をフラットにして真ん中で切ってペアを作るので良さそう(C.flatten!; C[C.size/2..].zip(C))。どの解説もそういうペアの作り方をしてるので。どの頂点集合も過半数に届かないようにしているのだから、たしかにそれで同一集合からペアを作ることはないみたい。それと、DFS での頂点の並べ方は帰りがけ順でも OK と解説に書いてあった。


2024年07月12日 (金) PS5 のコントローラーって臭くなりやすいと思う。手に汗握る状況が多いというのが根本にあるとしても、PS4 まではコントローラーが臭いとかコントローラーを握っていた手が臭いとかが気になったことはなかった。ウェットティッシュでよく拭いてリセットしても数日で臭くなる。材質かな。表面処理かな。何が違う?


2024年07月08日 (月) 先日自転車のハンドルを掴み損ねて上半身から地面にダイブした。雨の日で手袋をしていたので手は平気。手袋も無事。ズボンの膝がちょっとほつれてるけど穴は空いていない。一番のダメージが肋骨にある。指で押さえると痛む場所が1か所特定できるだけなのだけど、肋骨の痛みによる QOL の低下が著しい。咳をすると痛む。深呼吸をすると痛む。布団でうつぶせになると痛む。日常の、ささいな、何かしらの行動に対するリアクションとして痛みが発生することのなんと不自由でうっとうしいことか。年を取るとたんが絡むんですよ。若い子みたいにのどの奧がつるっとしてないんで。咳払いでいっときの疎通を確保しようとするたび肋骨が痛む。つら。■「雨の日で手袋をしていたので」と書いたことについて。まぎれもない事実なのだけど、雨の日でないなら手袋をしていないという裏読みをさせてしまうとしたらミスリーディングである。ある命題の真偽と裏の真偽に関連はないのだとしても。誤解がないように書くと、雨の日だから雨用の手袋をしていた(晴れの日は晴れ用の手袋をしている)。どちらも手のひらは革で丈夫。もし「手のひら以外は革でない」という裏読みをしたなら、半分間違っている。


2024年07月06日 (土) [AtCoder] 今日はデンソークリエイトプログラミングコンテスト2024(AtCoder Beginner Contest 361)があった。自分のすべての提出。■A 問題「Insert」。問題名の通りに Array#insert を呼び出す。いつまでも引数の順序が覚えられないメソッド。今日はリファレンスを引くのも面倒がってテキトーに位置と値を並べて呼び出して結果を確かめた。■B 問題「Intesection of Cuboids」。現在は修正されているタイトル名のなごりが見える(イン「テ」セクション)。コンテスト中に気が付かなかったのは不覚というほかない。誤字脱字はかなり神経質に駆逐したいタイプなので。さて本題。頭で立体交差を想像するのは難しいけども、これは1次元の交差を3回確かめるだけ。制約を確かめてから、ソートしたりイコールの場合を考慮したりしたけども、今改めて制約を見るとちゃんと不等号で大小関係が規定されていた。目がついていない。言い訳をすると、同じ範囲の制約がたくさん並んでいたから、すべての入力値が範囲内で無制限の値を取るのだと思ったのだった。6つも 12 個も同じようにたくさんでしょうよ。目がついていないのと数が数えられないのと、どちらがましか、言い訳になっているか。■C 問題「Make Them Narrow」。ソートして最小値を決め打つ。Array#each_cons がおそらく線形時間を要するせいで TLE を1回出した。たしか以前も同じメソッドで TLE を出している。学習しないな。だけども、配列の dup や shift、pop では配列の要素レベルのコピーが抑制されると知っているから、配列から固定サイズの部分配列を切り出すのに単位時間しかかからないと期待するのは当然じゃない? each_cons が Array#each に基づいて実装されてるとしても、一度の each_cons 呼び出し(と複数回のブロック実行)で線形時間しかかからないなら TLE にはならなかった。尺取りをするなら TLE にはならない。ブロック実行のたびに線形時間かかっていて、each_cons 全体では2乗の時間がかかっているからこそ TLE になる。これが予想外。■D 問題「Go Stone Puzzle」。制約がごく小さいのでメモして BFS をする。実装でいろいろミスをした。たとえば (1,2)、(3,4)、(5,6) みたいな (奇数番目,偶数番目) のペア単位でしか交換できないと思い込んでいたり。そこはちゃんとサンプルで落とされたけども、見るべき要素数が N ではなく N+2 だったりも。15 分かかった。■E 問題「Tree and Hamilton Path 2」。ARC179-D Portable Gate の簡単バージョン。精進記録はこちら>20240602。根を決めて DFS ですべての頂点を訪れてまた根に戻ることを考えると、すべての辺をきっちり2度ずつ通るのでコストの上限がまず決まる。本問題では根に戻る必要がないのでどれだけのコストが節約できるか。直径。自分の提出がすでに求まっている直径を再帰関数で改めて求めているのは、紆余曲折の結果なのです。引き算で求めるのではなく、2種類の再帰関数で積算して答えを求めようと迷走していたなごり。プライオリティキューを貼ったけど、いらなかったらしい。根からすべての頂点への距離を求めているのだし、各頂点へのパスは1つだけなのだから、それはそう。■F 問題「x = a^b」。苦手な苦手な数学問題。指数を3以上に決め打つなら N 以下の全ての立方数、4乗数、5乗数(って呼ぶのか知らないけども)……を列挙して重複を排除できる。じゃああとは最大で 10^9 個ある平方数をどうやって数えるかだけ。すでに数えた立方数、4乗数……が平方数でもあるかどうかを確かめて重複を除外することでクリアした。この問題の提出でも自分は変なことをしている。b を固定したときの a の最大値を Math.log で求めてからすべての a^b を列挙してるんだけど、それだったら a=1 から始めて N<a^b になるまで a+=1 を繰り返せばいい。コンテスト中はそこまで頭が回らないんだなあ。■G 問題「Go Territory」。解けてないよ。サンプルにあるように囲われている格子点を数えたい。縦横斜めに並んだ石のあいだで UnionFind をして、まずは輪っかを作っているかもしれないグループを特定した。次にグループを構成する石の周囲8マスから BFS を開始して孤立している格子点の島を数えようとした。どこで探索を打ち切るか。グループを構成する石の X 座標 Y 座標の最大最小を限度にして BFS を打ち切って孤立していないと判断をした。これでサンプルは合ったけど、WA があるかもそうだけど TLE は間違いないと思うんだよなあ。おおざっぱに2乗の範囲を塗りつぶそうとしてるわけだから。■コンテスト成績証。黄パフォに限りなく近いいいパフォが出たけども、前回(ABC が Unrated 判定だったので配点と Writer から必敗を覚悟して出た ARC)の緑パフォの傷が癒せただけなんだよなあ。F 問題まで4桁人数が解いてるので早解き回だったみたい。それは配点からも読み取れる。簡単な問題に滅法強いという自己評価を裏切らない結果。■G 問題。自分のやり方で WA になる例。ループが2つ左右にくっついていて、右のループの周辺ということで、右のループの外側、左のループから見れば内側から BFS を開始した場合、打ち切るタイミングを誤る。盤面を BFS のたびにクリアすれば解決するけど、ますますもって TLE が加速する。■■■精進。G 問題。提出 #55351016 (AC / 796 Byte / 571 ms)。kotatsugame さんの動画(【競技プログラミング】ABC361【実況】)で解法を聞いたんですよ。UnionFind をするのは石と石ではなく、縦もしくは横方向に連続した格子点列の隣り合ったもの同士だった。やってることは難しくなくて、付加情報として格子点数を持った UnionFind だけど、頂点番号が与えられているわけではないので、格子点列に自分で番号を割り振らないといけないひと手間がやっかい。Y 座標列をソートし忘れたり、ひと手間に色んなミスがからんでくる。グループの管理と格子点数の管理を同時にやろうとしてグループ0と数0を混同したりもした。また、格子点の総数が数えられなくて答えがなかなか合わなかった。X 座標の最大値が 200000 だとして、0 から 200000 のあいだには 200001 個の格子点があるんですよ(あたりまえ……ではなかったんだなあ)。


2024年07月01日 (月) [AtCoder] 精進。昨日あった ABC360-E「Random Swaps of Balls」。ひとえに、ひとえにデバッグ力が足りなかった。サンプルの2に 3 2 という入力例がある。サンプル1のように解説がないし、出力例が実数ではなく 554580198 (mod 998244353) だということで、途方に暮れていたのが昨日。だけどね、自分で計算すればいいんですよ。昨日の方針だけど、場合の数を K 回数え上げていって、最後に N^{2K} で割ることで確率に変換するようにしていた。ということは、3 2 という入力に対しては9通りの出目が2つ続く 81 通りの場合がうまく数えられていれば良かった。81 に足りなければ遷移の式が誤っているということ。そのようにして今日はサンプルの2が合った。そして次のサンプル3の入力が 4 4。これの答えがまた合わなかったのだけど、同じようにして 4 2 に対する 256 通りの数え漏らしを見つけることでサンプルの3もまた合った。■提出 #55117837 (AC / 362 Byte / 126 ms)。N=1 で WA を出さなかったのはすでに他所で知っていたから。全く警戒していなかった。■この E 問題までささっと解けてまだ不満というのが自分の現状認識なんだけど、また脳みそにクモの巣が張ってきてるみたい。半年後からの挽回に期待!■続けて G 問題 Suitable Edit for LIS にも取り組んで提出したのだけど、#55121924 (WA×8/AC×45)、WA になるケースが全く作れなくてデバッグが進まない。C++ の AC 提出と答えを突き合わせたりしてるんだけど、最初にコピーしてきた提出は長さ6程度のシャッフルした順列に対する答えがおかしかったよ(それでも AC)。2つめにコピーしてきた C++ の AC 提出とは意見の一致を見たので、自分だけが盛大な勘違いをしているということはなさそう。こんなザルなジャッジだったら8個くらいの WA は見逃してくれてもええやろ。■G 問題について現在わかっていること(あるいは勘違いしていること)。操作によってできるのは LIS の長さを +1 することだけ。先頭か末尾の値を含まないで LIS が作れるなら、先頭か末尾の値を操作して +1 できる。では先頭と末尾の値が LIS に不可欠だったら? 適切な位置に LIS に参加しない空き要素があるなら +1 できる。適切とは? 空き要素があってもその前後にある LIS を構成する要素が連番だったら +1 できない。条件はこれだけだと思う。ところで LIS って候補がいくつもあるのが普通。最長の長さを知りたいだけならそれらを区別する必要がないけど、今回は空き要素を挟めるか挟めないかがポイントなので、LIS の個別の列に踏み込んでいかないといけない。添字列に対して LIS を求める操作をして作業配列を上書き更新せずに追記して履歴を残すようにしたらうまくできないかなーと思って書いたのがさっきの提出。なにがうまくないのかわかんない。思いつきでいけるやろって思う方がおかしいか。そうか。■■■通ったー!!! G 問題。提出 #55154669 (AC / 672 Byte / 277 ms)。前の提出が 671 Byte だった。17 行目の <<= にすると WA が AC になった。狭義単調増加だから、値の比較にイコールがないのは一見自然なんだ。でも 17 行目では LIS に含まれない要素をはじいていた。< の否定が >= であるように、そこではイコールが必要だった。なんだー、1文字かー。ランダムケースの生成ルールを A = 1,*([2,3,4]*3).shuffle,5; puts A.size,A*' ' に変えたらすぐに見つかった。同値の要素の重複がキーだった。ともあれ、やろうとしたことがちゃんと AC に繋がっていたのは良かった。■LIS の履歴の活用法について書く。作業配列には通常長さ i の増加列の末尾の値を記録する。最終的に i が取り得る最大値が LIS の長さ。今回は値の位置も知りたいので値の代わりに添字を記録し、さらに履歴も知りたいので各長さ i それぞれに添字列を記録していった。入れ子配列の総要素数は N+(LISの長さ) になる。作業配列には最長に届かなかった短いものも含む全ての長さの増加列の情報が記録されている。これを後ろから見ていくことで LIS の一部ではない要素をはじいていくことができる。値を見ることで添字列の先頭から、添字を見ることで添字列の末尾から取り除いていくことができる。たぶんね。あとは前後の添字列を見比べて LIS に中間値を挿入する添字の空きと値の空きがあるかを確かめる。■■■遅れていたレート更新があったのだけど、B 問題で範囲が間違っていた普通の WA コードを投げた人が Unrated に不満を表明していた。テストケースの制約違反とは関係なく WA だった人も Unrated なの? 確かめたら自分も Unrated で草。4完低パフォだから不満はありませんけども。1≦c≦w という範囲を添字にするときに、c を 0 始まりにするのを忘れて各行1文字目を縦読みするケースが漏れていて WA を1回出したんだよね。


2024年06月26日 (水) 競プロ出身者の使えなさは異常」■すごくありそうだなって思う。全体から見れば一部だし界隈によらず存在する特性でもあるはずだけど、特に優秀で他によりどころがない場合に、ああいう悪い感じに増長してしまうことはあるだろうなと思う。競技プログラミングになじむ時点でその素養は高いかもしれない。もちろん主語がでかいし偏見だし個人を見ろと言いたいし、クソと言っている周囲がクソな環境にずぶずぶにつかったクソである可能性も常に考えている。増長っていうか防衛にも見える、ハリネズミ的な。誰も認めないから主張が先鋭化するんじゃないのか。認めつつ穏当に導くことも、マウントを取り返して黙らせることもできなかった結果ではないのか。なんにせよミスマッチはその通り。お互いに不幸でしたね。