# Gori#016(ABC036)

問題

# B - 回転

# 概要

N×NN \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;
}       

提出

# C - 座圧

# 概要

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

# 解法

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

# D - 塗り絵

# 概要

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

# 解法

Editorialに沿って解く.

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

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

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

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

# 頂点xxが白の時

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

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

# 頂点xxが黒の時

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

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

# 一般化

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

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

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

  • f(x)=g(x)+i=1kg(yi)f(x) = \displaystyle{ g(x) + \prod_{i=1}^{k} g(y_i)}
  • g(x)=i=1kf(xi)g(x) = \displaystyle{ \prod_{i=1}^{k} f(x_i) }

これを実装すればよい.

提出コード(C++)

お疲れ様でした.

# 参考資料

Last Updated: 2019-3-18 23:45:49