Gori#016(ABC036)

問題 (opens new window)

B - 回転

概要

$N \times N$の文字列を90度回転させて出力せよ.

解法

• $\color{red}{\downarrow}\color{blue}{\rightarrow}$の入力を$\color{blue}{\downarrow}\color{red}{\leftarrow}$に変換してやれば良い.
• 出力部分は以下の通り.

for(int wi=0;wi<n;++wi){
  for(int hi=n-1;hi>=0;++hi){
    cout << s[hi][wi];
  } 
  cout << endl;
}       

提出 (opens new window)

C - 座圧

概要

• $a_1, ..., a_n$が与えられた時, 座圧した結果の文字列に変換して出力せよ.
• e.g.)
• 3 3 1 6 1
• ->
• 1 1 0 2 0

解法

ソートして1から割り振ればよい.
が, これは長いので, std::mapを用いた公式解にしてみる.

• mapに$a_1$,...,$a_n$をキーとして追加

• mapではキーが小さい方から0, ..., nを割り当てる

• mapのa_1, ..., a_nを参照する.

• map解 (opens new window)

• sort解(こちらの方が高速だった) (opens new window)

D - 塗り絵

概要

• $N$個の島が$N-1$本の橋で繋がっている.
• この時, 各島を白と黒を使って色塗りする時の塗り方は何通りか?
• ただし, 橋の両端の島が黒になってはならない.

解法

Editorialに沿って解く.

$N$頂点, $N-1$辺なので, このグラフは木であることがわかる.
その上で, 木の任意の頂点の通り数を, その頂点の子の通り数を用いて表したい($\because$ DPの漸化式を作りたい)

$f(x), g(x)$を以下のように定義する.

$f(x) :=$ 頂点$x$を根とする部分木を白と黒で塗る時の通り数.
(ここで, 頂点$x$は白でも黒でも良い)

$g(x) :=$ 頂点$x$を根とする部分木を白と黒で塗る時の通り数. (ただし, 頂点$x$は黒でなければならない)

頂点$x$が白の時

頂点$x$が白だった時を考える.
頂点$x$が白の時, その子は白でも黒でも良い.

したがって, 頂点$x$の子を$y_1, ..., y_k$とすると,
この時の頂点$x$の通り数は, $\displaystyle{\prod_{i=1}^{k} f(y_i)}$となる.
この式の意味は, 具体的に書き出してみれば分かるので, そこは紙にでも書いてみると良いと思う.

頂点$x$が黒の時

頂点$x$が黒だった時を考える.
頂点$x$が黒の時, その子は白でなければならない($\because$ 題意).

したがって, 頂点$x$の子を$y_1, ..., y_k$とすると,
この時の頂点$x$の通り数は, $\displaystyle{\prod_{i=1}^{k} g(y_i)}$となる.

一般化

この上で, 頂点$x$の色の指定がない$f(x)$は以下のように定義できる.
$f(x) = \displaystyle{ \prod_{i=1}^{k} f(y_i) + \prod_{1}^{k} g(y_i)}$

また, 頂点$x$が黒と指定されている$g(x)$は, 子が全て白と確定しているため, 以下のように定義できる.
$g(x) = \displaystyle{ \prod_{i=1}^{k} f(x_i) }$

$g(x)$を用いると, $f(x)はさらに短くでき, 一般化した式は以下のようになる.

• $f(x) = \displaystyle{ g(x) + \prod_{i=1}^{k} g(y_i)}$
• $g(x) = \displaystyle{ \prod_{i=1}^{k} f(x_i) }$

これを実装すればよい.

提出コード(C++) (opens new window)

お疲れ様でした.

参考資料

• ABC036 Editorial (opens new window)
• 漸化式を立てて「tree DP問題」を解く D - 塗り絵 (opens new window)