AtCoder Grand Contest 014 D - Black and White Tree

問題記録 AtCoder AGC AGC #014

http://agc014.contest.atcoder.jp/tasks/agc014_d

問題概要

N頂点の木に対し以下のような2人ゲームを行う。各手番において未着色の頂点を必ずひとつ選び、先手ならば白、後手ならば黒で塗る。すべての頂点が塗られたあと、黒の頂点に隣接している白の頂点をすべて黒にする。ここで白の頂点がひとつでも残っていれば白の勝利となる。両方が最適に行動したときどちらが勝つか求めよ。

解法

先手は「隣接頂点をひとつしか持たない頂点A」＋「その頂点と隣接している頂点B」の2つを塗ることができれば勝ちである。逆に言うと、先手がBの頂点を選び続けると後手はそれに対応するAの頂点を選び続けることしかできない。これを踏まえるとこの問題は以下のように言い換えることができる。「隣接頂点をひとつしか持たない頂点」と「その頂点に隣接している頂点」の組を選び、グラフから取り除く。この操作の過程で孤立する頂点が現れたら先手の勝ち、孤立する頂点が現れずに全部の頂点を消しきれれば後手の勝ちとなる。これはDFSで葉の方から消していく処理で書くとO(N)でできる。

感想

公式解説の完全マッチングを使った説明の方が断然わかりやすいので見てください

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto N = readln.chomp.to!int;
    auto edges = new int[][](N);
    foreach (i; 0..N-1) {
        auto s = readln.split.map!(to!int);
        edges[s[0]-1] ~= s[1]-1;
        edges[s[1]-1] ~= s[0]-1;
    }
 
    if (N == 2) {
        writeln("Second");
        return;
    } else if (N == 3) {
        writeln("First");
        return;
    }
 
    
    bool first = false;
    
    int dfs(int n, int p) {
        int[] tmp;
        foreach (m; edges[n]) if (m != p)
            tmp ~= dfs(m, n);
 
        if (tmp.sum > 1)
            first = true;
 
        //writeln(n, tmp);
        return tmp.sum ? 0 : 1;
    }
 
    
    if (dfs(0, -1))
        first = true;
    
    writeln( first ? "First" : "Second" );
}

AtCoder Grand Contest 011 D - Half Reflector

問題記録 AtCoder AGC AGC #011

http://agc011.contest.atcoder.jp/tasks/agc011_d

問題概要

左右からボールを入れられるN個の装置が横一直線に並んでいる。装置は状態Aか状態Bのどちらかである。状態Aの装置にボールが入ってくると、入ってきた方向にボールを跳ね返し状態Bに変化する。状態Bの装置にボールが入ってくるとそのまま逆側からボールを排出し状態Aに変化する。各装置の初期状態が与えられるので、一番左の装置の左側からボールを入れるという操作をK回繰り返した後の各装置の状態を求めよ。

N <= 2×105, K <= 109

解法

小さいNで実験してみると、ボールを一回入れるごとに以下のような規則的な変化をすることがわかる（わからない）。

  1. 先頭の装置がAの場合、先頭の装置がBに変わるだけ (AABBBAB -> BABBBAB)
  2. 先頭の装置がBの場合、全部の装置の状態が反転して左にひとつシフトした形になる。先頭のBは末尾に回ってAになる (BABBBAB -> BAAABAA)

後者のパターンで変化が起きるとき最後尾にくっつくのは必ずAになるので、十分に長いKをとると最終的にはBABABABABA...のような互い違いの形に収まる。この形になると、Nが偶数の場合必ずBが先頭に来るのでBABABAの形で一切変化が起こらなくなる。Nが奇数の場合はAが一度先頭に来るので ABABAB -> BBABAB -> ABABAB -> ,,, のように先頭のABだけが切り替わりつづける振動状態になる。

あとはこの規則をシミュレートしていけばいい。いま先頭がどこかと反転状態はどうかだけ持っておけばO(N)でできる。列を舐めきってもKが余っていたらあとは上の最終パターンにはまるのでNの偶奇によってよしなにやる。

解法は以上だが一応こうなる理屈を（公式解説を見て）考えてみる。変化が起きるのは先頭がBのときだけなので、このパターンだけを考える。先頭2つがBAのときボールが左から入ると、oBA -> AoA -> AoB -> BoB -> BAo という変化でボールは右へ出ていく。次に先頭2つがBBのときは oBB -> AoB -> AAo という変化でやはりボールは右へ出ていく。つまり右がAのときは一回ボールが跳ね返ってくるので左は元のBに戻り、右がBのときはボールが戻ってこないので左は一回反転したAのままになる（＝左の装置は右の装置の反対の状態になる）。右へ出ていく直前、右の装置は必ずBの状態を取っているので、以降のすべての隣接2要素においてもまったく同様の変化が発生する。つまりボールが2マス以上戻ってくることはなく、必ず右に送られていくことになる。そして最後に右から出ていくとき右の装置は必ずAになっているので、先頭のBがcyclicにシフトして最後尾のAになるとみなせる。この変化を言い換えると上でいう左シフトということになる。

感想

実験ゲーかと思いきや証明パートも確かにそうやなあという感じだった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];
    auto S = readln.chomp.map!(a => a == 'A').array;
    foreach (i; 0..N) S ~= [0, 1];
 
    int p = 0;
    bool flip = false;
 
    while (p < N && K > 0) {
        int c = S[p] ^ flip;
        if (c) { // 先頭がA
            K -= 1;
            S[p] ^= 1;
        } else {
            p += 1;
            flip ^= 1;
            K -= 1;
        }
    }
 
 
    auto ans = new int[](N);
 
    if (K == 0) {
        foreach (i; 0..N) ans[i] = S[p+i] ^ flip;
    } else if (N % 2 == 0) {
        foreach (i; 0..N) ans[i] = i % 2;
    } else {
        ans[0] = S[p] ^ flip ^ (K % 2);
        foreach (i; 1..N) ans[i] = 1 - i % 2;
    }
 
    ans.map!(a => a ? 'A' : 'B').writeln;
}

Topcoder SRM 722 Div.1 Easy - TCPhoneHome

Topcoder SRM SRM #722 問題記録

問題概要

あるシステムにおいて、電話番号の桁数はNである。またこのシステムでは特定の接頭辞がついた電話番号はすべて「特別な番号」として予約されている。Nと接頭辞の集合Sが与えられるので、特別でない番号が何通り存在するか求めよ。

1 <= N <= 17, 0 <= |S| <= 50

解法

基本的には特別な接頭辞がつく番号の数を数え、それを10Nから引けばよい。ただしこのままだと重複が出るので、それは数えないようにする必要がある。具体的にはある接頭辞が別の接頭辞の接頭辞になっている場合、重複が起きる。例えば'12'と'123'が接頭辞に含まれるとき、'12'で始まる番号の数を数えるとその中に'123'で始まる番号を含んでいることになる。逆に、これ以外のケースで重複数え上げは発生しえない。以上よりある接頭辞が別の接頭辞を接頭辞として含んでいる場合は数え上げの対象に含めない、ということをすればよい。O(|S|^2)

感想

easyとしてちょうどいい感じがあって良かった。コードのところにpythonを載せるの初めてかもしれない。基本的にはD言語でやってるんですが、定数倍が不安だとかDが使えない場所だとかではC++を, 実装軽くて計算量にも十分な余裕がある場合はPythonを気まぐれで使ったりしてます

コード (Python2)

class TCPhoneHome:
    def validNumbers(self, digits, specialPrefixes):
        specialPrefixes = list(specialPrefixes)
        specialPrefixes.sort(key=lambda x: len(x))
        noneed = []
        for i in xrange(len(specialPrefixes)):
            for j in xrange(i+1, len(specialPrefixes)):
                if specialPrefixes[j].startswith(specialPrefixes[i]):
                    noneed.append(j)
        noneed = reversed(sorted(set(noneed)))
        for n in noneed:
            specialPrefixes.pop(n)

        ans = 10 ** digits
        for s in specialPrefixes:
            ans -= 10 ** (digits - len(s))

        return ans

AtCoder Regular Contest 083 E - Bichrome Tree

問題記録 AtCoder ARC ARC #083 木DP

http://arc083.contest.atcoder.jp/tasks/arc083_c

問題概要

N頂点の根付き木とN要素の数列Xが与えられる。木の各頂点に白or黒の色と非負整数を割り当てるとき、頂点nを根とする部分木に含まれる頂点のうちnと同じ色のものに割り当てられた数の合計がX_nとなるような割り当てが可能かどうか判定せよ。

N <= 1000

X <= 5000

解法

dp(n): 頂点nを根とする部分木において、片方の色の合計をXnとしたときのもう片方の色の合計の最小値

このdpを葉の方から更新していく。ただし葉の場合は0を返すことにする。葉でない頂点nのdp(n)を計算する際には、nのすべての子mについて、Xmとdp(m)のどちらかをどちらかの色に塗る、の組み合わせ列挙を考えるとdp(n)を出すことができる。普通にやると2子の数の計算量がかかってしまうが、X<=5000を利用してナップサックDPをやると「片方の色の合計がxであるときのもう片方の色の合計の最小」をO(NX)で出すことができる。このときどうやってもどちらの色もXn以下にできないのであれば、nに非負整数を割り当てることはできず答えはIMPOSSIBLEとなる。

感想

説明が難しすぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
immutable int INF = 1 << 29;
 
bool solve() {
    auto N = readln.chomp.to!int;
    auto P = readln.split.map!(to!int).array;
    auto X = readln.split.map!(to!int).array;
    auto edges = new int[][](N);
    foreach (i; 0..N-1) {
        edges[i+1] ~= P[i]-1;
        edges[P[i]-1] ~= i+1;
    }
 
    int dfs(int n, int p) {
        auto dp = new int[][](2, X[n]+1);
        int cur = 0, tar = 1;
        dp[cur].fill(INF);
        dp[cur][0] = 0;
 
        foreach (m; edges[n]) {
            if (m == p) continue;
            dp[tar].fill(INF);
            int w = dfs(m, n);
            int b = X[m];
            foreach (i; 0..X[n]+1) {
                if (dp[cur][i] != INF) {
                    if (i + w <= X[n]) {
                        dp[tar][i+w] = min(dp[tar][i+w], dp[cur][i]+b);
                    }
                    if (i + b <= X[n]) {
                        dp[tar][i+b] = min(dp[tar][i+b], dp[cur][i]+w);
                    }
                }
            }
 
            cur ^= 1, tar ^= 1;
        }
 
        return dp[cur].reduce!min;
    }
 
    return dfs(0, -1) != INF;
}
 
void main() {
    writeln( solve ? "POSSIBLE" : "IMPOSSIBLE" );
}

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

AtCoder 回文 問題記録 CODE FESTIVAL

http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d

問題概要

英小文字のみからなる文字列Sをいくつかの箇所で区切り、空でない部分文字列に分割することを考える。このとき必ずすべての部分文字列が「並べ替えれば回文にできる」という条件を満たすように分割しなければならない。可能な分割の最小数を求めよ。

|S| <= 2×105

解法

（なんか無駄に複雑なことをしている気もするので他の人の解説も見てください）

ある文字列が「並べ替えれば回文にできる」とは「奇数回登場する文字が高々1つ」と同値である。これは直観的には両端から文字を埋めて回文を作っていくことを考えるとわかりやすい。もしすべての文字が偶数個であるなら同じ文字を2個ずつとって両端に詰めていけばよいし、ひとつだけ奇数個の文字があるならそのプロセスの最後に余った1個を真ん中に置けばよい。

以上より重要なのは各文字が現れた回数の偶奇であるとわかった。ここで各文字の偶奇に0/1を割り当てると、これを長さ26のビット列で表すことができる（一例としてaとzが奇数回登場していて他が偶数回の場合、これに対応するビット列は 10000000000000000000000001 のようになる）。この表現の元では、ある区間において「奇数回登場する文字が高々1つ」というのは「立っているビットが高々1つ」と言い換えることができる。

ここで上のようなビット列においてSの左端から累積xorを取った数列をAとする。ただしA[0]は空文字列として00000000000000000000000000を割り当てる。こうすると累積和と同じように (A[n] xor A[m-1]) でm文字目～n文字目までの各文字の偶奇を得ることができるようになる。つまり「Sの区間[i, j]が条件を満たす」ならば「(A[j] xor A[i-1]) の立っているビットが高々1つ」である。

準備が整ったので以下のようなDPを考える。

dp(n): 1～n文字目だけを考えて分割を行ったときの最小分割数

このdpを小さいnから更新していく。ここでdp(n)が確定したとき、「Sの区間[n+1, m]が条件を満たすようなすべてのm」について、dp(m)=dp(n)+1という更新をかけることができる（n文字目までがdp(n)個に分割できて、n+1文字目～m文字目が1個に分割できるため）。問題はmをどうやって得るかだが、ここで上の累積xorを使うとそのようなmは (A[m] xor A[n]) の立っているビットが高々1つ、つまりA[n]と同一かあるいはひとつだけビットを反転させたようなA[m]を持つようなmが条件を満たす。前計算でA[i]=bを逆引きしてbからiを列挙できるようにしておけば、mの取得は簡単である。以上でDPを最後まで更新していけばdp(|S|)が答えになる。

注意点として、上のようなDPの配り方を愚直にやると遷移の数が|S|^2になりうるのでそのままだとTLEする（たとえばaaaaaaaaaaaa...は全部が全部に遷移できる）。これを避けるためには、あるビット列に遷移しようとするとき、以前にもそのビット列に遷移していて、かつそのときのdp値が今より小さければその遷移はスキップするという枝刈りが必要。こうするとある特定のビット列への遷移は高々27回までしか行われないので、結局O(N)時間に収まる（たぶん）。

感想

「DPはDAGの最短経路」を地で行く考察ができた感があり、良かった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto X = new int[](N+1);
    int[][int] Y;
    X[0] = 0;
    Y[0] = [0];
    foreach (i; 0..N) {
        int c = S[i] - 'a';
        X[i+1] = X[i] ^ (1 << c);
        Y[X[i+1]] ~= i+1;
    }
 
 
    auto dp = new int[](N+1);
    dp.fill(1 << 29);
    dp[0] = 0;
    int[int] used;
 
    foreach (i; 0..N) {
        foreach (j; 0..26) {
            int next = X[i] ^ (1 << j);
            if (next in Y && (!(next in used) || used[next] > dp[i])) {
                used[next] = dp[i];
                foreach (m; Y[next]) {
                    dp[m] = min(dp[m], dp[i]+1);
                }
            }
        }
 
        if (X[i] in Y && (!(X[i] in used) || used[X[i]] > dp[i])) {
            used[X[i]] = dp[i];
            foreach (m; Y[X[i]]) {
                dp[m] = min(dp[m], dp[i]+1);
            }
        }
    }
 
    dp[N].writeln;
}

AtCoder Grand Contest 011 C - Squared Graph

問題記録 AtCoder AGC AGC #011

http://agc011.contest.atcoder.jp/tasks/agc011_c

問題概要

N頂点M辺の単純無向グラフGが与えられる。Gの各頂点は1～Nまでの番号が付いている。Gを元にして以下のようなグラフG'を作ったとき、G'の連結成分の数を求めよ。

  • 頂点数はN2
  • 各頂点は1以上N以下の2整数の組(a, b)で番号付けされる
  • 元のグラフGにおいてa-a'間, b-b'間にそれぞれ辺があるとき、G'の(a, b)-(a'-b')間に辺を張る

2 <= N <= 105

0 <= M <= 2*105

解法

G'の辺が張られる条件は、直観的には以下のように言い換えることができる（公式解説動画参照）。

  • 元のグラフGの2頂点a, bにコマを置く
  • 置いたコマを辺に沿って「同時に」動かす
  • この1回の操作の結果コマが頂点c, dに移れるとき、G'において(a, b) - (c, d)間に辺が張られる
  • この操作を繰り返して遷移できる頂点ペアはすべてG'において連結になる。

このように考えると、元のグラフでa-bが非連結であれば(a, *) - (b, *)に辺が張られることはありえないことがわかる。ゆえにまずはGを連結成分ごとに分解し、その単位で考えていくことにする。ここで分解した各連結成分を以下の3パターンに分類する。

  1. 孤立点
  2. 二部グラフ
  3. それ以外

まず孤立点については辺がないので上で書いたような操作をどうやっても行うことができない。ゆえに元のグラフで頂点aが孤立点である場合G'においても (a, *) と (*, a) は孤立点になる（＝頂点ひとつで連結成分ひとつをなす）。

次に二部グラフについて。上の操作において選ぶ2頂点がいずれも二部グラフの上にあったとすると、同じ連結成分上にあってもたどり着けない組合せというものが出てくる。二部グラフを赤と青に塗り分けたとしたら、上の操作によるコマの移動は (赤, 赤) -> (青, 青) -> (赤, 赤) -> ...という遷移と(赤, 青) -> (青, 赤) -> (赤, 青) -> ,,,という2パターンになり決して交わらないので、これらはG'において2つの連結成分を作り出すということになる。

逆にどちらかのコマさえ非二部グラフの上に乗っているのならば、連結成分内のすべての頂点の組合せに遷移することができる。よってこの組み合わせにおいてG'に作り出される連結成分は1つだけである。

以上より解法はまず元のグラフを連結成分ごとに分解し、それぞれの連結成分を上の3パターンに分類したうえで、各組合せによってできる連結成分の数を足し合わせる、ということになる。気を付ける点として、最初の2コマを置く頂点が同じ連結成分内にある場合とそうでない場合で数え方が若干違う。もし(a, b)が同じ連結成分内に属していない場合、aが右に行ったりbが左に行ったりすることはないので、どちらの連結成分を左に置くかというところで2回同じカウントをする必要がある。

感想

うーん、５００００００００点！！！！

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0].to!int;
    auto M = s[1];
    auto edges = new int[][](N);
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        edges[s[0]-1] ~= s[1]-1;
        edges[s[1]-1] ~= s[0]-1;
    }
 
 
    int[][] groups;
    bool[] used = new bool[](N);
    int[] color = new int[](N);
    color.fill(-1);
 
    void dfs1(int n, int g) {
        if (used[n]) return;
        used[n] = true;
        groups[g] ~= n;
        foreach (m; edges[n]) if (used[n]) dfs1(m, g);
    }
 
    bool dfs2(int n, int c) {
        if (color[n] != -1) return color[n] == c;
        color[n] = c;
        foreach (m; edges[n]) {
            if (!dfs2(m, c^1)) return false;
        }
        return true;
    }
 
 
    int gn = 0;
    bool[] is_bi;
    foreach (i; 0..N) if (!used[i]) {groups ~= (new int[](0)); dfs1(i, gn++);}
    foreach (g; 0..gn) is_bi ~= dfs2(groups[g][0], g);
 
    long ans = 0;
 
    long G = groups.length;
    long one = groups.map!(g => g.length == 1).sum;
    long bi = is_bi.sum - one;
    long other = G - one - bi;
 
    ans += one * 2 * N - one * one;
    ans += bi * 2 + other;
    ans += bi * (bi - 1) * 2;
    ans += other * (other - 1);
    ans += other * bi * 2;
 
    ans.writeln;
}

AtCoder Regular Contest 078 E - Awkward Response

問題記録 AtCoder ARC ARC #078 インタラクティブ

http://arc078.contest.atcoder.jp/tasks/arc078_c

問題概要

ある正整数Nが設定されている。64回以内の質問クエリでNを特定せよ。質問クエリで正整数nを投げると、「n <= N かつ str(n) <= str(N)」または「n > N かつ str(n) > str(N)」 のときYESが、そうでないときNOが返ってくる。

1 <= N <= 109

1 <= n <= 1018

解法

桁数を特定してから2分探索する。

まず桁数の特定は10, 100, 1000, ... を順に投げていくとできる。例えばN=152のとき100まではYESだが1000以降はNOが返る。一般的には初めてNOになるときのnを10xとすると、Nは 10x-1 < n < 10x ということがいえる。（ただしNが10xの形をしているときがコーナーケースで、この場合はいつまでもNOが返ってこない。この場合は次に2, 20, 200, ... という風に投げていけばNを特定できる）

桁数が特定できたらあとは二分探索を行う。ここで推測する数字をそのまま質問してもダメ（例えばN=123のとき、122も123も124も返答はYESになってしまう）で、工夫が必要になる。自分はnに109を掛けることにした。Nの桁は決まっているので、同じ桁のnに対して10xを掛ければ数字での比較は必ずn > Nになる。一方で文字列での比較は10xを掛ける前と変わらないので、Nを境に大小が切り替わる。これで2分探索ができる。

前半で高々9回、後半でだいたいlog_2(109) ≒ 30回の質問クエリになり、制約内に収まる。

感想

整理すると結構すっきりするけど最初もっとぐちゃぐちゃなやり方でやってしまった。D言語のdebug構文をうまく使えた感じがある

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
long N, cnt;
 
bool ask(long n) {
    writeln("? ", n);
    stdout.flush;
    cnt += 1;
    
    debug {
        string sn = n.to!string;
        string sN = N.to!string;
        return (n <= N && sn <= sN) || (n > N && sn > sN);
    } else {
        return readln.chomp == "Y";
    }
}
 
void main() {
    debug {N = readln.chomp.to!long;}
 
    long x = 10;
    for (; x <= 10^^9 && ask(x); x *= 10) {}
 
    if (x == 10L^^10) { // N = 1, 10, 100, ...
        x = 2;
        for (; x <= 2 * 10L^^9 && !ask(x); x *= 10) {}
        writeln("! ", x / 2);
    } else {
        long hi = x - 1;
        long lo = x / 10;
        while (hi - lo > 1) {
            long mid = (hi + lo) / 2;
            if (ask(mid * 10L^^9)) hi = mid;
            else lo = mid;
        }
        writeln("! ", hi);
    }
 
    debug {cnt.writeln;}
}