脳log[20230508]

2023年05月08日 (月) [AtCoder] 精進。ARC102-D「All Your Paths are Different Lengths」(青 diff)。やることはまあまあすぐにわかる。数値の２進表現をグラフに直す。L と N の制約がそのような配分になっている。ビットごとに頂点を割り当てて隣接ビットへ１の辺(重み２べき)と０の辺(重み０)を張る。それだけだと L がフルビットでないときに困るけど、１のビットに対応してそのビットが最初に倒されるビットである場合を表す辺を張る。■提出 #41255174 (WA×7)。こういうジャッジスクリプトを使っていた>judge.rb27。入力される L の上限は 20 ビットある。そのときに N=21 となる答えを返していたのが WA の原因。N は 20 以下に制限されている。L のビット数＋始点１＋終点１くらいの頂点を使わせてくれてもいいと思うけど、L のビット数と同じだけしか許されていない。■提出 #41257168 (AC)。すごく苦しんだし、その過程では３進数でやろうかとも考えたけど、結局、始点と始点に隣接する頂点を機械的にマージすることで答えが合った。いらん苦労だったと思う。制約が無駄に厳しかった。あるいは上手い考え方があったのか。■提出 #41260968 (AC)。３進数でやった。たぶん最大ケースが L=531440(10)=222222222222(3) で、解答が N=13;M=57 になる。M が上限の 60 に近いがセーフ。あんまりややこしいので初めて秘密兵器(ノート)を使った。ノートを見れば明らかだけど、２進数であるか３進数であるかにかかわらず、自分が考えるとどうしても桁数＋G(終点)の頂点を使ってしまう。MSB を S(始点)として使用してもだ。だから２進数でやったときに L のビット数＋１を使ってしまって制約を１だけ超えてしまった。■３進数で真の最大ケースは L=885734(10)=1122222222222(3) だったかも。このとき解答は N=14;M=60 になる。上限いっぱいでぎりぎりセーフ。辺の制約(M)がキリよくおおざっぱなのに対して頂点の制約(N)がタイト過ぎて無駄に解答の様式(=ただの形。記述の癖以上のものではない)を縛ってると思うんだよな。