ASC47 問題・解法

2014-2015 Winter Petrozavodsk Camp, Andrew Stankevich Contest 47 (ASC 47)
Solutions

サイト
http://codeforces.com/gym/100608
問題文
http://codeforces.com/gym/100608/attachments/download/3181/20142015-winter-petrozavodsk-camp-andrew-stankevich-contest-47-asc-47-en.pdf
4人で4時間くらい参加。この記事は終了後に他人のコード見て思ったことがほとんど。

B,G,JがDPの良い問題だと思う。

A. Ambitious Plan

問題

二次元平面上にドローンがn体、砦がm城、塔がt基ある。
ドローンD、砦F, 2つの塔T1, T2について線分(D, F)と線分(T1, T2)が交差するような集合 { D, F, T1, T2 } が幾つあるか求めよ。
ただし、全てのドローンのy座標は正で、全ての砦および塔のy座標は負であることが保証されている。
どの3点も同一直線上にないことが保証されている。

n <= 1500
m <= 1500
t <= 1500

解法

各砦について独立に数え上げる。
砦一つを中心としてドローン達と塔達を角度で平面走査する。
交点の個数をセグメントツリーで管理する。詳しくは理解していない。

B. Borderless Words

問題

あるab文字列Sについて、任意のi (1 <= i < |S|) について長さiの接頭辞と長さiの接尾辞が異なるならばSをBorderlessと呼ぶ。
2つの整数n, kが与えられるので長さnのab文字列の中で辞書順k番目のBorderlessな物を求めよ。

n <= 64
k <= #{ 長さnのBorderlessなab文字列 }

解法

辞書順最小は貪欲。
先頭から一文字づつ決め打ちした時に、Borderlessがk個以下かどうか判定していく。
例えば
f("aab??"):=Borderlessになるような'?'の埋め方の場合の数
という問題になる。

この問題をDPで解く。
dp[i+1] := S[0..i]がBorderlessになるような'?'の埋め方の組合せ数
とすると、

dp[i+1] = 2^(S[0..i]の'?'の個数)
    - (S[0..0] と S[i..i] が同じBorderless文字列の組合せ)
    - (S[0..1] と S[i-1..i] が同じBorderless文字列の組合せ)
    - (S[0..2] と S[i-2..i] が同じBorderless文字列の組合せ)
    ...
    - (S[0..(i+1)/2] と S[i-(i+1)/2..i] が同じBorderless文字列の組合せ)

(S[0..j] と S[i-j..i] が同じBorderless文字列の組合せ)
は dp[j+1]*(2^(S[j+1..i-j-1]の'?'の個数)) で求められる。

C. Catalan Combinatorial Objects

問題

Combinatorial Objectというデータ構造及びその集合の記法を定義している。
例

L(P(L(P(L(L(B)),B)),P(B,L(P(P(B,B),P(B,B))))))

整数kが与えられるので、Combinatorial Object集合を一行で出力せよ。
ただし、その集合は重さが(0,1,2,3,4,5)のデータ構造はそれぞれ(1,1,2,5,14,k)通りあるものでなければならない。

120 <= k <= 140

解法

不明
埋め込み

D. Decomposable Single Word Languages

問題

アルファベット26文字のための決定性オートマトン(DFA)について考える。
1単語wだけを認識するDFAは、wの長さをnとするとその最小の状態数はn+2 (初期状態+各文字を読んだ状態+デッドエンド) である。
f:id:natsugiri:20150406201018p:plain
以下の条件を満たす2つのDFA X, Yを出力せよ。

  1. Xの状態数はn+1以下
  2. Yの状態数はn+1以下
  3. (Xの認識する文字列の集合)と(Yの認識する文字列の集合)の共通部分はちょうどwのみ

ただしそのようなX, Yが存在しないならそれを指摘せよ。

解法

どこか1文字の直後に*を入れるとwを認識しつつ、状態数が1減る。
なぜならその文字を読んだかどうかの状態が不要になるから。当然w以外の文字列も認識する。
例えば

aabc : 状態数6
aabc* : 状態数5
aab*c : 状態数5
aa*bc : 状態数5
a*abc : aa*bcに直さないとDFAにならない
a*bc : 状態数4

aa*bcとa*bcの積集合はw以外にも存在するのでこの2つは選ばないように、違う文字の最後に*を入れたDFAを2つ選べば良い。
wが全て同じ文字であった場合はX, Yは存在しない。

E. Elegant Square

問題

以下の条件を満たすn x nの魔方陣に似たものを出力せよ。

  1. 全ての数は互いに異なる正の数
  2. 全ての数はsquare free
  3. どの行・列についてもそれらの積は等しい
  4. 全ての数は1e18以下

3 <= n <= 30

解法

ある素数pがどの行・列についても一つになるように配置する(つまり1~nの順列)と良さそう。
n奇数の場合は

1 2 3 5 7      1 11 13 17 19
7 1 2 3 5     11 13 17 19  1
5 7 1 2 3  X  13 17 19  1 11
3 5 7 1 2     17 19  1 11 13
2 3 5 7 1     19  1 11 13 17

のように右下がり斜めと右上がり斜めを重ねれば良い

偶数の場合はもう少し不規則な物にする必要がある。n x n の正方形を3, 4つ掛けても良い。

F. Four Colors

問題

Interactive.
木がある。コンテスタントとジャッジが交互に木の頂点に色を塗っていくゲームを行う。

  1. 初めはどの頂点も色が塗られていない
  2. 色は4色
  3. プレイヤーは自分のターンに色の塗られていない頂点1つとその頂点に塗りたい色1つを指定する、ただし同じ色が隣り合うようなものは指定できない
  4. 色を塗ることができる頂点がなくなったらゲーム終了
  5. 全ての頂点に色が塗られていたらコンテスタントの勝ち、さもなければ負け
  6. コンテスタントが先行

木の頂点数<=1000

解法

4色もあるのでどうとでもなる。
(隣接する頂点に塗られている色の種類が多い順, 次数が高い順)、の辞書順で勝てる。

G. Greater Number Wins

問題

0~b-1の出るb面ダイスがある。
アリッサとベンが2種類のゲームを行う。
どちらのゲームも二人はそれぞれd桁のセルを持っている。
サイコロを振って出た目を見た後、空いているセルにその数を書く。これをmoveと呼ぶ。
二人とも全てのセルが埋まったとき、大きい数になっている人が勝ち。

1つ目のゲームは

  1. 二人は交互に1回moveを行う
  2. アリッサが先行

2つ目のゲームは

  1. まずアリッサがd回moveを行う
  2. 続いてベンがd回moveを行う

それぞれのゲームで互いに勝率を最大にする行動をとったとき、アリッサの勝率を両方答えよ。

d <= 10
b <= 10
(b+1)^d <= 3000

解法

(b+1)^d が1人のプレイヤーの状態数そのものなので、DPで解く。

H. Higher Math Lesson

問題

行列の対角化

解法

不明
線形代数

I. Isomorphism

問題

n頂点のグラフGについて
V(u, i)を頂点uからの距離がiのである頂点集合とする。
D(u, i)をbag{ deg(x) | x in V(u, i) } とする。bagは多重集合の意味、deg(x)はxの次数。
D(u)をリスト[ D(u, 0), D(u, 1) , ... , D(u, n-1) ] とする。これをuのdegree profileと呼ぶ。
Gの全ての頂点についてのdegree profileの多重集合をGのdegree profileと呼ぶ。

整数nが与えられるので、次の条件を満たす2つのグラフG, Hを出力せよ。

  1. G, Hの頂点数はどちらもn
  2. G, Hは多重辺、自己ループのない単純グラフ
  3. G, Hは同型ではない
  4. Gのどの頂点も互いに頂点のdegree profileが異なる
  5. Hのどの頂点も互いに頂点のdegree profileが異なる
  6. G, Hのdegree profileは等しい

ただしそのようなG, Hが存在しないならばそれを指摘せよ。

この2つのグラフはdegree profileが互いに等しく、同型でない。
しかし、各頂点についてdegree profile が異なるという条件を満たさない。
f:id:natsugiri:20150406201056p:plain

3 <= n <= 100

解法

不明
頂点数6のヒントになりそうなものが問題文中にあるが、頂点のdegree profileが異なると言う条件を満たさない。実は頂点数が6以下の時はG, Hは存在しないらしい。
頂点7の場合を何とか捻出し、それにパスを取り付けて頂点数を調節する解法が出されていたのを確認した。

J. Jinxiety of a Polyomino

問題

凸なポリオミノが与えられる。
ただし凸とは、ポリオミノを形作る水平・垂直な線分が途切れて分かれていないこと。
ポリオミノの2つのセルa, bについて、aからbへ移動するのに少なくとも必要な向きを変える回数をturn(a, b)とする。
全てのセルの組合せa, bについてturn(a, b)の最大値をJinxietyと呼ぶ。
Jinxietyを求めよ。
f:id:natsugiri:20150406201210p:plain

サイズ h*w
h, w <= 2000

解法

DP
凸の条件は言い換えると任意のセルからセルへの移動は右・下とか右・上とかの2方向を切り替えながら進めばよいということ。
左と上だけを使う場合をDPで求める。また上下反転したのち同様に求める。

left[y] := y行目の一番左にあるポリオミノのセルのx座標
up[x] := x列目の一番上にあるポリオミノのセルのy座標

dp[y][x] := セル(x, y)から左と上だけで行ける範囲のセルで、
    向きを変える回数の最小値の最大値

dp[y][x] =
    0 if (x, y)がポリオミノの外
    0 if [0..x-1]*[0..y-1]が全てポリオミノの外
    dp[up[x]][left[y]] + 1  otherwise

上下反転させた場合も含めて、dpテーブルの最大値がJinxiety。