2017-10-27

Topcoder SRM 715 Div.1 Easy - MaximumRange

Topcoder SRM SRM #715 問題記録

問題概要

初期値0の変数Xがある。+1と-1が並んだ命令列が与えられ、前から順番にその命令をXに適用するか無視するかを自由に選択できる。この過程において作れるXの最大値と最小値の差の最大値を求めよ。

解法

+と-の数を数えて大きい方を取る

感想

問題概要の方が長い

コード (C++)

#include <bits/stdc++.h>
using namespace std;

class MaximumRange {
    public:
    int findMax(string s) {
        int p = 0;
        int m = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '+') p++;
            else m++;
        }
        return max(p, m);
    }
};

2017-10-27

天下一プログラマーコンテスト2016予選A C - 山田山本問題

問題記録 AtCoder 天下一プログラマーコンテストトポロジカルソート

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_c

問題概要

英小文字のみからなる2つの文字列のペア(Ai, Bi)がN個与えられる。ここで26個のアルファベットの順番を並べ替え、AiがBiより辞書順で小さくなるようにしたい。そのような並べ替えが存在するか判定し、存在する場合はそのうち元々の辞書順で最小のものを求めよ。

解法

英小文字26文字を頂点とし、「文字αが文字βより先でなければならない」という関係が成り立つときα -> βに辺を張る。このグラフにサイクルがなければ解が存在し、サイクルがあれば解が存在しない。サイクルが存在するということは「この文字より先じゃないと駄目」という関係をたどっていくと「自分自身より先じゃないと駄目」という矛盾した結論になる頂点が存在するということになるからである。

解が存在する場合、グラフのトポロジカルソートのうち辞書順最小が出力すべき解となる。普通のトポロジカルソートは 1.入ってくる辺がない頂点を選ぶ 2.その頂点を解の末尾に追加する 3.その頂点から出ている辺をすべて削除するの繰り返しで求めることができる。これを少し改変し、入ってくる辺がない頂点を選ぶパートで、選んだ頂点を優先度付きキューに溜めておき、辞書順で小さいものから取り出すようにすると最終的なトポロジカルソートも辞書順最小になる。（なおこの操作の結果すべての辺を削除することができなければトポロジカルソートは存在せず、解なしということになる）。

コーナーケースとして、AiかBiのどちらかがどちらかの接頭辞になっている場合がある。サンプルにもある通りBがAの接頭辞の場合どう順序を変えてもAを前にはできないので、解なしになる。逆にAがBの接頭辞の場合絶対に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 N = readln.chomp.to!int;
    auto edges = new bool[][](26, 26);
 
    foreach (i; 0..N) {
        auto s = readln.split;
        auto A = s[0];
        auto B = s[1];
        bool found = false;
        
        foreach (j; 0..min(A.length, B.length)) {
            if (A[j] != B[j]) {
                edges[B[j]-'a'][A[j]-'a'] = true;
                found = true;
                break;
            }
        }
 
        if (!found && B.length < A.length) {
            writeln(-1);
            return;
        }
    }
 
 
    auto q = new BinaryHeap!(Array!int, "a > b")();
    int[] toposo;
    foreach (i; 0..26) if (edges[i].sum == 0) q.insert(i);
 
    while (!q.empty) {
        int n = q.front;
        q.removeFront;
        toposo ~= n;
        foreach (m; 0..26) {
            if (edges[m][n]) {
                edges[m][n] = false;
                if (edges[m].sum == 0) q.insert(m);
            }
        }
    }
 
    
    if (26.iota.map!(i => edges[i].any).any) {
        writeln(-1);
    } else {
        char[] ans;
        foreach (c; toposo) ans ~= c.to!char + 'a';
        foreach (i; 0..26.to!char) if (ans.map!(a => a != i + 'a').all) ans ~= i + 'a';
        ans.writeln;
    }
}

2017-10-26

CODE FESTIVAL 2017 qual A D - Four Coloring

AtCoder CODE FESTIVAL 問題記録構築ゲー

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d

問題概要

H行W列のグリッドを4色で塗り分ける。このときマンハッタン距離がちょうどdのグリッド同士は別の色で塗らなければならない。条件を満たす塗り方をひとつ示せ。

H, W <= 500

解法

(x, y) -> (x+y, x-y)の変換で45度回転させた座標系において(D-1)×(D-1)の正方形を等間隔に敷き詰め、各正方形内のグリッドは隣接する上下左右斜め8つの正方形と異なる色になるように同じ色で塗る。これは以下のように塗ればできる。

最後に回転を戻せば答え。

なぜこれでよいかというと、(x, y) -> (x+y, x-y)の変換で、前者におけるマンハッタン距離が後者におけるチェビシェフ距離と等しくなるため。つまり後者において(D-1)×(D-1)の正方形を同じ色で塗るのは、どの2点を取っても必ずチェビシェフ距離がD未満になるように塗るということに相当する。このようにするとチェビシェフ距離がちょうどDになるようなグリッドが上下左右斜め8近傍の正方形に含まれることになるので、そこを塗り分ければよい、ということになる。

感想

本番で解けなかったんですが、この問題の最大の罠は「なんかいけそうだけど実は正しくないアドホック解法」が無限に湧いてくるところでした。そういう沼から抜け出すにはどうしたらいいんだろうな～

コード (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 H = s[0];
    auto W = s[1];
    auto D = s[2];
     
    auto N = max(H, W) * 3;
    auto B = new int[][](N, N);
    int[] colors = [1, 2, 3, 4];
     
    for (int i = 0; i * D < N; ++i)
        for (int j = 0; j * D < N; ++j)
            for (int a = 0; a < D; a++)
                for (int b = 0; b < D; b++)
                    if (i * D + a < N && j * D + b < N)
                        B[i*D+a][j*D+b] = colors[i%2*2+j%2];
     
        
    auto ans = new int[][](H, W);
    auto color = " RYGB";
        
    foreach (i; 0..H) {
        foreach (j; 0..W) {
            int ni = i + j;
            int nj = i - j + W;
            ans[i][j] = B[ni][nj];
        }
    }
     
    ans.each!(an => an.map!(a => color[a]).writeln);
}

2017-10-26

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

2017-10-25

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×10⁵, K <= 10⁹

解法

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

先頭の装置がAの場合、先頭の装置がBに変わるだけ (AABBBAB -> BABBBAB)
先頭の装置が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;
}

2017-10-24

Topcoder SRM 722 Div.1 Easy - TCPhoneHome

Topcoder SRM SRM #722 問題記録

問題概要

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

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

解法

基本的には特別な接頭辞がつく番号の数を数え、それを10^Nから引けばよい。ただしこのままだと重複が出るので、それは数えないようにする必要がある。具体的にはある接頭辞が別の接頭辞の接頭辞になっている場合、重複が起きる。例えば'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

2017-10-23

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