AtCoder Regular Contest 083 E - Bichrome Tree

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

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

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回同じカウントをする必要がある。

感想

うーん、500000000点!!!!

コード (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

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;}
}

Topcoder SRM 719 Div1 Easy - LongMansionDiv1

問題概要

N行無限列の2次元グリッドがある。各行にはコストが設定されており、その行のマスに1回乗るたびに毎回そのコストがかかる。移動の開始点と終了点が与えられるので最小のコストを求めよ。

N <= 50

解法

開始行→経由行→終了列→終了行という感じで移動することを考えて、経由行を全探索する。O(N).

感想

まじでこれ以上書くことがない

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

class LongMansionDiv1 {
public:
    ll minimalTime(vector<int> t, int sX, int sY, int eX, int eY) {
        int N = t.size();
        ll ans = 1LL << 59;
        
        for (int x = 0; x < N; ++x) {
            ll tmp = (ll)abs(eY - sY) * t[x];
            for (int i = min(x, sX); i <= max(x, sX); ++i) tmp += t[i];
            for (int i = min(x, eX); i <= max(x, eX); ++i) tmp += t[i];
            tmp -= t[x];
            ans = min(ans, tmp);
        }

        return ans;
    }
};

Topcoder SRM 720 Div1 Medium - DistinctGrid

問題概要

与えられる整数n, kに対して、各行・各列をみたとき異なる数がちょうどk個存在するようなn * nのグリッドを構成せよ。解が複数ある場合は使われる数の種類が最大になるものを答えること。

3 <= n <= 50

1 <= k <= n/2

解法

 1  2  3  0  0  0
 0  4  5  6  0  0
 0  0  7  8  9  0
 0  0  0 10 11 12
15  0  0  0 13 14
17 18  0  0  0 16

証明についてはこどふぉに貼ってあったpdfが参考になった(一番下の問題)。要するに↑の形より一個でも多くの違う数を入れようとすると矛盾が起きるので背理法でokということになるらしい。

感想

これでいいの?と思って投げたら通ってこれでいいの?ってなった

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

class DistinctGrid {
public:
    vector<int> findGrid(int n, int k) {
        vector<int> ans = vector<int>(n * n, 0);
        int num = 1;
        REP(i, n) REP(j, k-1) {
            ans[i * n + (i+j) % n] = num++;
        }
        return ans;
    }
};

Topcoder SRM 720 Div1 Easy - SumProduct

問題概要

0~9の各数字について、それぞれを何回まで使ってよいかを示した配列amountが与えられる。amountの制限を守って桁数がblank1の非負整数A, blank2の非負整数Bをつくるとき、ありえるA, Bのすべての組合せにおけるA*Bの総和を求めよ。

max(amount) <= 100

blank1, blank2 <= 100

解法

Aのi桁目に使う数字aとBのj桁目に使う数字bを固定する。このケースにおけるA*Bの総和は

(10i * a) * (10j * b) * (他の数字の並べ方)

となる。他の数字の並べ方とはつまり固定した2桁以外にどう数字を配置するかということで、これはDPで求めることができる。

dp(i, j) = 0~iまでの数字を使ったときの、j桁の数の作り方の総数

遷移は既に構成してる数字の並びに対して数iを差し込んでいくというイメージで考えるとコンビネーションを使ってできる (ei1333さんのブログがわかりやすかったです)。

感想

easyとは何か?

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

const ll MOD = 1000000007;
const ll MAX = 201;
ll comb[MAX][MAX];
ll dp[10][MAX];

ll powmod(ll a, ll x, ll m) {
    ll ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

class SumProduct {
public:
    int findSum(vector<int> amount, int blank1, int blank2) {
        ll ans = 0;

        comb[0][0] = 1;
        comb[1][0] = 1;
        comb[1][1] = 1;
        REP2(i, 2, MAX) REP(j, MAX) {
            comb[i][j] = (j == 0 || j == i) ? 1 : (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
        
        
        REP(a, 10) REP(b, 10) {
            amount[a] -= 1;
            amount[b] -= 1;
            if (amount[a] < 0 || amount[b] < 0) {
                amount[a] += 1;
                amount[b] += 1;
                continue;
            }

            memset(dp, 0, sizeof(dp));
            REP(j, MAX) dp[0][j] = j <= amount[0] ? 1 : 0;
            REP2(i, 1, 10) REP(j, MAX) REP(k, amount[i] + 1) {
                if (j - k < 0) continue;
                (dp[i][j] += dp[i-1][j - k] * comb[j][k] % MOD) %= MOD;
            }


            REP(i, blank1) REP(j, blank2) {
                ll tmp = 1;
                tmp = tmp * a * powmod(10, i, MOD) % MOD;
                tmp = tmp * b * powmod(10, j, MOD) % MOD;
                tmp = tmp * dp[9][blank1 + blank2 - 2] % MOD;
                ans = (ans + tmp) % MOD;
            }
            
            amount[a] += 1;
            amount[b] += 1;
        }

        return (int)ans;
    }

};