CodeChef Cook100 Editorial

CodeChef Cook100で解いた問題の解説です(div2の4問目、div1の3問目まで)。

Truth and Dare

Contest Page | CodeChef

概要

集合T_r, D_r, T_s, D_sが与えられる。 T_s \subseteq T_r かつ D_s \subseteq D_r のとき "yes"と、そうでないとき"no"と答えよ。

解法

set<int> で集合を管理して愚直に部分集合になっているか調べる。 制約が小さいのでvectorでも十分。

ソースコード: Solution: 24027534 | CodeChef

英語がとても読みづらい(というか未だに詳細を理解していない)。


Beautiful Garland

Contest Page | CodeChef

概要

R,Gの2種類からなる文字列s ( 2 \leq |s| \leq 10^5) が与えられる。 このsは先頭と最後がつながった一つの輪と考える。 この輪に対して以下の操作が高々1回できる。

  • 輪を2つの文字列s1, s2に分解する。 そしてs2を前後反転させてから再度s1とつなぐ。

この輪をRとGが交互に現れるようにできるか。

解法

まずRとGの数が同じでないとどうやっても交互にはできない。

次にRとGの数が同じときを考える。 この操作は同じ箇所に対して2回行うともとに戻ることがわかる。 そのためこの操作でsをRとGが交互になるようにできたならば、sはRとGが交互になっている文字列から操作を1回だけして作ることができる。逆も同じ。

そのため、 sをR, Gが交互になっている文字列から操作を1回だけして作ることができるか分かれば良い。

両端が同じ文字の位置で反転させると変化しない。そうでないなら部分文字列"RR", "GG"がちょうど一回ずつ現れる形になる。

以上からsの中のR,Gの数が同じであり、かつsがすでにRとGが交互になっている or 部分文字列"RR", "GG"がちょうど一回ずつ現れるときに"yes"、そうでないなら"no"である。

ソースコード: Solution: 24027634 | CodeChef


A-B Game

Contest Page | CodeChef

概要

A, Bの二人でゲームをする。このゲームは長さN \leq 10^5の一直線上に並んだマスの上で行われる。 各マスにはAのコマかBのコマが置かれているか何も置かれていないかのいずれかである。 プレイヤーAはAのコマを、プレイヤーBはBのコマを動かすことができる。動かすことができるのは駒があるマスから移動する先のマス までに何もないときに限る。つまり、すでに置かれているコマを飛び越すことはできない。

またコマごとに動かすことができる方向が事前に決まっており、マスの左端から順番に右方向、左方向、右方向、・・・である。 これはゲームの間変わることはない。

マスの初期状態が文字列sとして与えられ、ゲームはAの手番から始まる。このときAが勝つかBが勝つか答えよ。

 解法

大体のゲーム問題はNimに帰着できるのでNimにならないか考える。

まずコマを動かすことができる方向が右・左と交互になり、またコマを飛び越えて動かすことはできないので、 コマを左から2個ずつのペアにするとそれぞれ個別の独立したゲームが複数あるとみなすことができる (ただし奇数個あるときは別に考える必要がある)。

例えばs="A..B.A....B.BB"のときは次の3つの独立したゲームとみなせる:A..B, A...B, BB

ここで1つのペアに着目する。ペアにある空きマスの個数をLとする。 個別のゲームには次の2種類のパターンがある。

  • 両端が同じ文字のとき: これはNimではコマを動かすことができるプレイヤーだけが自由に取り除くことができる石の山とみなせる。石の個数はLである。
  • 両端が違うとき: どちらのプレイヤーも自分のコマを動かすことで任意の L' \lt Lについて空きマスがL'個である状態に持っていける。これはNimでは石の数がL個ある山と同じ性質をもち、Nimとみなせる。

これらからこのゲーム全体は次のようなゲームに言い換えられる:

プレイヤーA,Bのどちらも自由に取ることができる石山(普通のNim)、プレイヤーAだけが石を取り除ける山、プレイヤーBだけが石を取り除ける山の3種類があるNimの亜種

このゲームの戦略としては、普通のNimでゲームを行い、何もできない状態になったら 自分専用の山から石を1つずつ取り除くのが最善である。

普通のNimの石山はAが勝つならばA専用の1つの石、Bが勝つならば無とみなせるので、 A,B専用の石の山の数の大小のみでゲームの勝敗を決められる。

最後にコマの数が奇数のときは右端のコマ専用の石の山とみなせばよい(この処理をしていなくて1WA)。

ソースコード: Solution: 24042766 | CodeChef


Tree Unattractiveness

Contest Page | CodeChef

概要

N \leq 100 頂点からなる木Tと\{0,1,2\}のうちいずれかの数字が書かれたN 個のマーカーがある。 これらのマーカーを各頂点にちょうど一つずつ置いていく。 頂点vに置かれたマーカーの数字をn_vとする。

このときあるマーカーの置き方に対してそのスコアは \max\{|n_u - n_v| \mid 頂点u, vは木T 上で隣接している\} で定められる。 マーカーを適当においたときに得られるスコアの最小値を求めよ。

解答

ありうるスコアは0,1,2のいずれかであり、0かどうかはすぐ分かる (すべてのマーカーか同じときに限る)。 そのため1が作れるかどうかを判定すればいい。

スコアが1になるように置くためには、マーカー0と隣接するのは0か1、マーカー2と隣接するのは2か1でなければならない。また1は何と隣接しても良い。

このことから、木に置いた1のマーカーがある頂点で木を分断すると、分断されたあとの各連結成分に置かれるマーカーはすべて0か2になっていなければならない。

この性質から根を適当に決めて木dpができる。 パラメータは今の頂点に何を置いたか、部分木で0,1を使った個数となる (2を何個使ったかは部分木のサイズから計算できる)。 ただし愚直に"dp[頂点][置いたマーカー][0の数][1の数]=スコア1が作れる/作れない"というtrue/false としてしまうと計算量的に間に合わない。

ここから次元を減らすことを考える。上で説明したように1は何と隣接しても良いためできるだけ使わないほうが良いと 直観的に分かる。 そこでdp[頂点][置いたマーカー][0の数]="スコア1にするために必要な1のマーカーの個数の最小値"としても正しく計算できる。

このとき遷移は頂点vの子をc_1, c_2, \ldots, c_nとしたとき

  • 
dp[v][1][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots +  dp[c _ n][m' _ n][z _ n] + 1

    ただし、1 \leq k \leq nに対して 
m' _ k \in \{0,1,2\}, z _ 1 + \cdots + z _ n = z

  • 
dp[v][0][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots +  dp[c _ n][m' _ n][z _ n]

    ただし、1 \leq k \leq nに対して 
m' _ k \in \{0,1\}, z _ 1 + \cdots + z _ n + 1 = z

  • 
dp[v][2][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots +  dp[c _ n][m' _ n][z _ n]

    ただし、1 \leq k \leq nに対して 
m' _ k \in \{1,2\}, z _ 1 + \cdots + z _ n = z

このdpの計算量は一見O(N ^ 4)に見えるが、二乗の木dpの形なので(参考リンク: https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594) O(N ^ 3)になる。

ソースコード: Solution: 24095010 | CodeChef