メモ@inudaisho

君見ずや出版 / 興味次第の調べ物置き場

AtCoder ABC036 D 塗り絵

 ABC050 D - Xor Sum がどうやっても飲みこめず、自信をなくしそうだったのでとりあえず他のに手を出すことにしてちょこちょこやっていたがちょっと固いのにあたったのでまた何か書こうとおもう。

XorSum で見る問題の構造と解法

 AtCoder のABCのDをだいたい一割くらいこなしたので、ちょっと思うところを書いておくと、

f:id:inudaisho:20181027190928j:plain

 AtCoder にかぎらずだが、問題にたいする答を出すときは、まず構造を把握し、それから解法を考え、実装するという三段階がある。まずは問題が何を意味しているのか、それがわからないと何もできない。これが構造を把握するということで、XorSum でいうと論理演算の構造がわかっていないと話が進まない。公式解法を見ればいちおう解法の手掛かりはかいてある。人の書いたものをみれば、実装されたものも見れる。しかし論理演算の構造がわかっていないので、どういうロジックでそうなるのか飲みこめない。xor と and でたしかに足し算になることがわかっても、減算器の要領だよと言われてもどうも飲みこめない。0/1 の世界で2はどこから来てどこへ行くのか... どうやったら腹に落ちるのか... 論理演算やビット演算をたくさんやってみて慣れるしかないのかな?

ABC036 D 塗り絵

 XorSum に比べるとこっちは把握しやすい。問題は頂点の塗り分けで、グラフ理論の本に書いてあった四色問題みたいなやつの話だなとわかる。黒白二色で隣同士黒黒とは塗れない。とりあえず「島」と「橋」を絵にして場合分けすると、入力例2はこんな感じになる。

f:id:inudaisho:20181027194438p:plain

 1を根にしてそこで白黒置いて場合分けすると分岐のところで混乱する。結局中心の8で白黒分けてみたらわかりやすく、各枝の末端のパターンをかけて足すと出力例2になる。なるほどパターンがあるから動的計画法いけそうだが... 最初分岐で混乱して結局8を中心にしたように、枝の分岐はどうあつかえばいいのだろう。DPテーブルで描けるようなものなのだろうか。わからん。パターンも絵で書けるだけでそれをロジックに落とせない。XorSum とは逆の状態、構造はわかったが実装がわからんという状態だ。

木DP

 そこで公式解法をみると「木DP」で遠いところから積みあげていけばよい、関数はこれこれと書いてある。

どこかを根にして根に向かって xが親、y1 .. yk が子として、f(x)はxが白黒の場合、g(x)はxが黒の場合

f(x) = g(x) + g(y1) * g(y2) * .. * g(yk)

g(x) = f(y1) * f(y2) * ... * f(yk)

 うーん?なんかそれっぽいが.... とおもってここで逡巡。その中心となる漸化式はともかく、他の人の解答をみると二段階で書いてある。だが、公式解法から自分が思いつくのは三段階。木を構築し、レベル分けし、遠いところから数えあげていくという三段階だ。うーん。人のより一手間かかってる分遅くなりそうだ.... とはいえいきなり作るのもおもいつかない...

 とここで悩むのがまちがっていて、とりあえず書けばよかったのだ。自分の人生こういうところで間違えてきたんだと思うがもう44にもなったらとりかえしがつかない。どうでもいい逡巡についてはここまでにして、結局書いてみた。

            aFChild = 1
            aGChild = 1
            for y in dsChild:
                aGChild *= aG[y] % iD
                aFChild *= aF[y] % iD
            aG[x] = aFChild
            aF[x] = aG[x] + aGChild

 なるほど。書いてみると、末端の子がないところでもうまく解釈できるようになっている。すごいスマートだな。こんなの自分ではどうしても思いつかなそう。絵にできてもここまで明晰にロジックに落とせるかといえると無理。こういうところですこし壁を感じてしまう。まぁ人それぞれ向き不向きがあるからしかたないか。

 それはともかく、とりあえず書いたものの遅いんだろうな... とおもいながら出してみたらPython3の中ではかなり速かった。うーん。毎度のことながらどういうことなんだ? やっぱりPytho(禁則事項です)

木DP と動的計画法

 動的計画法というのはDPテーブルでどうこうするものだとおもっていたが、今回木DPについて調べたとき、†全方位木DP† については詳しいのがあったが、肝心の普通の木DPの記事があんまりみつからなかったので英語まで手をのばした。そうすると、やっぱりこっちでも普通に DFS書いてぐるぐるまわしている。木だからそうするしかないよな、とはおもいつつ、英語だとDPは単に "Dynamic Programming" なので、日本語でいう「動的計画法」の語感がもつ「なにか特定の一技法」よりももっと大雑把な概念で、まるで「細かいことはいいから波に体を任せなさい。そうすれば答えは自ずから出る」とでも言われてるような気がした。

Dynamic Programming (Dover Books on Computer Science)

Dynamic Programming (Dover Books on Computer Science)