読者です 読者をやめる 読者になる 読者になる

phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

GCJ2017 Round1A A. Alphabet Cake

問題

R*Cのグリッドに大文字アルファベットまたは「?」が書かれている。
各アルファベットは高々1回しか出現しない。
「?」は出現したアルファベットのどれかを割り当てることができる。
各アルファベットを長方形を維持した状態で拡張し、すべての「?」をどれかのアルファベットに割り当てたい。
割りあてた後の「?」のない状態を1つ出力せよ。

制約

1 <= R,C <= 25

解説

まずすべての行について、アルファベットを適当に横方向(左右)に全部を伸ばす。
これで「?」が残っている場合は、その行すべてが「?」になっているはずである。
この「?」のみの行は上か下で埋まっているアルファベットを行ごと伸ばせは長方形を維持して埋められる。

反省

大切な気づきは、「行と列が独立に計算できる」こと。
最初単純な左右に伸ばす方法を考えてたのに、考えてるうちに、上下方向も同時に考える方向に進んでしまってハマった。
(左右上下で長方形を考えると、考えるべきパターンがかなり多くなってしまう)
結局本番は「考える長方形候補を減らす&「?」が残らないようにするルール」みたいなのを書いてしまった。。。