脳log[20221204]

2022年12月04日 (日) [AtCoder] 精進１。CODE FESTIVAL 2016 qual B-C「Gr-idian MST」(青 diff)。１辺が 10 万のグリッドだから辺に沿った処理は通るけど (辺×辺) の処理は通らない。UnionFind のような具体的個別的な処理ではなく、何か規則に沿って処理をまとめなければいけない。まず、造る道路の数は頂点数マイナス１に決まっている。最も低コストな道路はそれが縦であれ横であれ造れるだけ造らないという選択肢がない。では２番目３番目のコストの道路は……。提出 #37039797 (AC / 167 Byte / 173 ms)。あるコストで造れる行方向(列方向)の道路を１通り造ったら、行に対しては列、列に対しては行方向の道路を造る際の必要数が１つ減る。その繰り返し。■精進２。同-D「Greedy customers」(青 diff)。まず単純なケースとして列が昇順の場合と降順の場合を考えた。降順の場合、後ろの人を狙って物を買わせることはできない。昇順の場合はできるけど、いずれ前の人が邪魔になる。先頭の人の所持金を１刻みで残金１まで毟り取れることは決まっているしそうしない理由もない。先頭の人から順番に狙い撃ちにするので良さそう。１人目の所持金を１まで減らしたとして２人目の所持金が１のときは？ ２のときは？ ３のときは？ ４のときは？ ５のときは？ 提出 #37040436 (AC / 120 Byte / 89 ms)。よーく考えた。WA になる例外ケースがありそうな気がしたので先頭の要素だけ特別扱いしたりもした。■精進３。CODE FESTIVAL 2016 Final (Parallel)-C「Interpretation」(水 diff)。以前に見た問題だけどまだ解けていなかった。さすがに前回と前々回の ABC-F がともに UnionFind がらみだったので(でもどちらも時間内には解けなかった)、その適応を見逃したりはしない。提出 #37040679 (AC / 327 Byte / 175 ms)。人と言語を２列に並べた２部グラフを考える。今回は解法から発想したので気付かないまま、いわば偶然 AC に至ってしまったけど、問題文を読解するにあたってコミュニケーションが取れることの条件「2 人ともが話すことの出来る言語が存在する」ことと「2 人ともが X とコミュニケーションを取ることが出来る」ことの違いをよく意識しなければいけない。２つの条件でそれぞれ使われている「共通言語が存在する」ことと「コミュニケーションが取れる」ことはイコールではない。共通言語の存在は再帰関数の停止条件であり、コミュニケーションが取れることは共通言語の存在により再帰的に定義されている。後になって問題を反芻していたとき、X 以外の別の人間を介在させてコミュニケーションが取れると判断してはいけない気がして、なんで AC だったのか疑問に思って問題を読み直して、表現の違いに気がついたのだった。■なんだかんだで青 diff が半分くらい埋まってきてるので、そろそろ青入りさせてくれてもいいんですよ。