脳log[20240512]

2024年05月12日 (日) [AtCoder] 今日は AtCoder Regular Contest 177 があった。コンテスト成績証。自分のすべての提出。AC までの所要時間が、A=５分、B=８分半、C=20分。計34分で３問解いておしまい。昨日に続いて Highest 更新は嬉しいんだけど、焦らしますねえ。あと +2 で青タッチだよ。青になって青を維持するためには ABC-F が半分以上の確率で得点できないと無理だと思ってるよ。今は精進で６割埋められるくらいかな。得点にできていない。ではふりかえり。■A 問題「Exchange」。DP でさえないし、愚直に１枚ずつカウントして許される制約。日本の硬貨は５倍２倍５倍２倍５倍と規則正しく増えていって完全に小が大をかねるので、使いにくい大きい硬貨から貪欲に使っていく。■B 問題「Puzzle of Lamps」。左からしか操作ができないので、一番右から目当ての状態を作っていく。■C 問題「Routing」。赤の道と青の道が X 字に交差するので、どちらの色でもある紫色を最低限だけ配置する。最初はちょっと難しく考えすぎていた。赤にとっての最善というのは、(1,1)が属する赤の島と(N,N)が属する赤の島を赤の島を経由しながら紫の道で連結していくことで求められる。それは 01BFS でできる。青の道の最善も同様にできる。で、考えすぎていたのは、それぞれにとっては必ずしも最善ではないけども、共通部分を大きく取ることで全体として紫の数を最小化できるケースがあるのかなと思ったこと。そんなケースはない。赤にとっての紫の道は必ず青を変化させているし、逆に、青にとっての紫の道は必ず赤を変化させている。お互いの紫の道に共通部分はない。じゃあ 01BFS を２回やってコストの和を答えにするだけ。■D 問題「Earthquakes」。DP ですよね。前からの値と後ろからの値を突き合わせて答えを出すのかなと。2^N 倍した数を答えにするというから、確率ではなく場合の数を足し合わせていったものがそのまま答えになるのかなと。正しい答えが出て来ませんでした。