脳log[20260308]

2026年03月08日 (日) [AtCoder] 昨日の AtCoder Beginner Contest 448。書くのが一日遅れたのは ShapeHero Factory (PS5 のゲーム) に生活リズムを破壊されているからです。■A 問題 chmin。AWC っぽさを感じてしまう。AWC のおかげでサンプルを最後まで試さない怠惰さを身に付けつつあります。■B 問題 Pepper Addiction。これも AWC っぽさを感じてしまう。くどくどと書いてあるけど、結局こういうことじゃん、というあたりに。■C 問題 Except and Min。K が５以下だとちゃんと目に入りました。トップ６だけで答えが出せるということ。■D 問題 Integer-duplicated Path。木の問題。同じ値の頂点とそのつなぎとなる頂点だけからなる木を考えるのかなと思ったけど、それで答えを出そうとすると同じ頂点を何度も答えにカウントする無駄が生じて許されない。頂点１からのパスだというのだから１を根にして考えるのが都合が良い。深さ優先で潜りながら値をカウントしていく。カウンターは使い回すので関数に入ったときにインクリメントしたものを出るときにデクリメントする。同じ値が２度目に出てきたらその子孫はすべて Yes。■E 問題 Simple Division。10007 という、AtCoder では見ないけど他所ではたまに見る数字。irb で調べたら素数ではあるらしい。しばし考えた。E 問題だけどこの問題の難しさがどこにあるのだろうかと。M で切り捨て除算したものを 10007 で割った余りが知りたい。N はとても大きい。当然 N は mod を取った状態で扱うわけだけど、mod 10007 の値を M で割ることには意味がない。mod M の値を 10007 で割った余りにも意味がない。でも、mod 10007M の値には意味がある。10007M が 10 の 8 乗程度に抑えられていることとも整合する。えっと、E 問題ならではの落とし穴がどこにあるのだろうか。ちなみに AC までには 30 分かかりました。何に時間を使ったか。ランレングス圧縮された N の値を展開するときに 111...111 という数字が必要になるのだけど、これを作る段階で困ってしまった。え、どうやって作るの？ 1 と 1 から 11 を作り、11 と 11 から 1111 を作るというように、繰り返し二乗法の要領で 111...1 を作るのに一番時間がかかった。よくわからないんだけど、10000...0 から 1 を引いたら 9999...9 になるので、9 で割ると 1111...1 になるらしいですよ。二進数だったら 1 を引いたときに 1 の列になるけど、10 進数だと 9 の列にしかならないんだよなあ、というところまでしか考えませんでした。こちらの方法はスマートだけど M が素数とは限らないので 10007M も素数ではなく、9 の逆元が存在しない可能性があるとかないとかで困ってしまうらしい。でも mod の値に 9 を混ぜておけば無限数列を mod 幅で折り畳んで重ねるときに幅 9 の境界が mod 幅の境界とも一致するので、不都合な重ね合わせは発生せず、普通に 9 で割ることができるんじゃないかな。よくわかんないのでやってみて結果を確かめるだけなんだけど。■F 問題 Authentic Traveling Salesman Problem。ふわっとしていて困ってしまう。サンプルを読むまで気がつかなかったんだけど、最小値を求める問題ではなかった。10 の 10 乗秒以内というのが、テキトーな数字ではなくこの問題の核心なのだった。10 の 10 乗を移動回数(N)で割ってみると 166666。X(Y)座標単独への割り当ては半分の 83333。X(Y)の値域は 0 から 20000000 まで。あんまりでたらめな移動をしない限りはなんとかなりそうな気がしませんか。なんとかならなかったんですけどね。グリッドを縦横半分半分ということで４分割して、それを再帰的に何度か繰り返して、それぞれの階層で４面を順になぞるように訪問先を選ぶようにした。スタート地点が好きに選べないのでどういうなぞり方をすれば効率的に網羅できるのかよくわからなかったんだよね。結局あんまり関係はなかったんだけど、「Cosmic Rays」という問題を思い出した。思い出せるということは印象的な問題だったということで、あれもそうだけどこの F 問題もわりと好き。テキトーにうまくやれよという感じが。■自分のすべての提出。コンテスト成績証。