ichirin2501's diary

いっちりーん。

AOJ1021 && SRM211

Emacs-like Editor

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/problem.jsp?vol=10&id=1021&tle=1&mle=32768&title=Emacs-like%20Editor&doc=4&lang=jp
仕様と異なる動作を含んでしまい、苦戦した。
そのまま実装するだけ、何がだめなんだよウワーン状態でしたw
問題文を正しく読めということ…orz
文章を二次元配列で表現して解いたけど、一次元配列のまま処理したほうが楽かも。
ソースコードをアップしようと思ったら既に削除してた、うっかりw
今度からはAOJのコードはアップしていく。

SRM211 DIV1 500pt

grafixMask
チュートリアルから。
問題文の意味が分からず、いきなりソースコードを拝見することに。
ソースコードを読んで漸く問題文の意味を理解する。
問題を理解したときに思い付いたのは、
二次元配列を左上から走査して上、左方向にマーキングがあったら同じマーキングをそのマスにも施す。
ない場合は新しいマーキングを施す。異なるマーキング同士が存在した場合は低い価値のマーキングを優先し、
マーキング個数を足す。的な処理。
計算量はO(n*m)になるけど、面倒な処理になりそうって思った。
でも、1つの色で領域を塗り潰すという処理を先行させれば計算量は増えるけど、実装は簡単になる。
拝見させて頂いたソースコードの解法がそれだった。
集合的な考え方?みたいな感じなのかな。問題に捉え方って他に何があるんだろう?
集合、グラフ…あれ、思い付かない…