高橋君はある倉庫 s（1≤s≤N）からスタートし、荷物を持っていない状態で東へ向かって倉庫を順に訪れます」)疑っている。」「サンプルが合わなかったので、基準値 S[i] を S[s-1] とする。つまり、スタート地点の荷物を拾うということであり、何も持たないで東へ向かう時間は存在しないということだ。瞬間というのを幅ゼロの時間だと定義すればそういう瞬間はあったのかもしれないが、そんなことを言い張るやつは存在を抹消されても文句は言わせない。」■やっぱり日本語の問題になるんだよな。最初は「右向きで一列ってどんな状態？」「握手とは」「時間の単位」「すなわち」がひっかかったし(20260212)、その次は「負の枚数のコインを得るゲーム」が人間にはない発想でおもしろかった(20260224)。今日はスタート地点にある荷物を必ず拾うというときに、「
荷物を持っていない状態で東へ向かって」と表現することはありえないということを書いた。今読み返すと今日もすなわちに続けて「
倉庫 s からスタートした場合、高橋君は倉庫 s,s+1,s+2,… を順に訪れ、累積の荷物の重量 As+As+1+⋯」と書かれてあって、そこで初めて問題を解く情報が揃う状況ではあったらしい。■すでに明らかではあったことをもう一度書くと、AI 作問に対する適切な態度とは、冗長な文章から必要な情報だけを拾い上げ、蛇足、論理の飛躍、不適切な言い回しなど、無視しなければいけないものを素早く無視する能力が一番問われている。じっくり読んでも困惑が深まるだけで馬鹿を見る。だけどこういう読み方って、自分にとって都合のいい部分だけを都合のいいように読む読み方と同じであって、こういう読み方ばかり訓練されてこれしかできないと問題よ。
/(A+)/ で split するのか /([^A])/ で split するのかということを。あとは入力によらず処理を統一するために入力の頭に必ず A を付加し、末尾に必ず AZ を付加するなどした(答えは変わらない)。そうすると split(/([^A])/) した結果が必ず偶数になって都合が良い。S と T をそれぞれ split して、偶数番目の比較で判定ができ、奇数番目の比較で答えが求まる。abs を付け忘れてサンプルが合わない。11 分かかったので D 問題より難しい。■D 問題 Take ABC 2。D は DP の D……ではありませんでした。ただの貪欲。最も左にある i を使用しない理由がないし、そのときに、i より右にあって最も左にある j を使用しない理由がない。最初に入力をスキャンして A、B、C に対応した i,j,k の列を用意しておいて、前から順に使えるものを使っていく(#73691658)。事前準備なしのバージョンはもっとシンプル(#73746369)。A の数と AB の数と ABC の数を管理しておき、A への遷移、A から AB への遷移、AB から ABC への遷移を文字列に沿って実行する。■E 問題 Divide Graph。辺のコストが倍々になっていくというのが特徴。この特徴をどう読めばいいのかは chokudai さんの典型に関するブログで読んだ(「競技プログラミングの強みと「典型力」について - chokudaiのブログ」)。つまり、大きい方から見てある辺を選ばないで済むのなら、それより小さい辺をすべて選んでもコスト的に見合うということだ。こういうことを書くのが今回初めてというわけでもない。初めてのときは二進数になぞらえて理解してなるほどねと膝を打つ様子を書いたと記憶している。さておき、じゃあソートして UnionFind だねというのが考えずにわかるんだけど、結局実装して提出するまでには 20 分かかるんですね。サンプルで気づいた見落としは、あるボーダーラインがわかったとして、それ以降のすべての辺を必ずしも選ばなくてもいい、ということ。その判定をするためにはボーダーラインを見つけるための UnionFind を寸止めの状態に保つ必要があって、そのへんでごちゃごちゃと場合分けが増えて時間を食った。■F 問題 Centipede Graph。以前にも似た問題があったかな。アルカンの問題。今日は両端の水素が１つずつ少ない。末端から積み上げていく DP を最初は検討したけど、積み上げていく段階では答えが出せない。全方位木 DP ってこと？ 結局はトップダウンで実装をしてそれがやりやすかった。まずコアとなる頂点を１つ決める。隣接頂点ごとにどれだけムカデの体節を伸ばしていけるかがわかれば、あとは最長の２つを選んで組み合わせたり１を足したりなんだりごちゃごちゃやって答えが求まる。「どれだけムカデの体節を伸ばしていけるか」を効率良く求めるのはメモ化再帰で実装した。一度の呼び出しで答えをすべて用意することはできない。呼び出し元を呼び出し返すことができないからだ。少なくとも２つの隣接頂点から呼び出されて初めてメモが完成する。かといって隣接頂点リストを呼び出しのたびに何度も走査すると星形グラフで死ぬので、リストは破壊的に消費することとした。一方向にどれだけ体節を伸ばせるかと、体節と体節を組み合わせて全長がいくつになるか、どちらも答えが１通りや２通りではなく計算が間違いやすくなっている。25 分で１ペナを出して、５分で修正して AC。実装がトップダウンで素直だったから凡ミスしかないと確信できたし読解もスムーズで頭から一読してバグが見つかった。時間が 20 分余ってしまった。625 点の G 問題にできることはありません。真ん中２つの使い回しが総当たりできるならなんとかなるかもしれないけど(トップ４)、それができないのではね。■自分のすべての提出。コンテスト成績証。瓦増えず。■F 問題。自分の実装(#73718005 の 18 行目)にバグがあると思ったけどバグはなかった。トップ２をメモして答えに利用しているのだけど、要素数が２のときの順序が追加された順で不定。でも要素数が２しかないときは答えが定数なのでセーフ。こんなのが原因で WA になったらリカバリーできないぜ。あと、他の人の提出が UnionFind とか直径とかいろいろ謎。次数が３以上の頂点だけのグラフを考えるのだろうか。いや４以上。端っこの処理が難しくない？ あとたぶんボトムアップで積み上げる木 DP でもやっぱりできるような気がしたな(全方位木 DP でなく)。２通りを数える必要があって、自身が中間の体節になる場合と、一方の端になる場合の両方を考えていくことで、行って戻る全方位でなく行きっぱなしの道中ですべての答えが列挙できる(たぶん)。■■■F 問題。ボトムアップで積み上げる木 DP バージョン。たいへん厳しい。じっくり丁寧にコメント付きで書いたけど WA×34、WA×25 のち AC。大枠はさっき書いた通り、自身が末端になるケースと自身が中間ノードになるケースを数える。それが WA×34。忘れてはいけないのが、自身が末端かつ唯一のノードになる場合で、必要な子の数が１つ減るので答えがゼロかイチかが変わってくる。それで WA×25。さらに、親に伝える数字には親を勘定に入れてはいけないけど、自身が答えを作るときには親を子の１つとしてカウントすることで他の子の要求数を減らすことができる。値としては同じものが含まれるとしても親に伝えるものと自身で使うもの、７つも８つもの数字を頂点ごとに取り扱って考え漏らさないのはとても難しい。一度 AC を出した後でよくよくわかっていても間違えるのだから、実装方針で当たりを引くという幸運があったのだとよくわかった。www. も省略してアドレスを表示するらしい。だから同じように example.com とアドレスが表示されていても、ページが表示できていたり(example.com にアクセスしている)、できていなかったりする(www.example.com にアクセスしている)。自分が使う Firefox にはそういうごまかしや視認性を下げる装飾(URL の特定の部分を薄くするとか)は一切させないけど、www があってもなくてもどうでもいいようなものだという見かたは否定しない。だからこそ **www を省かなくてはアクセスできない** という現状はアホの極みだと思うんだよね。伝わらないんだけど。マイナンバーは「番号」であり、カードは媒体です」と書いておられるけども、これはちょっと誤認があると思った。番号は個人の識別子ではあるけども、あなたがその番号で特定される個人であることを保証するものではない。一方でカードは、その所有と PIN の組み合わせによってあなたがそのナンバーとカードで特定される個人であることを証明することができる。カードは番号の媒体にとどまる存在ではないのです。あえて言うならあなたの代理人となりうるものだというのが自分の理解。代理人という言葉を自分は借金の連帯保証人と同じようなものだと思って使っている。あいつは俺で俺はあいつだからどんな言い逃れもできないという意味で。■ただちょっと思うのは、新しいマイナンバーカードがあっても警察の方で免許証連携の引き継ぎができなかった、あくまでも旧カードが必要というのが理解できなかった。マイナンバーカードを新しくしたからといって別人になるわけではないのだから、旧カードでも新カードでも免許証をくっつけるのに何の違いがあってできるできないという話になるのかわからない。免許証連携をしたマイナンバーカードが仮に同時に２枚存在するようなことが生じたとして、何の問題もないと思うけどどうなんですか。■警察は免許証をマイナンバーカードに準じたレベルで個人を特定して発行しているわけではないということ？ 理論的には誰かの免許を誰のマイナンバーカードにもくっつけることができる？ それを完全には防ぐことができない？ だからせめて唯一性を保証したい？
require 'prime'、Integer#prime_division とか、約数列挙とか、素数を列挙してからの試し割りとか、だいたい通らない。だけど絶対に通らない問題というのは数えるほどしかないし(少ないけどあります)、うまいやり方で余裕で通す人もいたりするものだから、結局は己の至らなさにはね返ってくるのであって、不満のはけ口はありません。残念。精進しような。■D 問題。Ruby で一番最初の AC であるこちらの提出 #73307835。答えの座標が X と Y のどちらか一方が１に固定されている。なんでそれでいいのかわからなくてスクリプトに手を加えてピース番号をグリッドにプロットしてみたけど、番号に重なりはなかった。全然わからない。……。お風呂でイメージしてきた。(1,1) から遠いところから切り落としては全体のサイズを縮めていく、という過程を考えれば、どのピースも (1,1) から右または下にどれだけ離れているかという尺度で特定できる……らしいですよ。■E 問題。Ruby で最初の AC がこちら (#73334218)。require 'prime' しないで素数の倍数に素因数をメモすることで素数を列挙している。自分は素数を判定する方法としてこのやり方を知っているけど、素因数を列挙するための情報源としての利用法は知らなかった。素数ではない(合成数である)数のスロットには素数のひとつが記録されていて、それにより自身が素数ではないことが知れる。それだけではなかった。ここで合成数を n、記録されていた素因数を p として、n = n/p を繰り返して n が 1 に至るまでには素因数の指数の和と同じ数のステップが存在し、その過程ですべての素因数を指数個分ずつ拾い集めることができる、ということらしい。すご。■まねしたのに通らへん。提出 #73350310 (TLE×2)。書き方か。step メソッドを while ループに書き換えたら通った。提出 #73350361 (AC / 1830 ms)。やはり while。while 文は(ブロック付き)メソッドより速い。■F 問題 Exactly K Steps 2。何重にも重なったループを書こうとして書き切れなかったけど、行列の文字が見えたら行列の掛け算をイメージしてループを書く助けにできる。提出 #73353560 (TLE×22/AC×21)。ダメです。行列計算は N の３乗だったような気がしますが、log(K)N^3≦3000万で通りませんか。F 問題で行列計算やるだけは考えが甘いですか。■E 問題の高速素因数分解に関連して ABC177-E の解説が挙げられており、それがまさしくさっき言及した Coprime の問題だったんだけど、えっと、自分はまだこの緑 diff の問題を通しておりませんでした。緑埋めをしているときに埋め切れず、水埋めをしているときにも何度もふりかえってははね返され、そして現在に至る。もう諦めて忘れてしまったみたい。■精進。ABC177-E「Coprime」。Coprime と名の付く類題に至るまで苦手意識を植え付けられたいわくつきの問題。Coprime 恐怖症の元凶。今日最初に書いた解答は ABC445-E にならって素因数分解をしてからそれを使って判定をするものだったが、これは全く望みがなかった。なぜって pairwise coprime を判定するのに全組み合わせを考えると O(N^2) になるから。N の上限が 100 万だというのにそれは無理。５年前の自分ですらそんな馬鹿はやっていなかった (#19442249)。あらためて考えると、各素数について、それを因数とする A 数列の要素がいくつあるかを数えて、その最大値がいくつかを見れば良い。最大値が 0 なら A 数列はどの要素も素因数を持たない(すべて１)ということ。最大値が１なら、どのペアをとっても共通の素数を因数に持つことがないということなので pairwise coprime。最大値が N なら全要素に共通の素因数が存在するということなので not coprime。残る２以上 N 未満の場合が setwise coprime になる。提出 #73355090 (AC / 560 ms)。たしかに実装内容だけ見れば緑 diff だけど、書き方がひと通りでなく、他のどの書き方をしても Ruby では通らないということで、見た目以上の難易度になっていたと思う。■他の人の提出を見ると、素数列挙は require 'prime' でも良いらしい。pairwise coprime を判定するのに全組み合わせを考えるのではなくセグメント木のようなピラミッドを考えると Bignum を頼ることになりそうだけど log(N) ステップで判定ができて間に合うらしい。なんだ AC をとるのに色々やり方があるじゃないか。お前があほなだけやったか。だって今日初めてある１つの値が 0 から N の範囲のどこに位置しているかによって分類できるという問題の構造に気がついたわけなので、ぼけなのは間違いない。■■■E 問題。TLE だった最初の提出 #73314590 だけど、１行目の require 'prime' を require 'faster_prime' に書き換えたものが余裕の AC だった (#73445802 / AC / 1361 ms)。これはくやしい。ABD の３完と、40 分残しての ABDE ４完でどれだけパフォーマンスが違っただろう。faster_prime ってなんぞ？ と検索してみたら、mame さんの GitHub が出てきた (mame/faster_prime: A faster substitute for `lib/prime.rb`.)。これは信用できるなあ。gem install faster_prime したのでローカルでテストできるし積極的に使っていきたい。N 人の参加者が一列に、全員同じ方向（右向き）を向いて並んでおり」 右向きとやけに具体的に書かれているけど、前後左右どちらを向いているとしても同じことなので意味のない情報。さらに、これだけでは情景が想像できない。同じ向きを向いて横隊を作っているのか縦隊を作っているのかがわからない。だからその後の「
全員が同じ方向を向いて一列に並んでいるため、隣り合う2人の参加者が握手をするとき、左側の参加者（番号が小さい方）の右手と、右側の参加者（番号が大きい方）の左手が触れ合います。」という論理がナンセンスに基づいている。むしろ２番目の文の前半部分はなかった方が、追加の情報から逆算して実際の並びはこうだったのだなと補完することができた。そして、ここで説明される行為を握手とは呼ばない。握手とは(直前までどちらを向いていようとも)向かい合ってするものだ。慣れていれば競プロ的な設定(隣り合った人が右手と左手をつなぐ。１番の人の左手と N 番の人の右手は余る)の肉付けに失敗したのねと了解できるけども、まじめな初心者ほど困惑するのでは？ 世の中には文字とみれば先頭から末尾まで１文字ずつなめるようにしか読めない人間がいるのです。そういう人を指してまじめと表しました。■■■４日目の「バッテリー残量」についてはソースコードにコメントとして書いた。「与えられる時刻に単位がないが、放電速度は mAh/s で与えられている。s が second (秒) の略であるとしても、「時刻(無単位)」との換算をどう考えるか。すなわち以下で具体的な式が与えられているので解けるが、まったくすなわちではない。これは定義であり、すなわちより前には何もなく、今この式でこうと決めたのだ。」■ではどういう表現ができたか。単位時間という言葉が使われていたように思う。時間の１つ分。時刻が１つ進んだときの間隔。「単位時間当たり Bi mAh バッテリー残量が低下する」みたいな。具体的な時間の単位が時間なら１時間当たりだし、分なら１分当たりになるところが、単位を特定しない場合には単位時間当たりになるのではないか。子供のときはよくわからん表現だと思っていたが、他にはなかったのかなと今では納得できる。単位という言葉に内包されているからか１という数字は明示されていない(１単位時間当たりではなかった)。そのこともよくわからん原因のひとつだったと思う。単位という言葉にそこまで明確な輪郭がまだ与えられていなかったので(単が一だとかもまだ意識していない)。