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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #397 ABCDE

Codeforces 全方位木DP

A. Neverending competitions

問題概要

最初は空港 SSS にいる。空港XXXから空港YYYに移動したという情報が n 個あたえられる。この情報は時系列順に並んでいるわけではないが、あり得ない移動はしていないことが保証されている。n回の移動後、空港 SSS にいるかどうかを判定せよ。

解法

最終的に空港SSSにいるとしたら、SSSから出た回数分だけ戻っていないとおかしい。よって空港SSSから出た回数と戻った回数が等しいかどうかを見ればいい。


B. Code obfuscation

問題概要

Kostyaはプログラムを書くとき、a,b,c,...,zの順で変数に命名をする。Kostyaが書いたプログラムから変数名だけ抜き出した文字列が与えられるので、Kostyaが書いたプログラムである可能性があるかを判定せよ。

解法

a,b,c,... の順になっているかを判定するだけで良い。


C. Table Tennis Game 2

X君が取るセット数をA、Y君が取るセット数をBとする。このとき

\[ AK \le a \le AK+B(K - 1) \]\[ BK \le b \le BK+A(K - 1) \]

が成立する。X君はA回セットを取っているのでAK点とるのは確定で、B個のセットでは0..K-1の点の自由に取れる、ということを考えるとこの式が出てくる。

この式を見れば \(A \le \lfloor a/K \rfloor\), \(B \le \lfloor b/K \rfloor\) が分かるが、よく考えるとイコールにするのが最適である。もし\(A = \lfloor a/K \rfloor\), \(B = \lfloor b/K \rfloor\) として条件を満たさないのであれば -1 を返せばいい。


D. Artsem and Saunders

\(g(h(x))=x\) なので、\(h\) は単射でないとおかしい。

\(h\)が単射であることを踏まえると、\(f(x)=f(y)\) のとき \(g(x)=g(y)\) が言えて、この条件を満たす \(g\) を決定するのは簡単である。

\(g\) は一般には一意に定まらないが、それらは\([m]\)の元のラベルの付け方の差異でしかないので実質一意に定まる。

よって構成した \(g\) が \(g(h(x))=x\) を満たすならそれが解で、満たさないなら他に候補がないので解が存在しないことがわかる。


E. Tree Folding

最後の一手で選んだのが u だとする。このとき木はどのような形になっているのかというと、

  • 単なるパス
  • Yみたいな形

のどちらかである。Y 型の真ん中の点 u を全探索しよう。

Y型に変形するには、まず u の子すべてをパスに変える必要がある。v を根とする部分木をパスに変えることのできる条件は、vから葉への距離が一定であることである。

v からの距離が一定であるかどうかは min と max を DP で計算すれば分かる。u を全探索するので N 回 DFS するかのかと思うかもしれないが、よく考えると 2 回の DFS で計算できる。N回DFSせずにDP値を計算するテクを全方位木DPと呼ぶ(のだと自分は思っている)。思考停止系のテクニック。筋肉。

あと気をつけたいのが、パスにまで変形したら終わりではなくて、パス長が偶数なら折りたためることに注意。