高橋君はある倉庫 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のブログ」)。つまり、大きい方から見てある辺を選ばないで済むのなら、それより小さい辺をすべて選んでもコスト的に見合うということだ。こういうことを書くのが今回初めてというわけでもない。初めてのときは二進数になぞらえて理解してなるほどねと膝を打つ様子を書いたと記憶している(k 桁のフルビットを作るときは 1 を左に k ビットシフトしてから 1 を引きますが、ある１つのビットとその下位フルビットの大小関係はつまりそういうことです)。さておき、じゃあソートして 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 の組み合わせによってあなたがそのナンバーとカードで特定される個人であることを証明することができる。カードは番号の媒体にとどまる存在ではないのです。あえて言うならあなたの代理人となりうるものだというのが自分の理解。代理人という言葉を自分は借金の連帯保証人と同じようなものだと思って使っている。あいつは俺で俺はあいつだからどんな言い逃れもできないという意味で。■ただちょっと思うのは、新しいマイナンバーカードがあっても警察の方で免許証連携の引き継ぎができなかった、あくまでも旧カードが必要というのが理解できなかった。マイナンバーカードを新しくしたからといって別人になるわけではないのだから、旧カードでも新カードでも免許証をくっつけるのに何の違いがあってできるできないという話になるのかわからない。免許証連携をしたマイナンバーカードが仮に同時に２枚存在するようなことが生じたとして、何の問題もないと思うけどどうなんですか。■警察は免許証をマイナンバーカードに準じたレベルで個人を特定して発行しているわけではないということ？ 理論的には誰かの免許を誰のマイナンバーカードにもくっつけることができる？ それを完全には防ぐことができない？ だからせめて唯一性を保証したい？