脳log[20220625]

2022年06月25日 (土) [AtCoder] 今日は 日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257） があった。自分のすべての提出。13 分余分にあれば６完だった！(空しい反実仮想)■特に書くことはないかな。(F 問題までの)傾向としては易化、典型寄りだったと思う。F 問題でも PAST の真ん中あたり(J とか K)に出そうな雰囲気。そういうときに点が取れないでどうするの？■C 問題で質問したよ。S の i 文字目を右から数えるのか左から数えるのか、問題文はわかるように書かれていないし(S=S1S2S3...Sn から成る。Si=1 のとき……とか。「Shortest Good Path」がそんな感じ)、サンプルの S がどれも左右対称だったから手掛かりがなかった。ビットなら LSB から数えるだろ常考、で納得するけども、文字列の常識は知らない。■解けたから簡単だというのは嘘だな。考えたことと罠を書いていこう。■C 問題「Robot Takahashi」。X が実数って書いてあるけど、与えられた数値(W)と、与えられた数値よりも(ちょっとだけ)大きな値だけを試せばいいよね。尺取りをすれば N の制約上限 20 万もクリアできる。与えられた数値よりちょっとだけ大きい値を試す必要があるのは、X 未満の子どもという条件で max(W) を勘定に入れるためには max(W)<X である必要があるから。■D 問題「Jumping Takahashi 2」。問題文を誤読したまま考えていた。つまり、あるジャンプ台からスタートしてジャンプを繰り返しながら全部のジャンプ台を巡らなければいけないのだと思っていた。サンプルを読めば間違いがわかるのだけど、頭の中でひと通り試行錯誤して実装してからサンプルを試す段階で初めて気がついた。ワーシャルフロイド法で解ける。■E 問題「Addition and Multiplication 2」。既視感がある問題。それも WA がいつまでも取れなかったことで記憶に残っている。調べたら初めて参加した ABC の D 問題「Match Matching」のことだった。しかもまだ AC してなかった>自分のすべての提出。ちょうどを要求されていない点で今日の E 問題の方が簡単だったのでは？ その E 問題。問題文を読めばどの i を選ぶかよりも操作回数を最大化することが大事だとわかる。まずは最小コストの数字を使用して桁数を最大化する。次に桁数を減らさない範囲で最大限 i を 9 に置き換える。それから 8,7,... と順番に残された条件の範囲で桁数を減らさない限りにおいて i を i より大きい数字に置き換えていく。罠は答えの出力方法。サンプルに「答えが 64 bit整数型に収まらないこともあることに注意してください」と書いてあるのだけど、これをよくある 32 bit整数型に収まらない場合の警告だと思って、でも上限がどこかに定めてあるんでしょうと問題文をさらったけど見つからなくて、Ruby だからと深く取り合わずに提出したら TLE になった。答えを文字列で持つのが正解。■F 問題「Teleporter Setting」。これも最初は問題文が読めていなかった。求めるのは 1 から N までの最短距離。それに不定なテレポーターがどう寄与するか。不定なテレポーターが寄与しないなら普通に町 1 から BFS した距離表(D1)でもって D1[N] が答えだし、寄与するときに考えるパターンは２通りしかない。つまり、1 から i を目指すより 1 から 0 を目指した方が近いパターンと、N から i を目指すより N から 0 を目指した方が近いパターン。それだけではない気がしたとしても、それだけ。■コンテスト時間中に 4 WA と自分より先を行っていた提出 #32743897 をデバッグしようとして 30 分以上考えている。予想だけど、町 1 と町 N が不定なテレポーター(0)を介して連結な場合が抜けていると思う。たとえば 1-2-0-9-N というグラフ構造のとき、i の値によらず min_a+min_b+2 が答えの候補としてある。