2017-11-08

Typical DP Contest M - 家

AtCoder TDPC 問題記録

http://tdpc.contest.atcoder.jp/tasks/tdpc_house

問題概要

H階建ての家があり、各階には部屋が1番～R番までのR個存在する。部屋間を以下のルールに従って移動するとき、H階の部屋1から1階の部屋1に移動する経路は何通りあるか。ルール1. h階の部屋rから(h-1)階の部屋rへ移動できる。ルール2. 同じ階の部屋間は、与えられる行列Gの対応要素が1であれば相互に移動可能。ルール3. 同じ部屋を2度通ることはできない。

H <= 10⁹

R <= 16

解法

横方向の移動の仕方をbitDPで計算した後、縦方向の移動の仕方を行列累乗で求める。

「その階で最初に部屋xにいて最後に部屋yにいたときの移動経路の総数」をすべてのx, y(1 <= x, y <= R)の組合せで求めると、これをR行R列の行列の形で表すことができる。すべての階で部屋の構造は同じなので、あとはH階分の行列累乗を行えばH階→1遷への遷移を求めることができる。

問題は「その階で最初に部屋xにいて最後に部屋yにいたときの移動経路の総数」をどう求めるかということであるが、これはbitDPで行うことができる。具体的には

dp(i, j, mask): 「その階で最初にいた部屋がiで、部屋集合maskをこれまでに通過し、最後にjにいる」ときの移動経路の総数

となる。遷移の際に経由する部屋を総当たりする必要があるのでこのdpの計算はO(R³×2^R)になる。行列累乗パートも考慮に入れると計算量はO(R³×2^R + R³×logH)となる。R=16だと若干怪しくなってくる計算量だが実はTDPCでこの問題だけTLが8secもあるので余裕を持って間に合う。

感想

最初2^R×R³の桁を一個見間違えて無駄に迷走してしまった……

コード (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 long MOD = 10^^9+7;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto R = s[1];
    auto G = R.iota.map!(_ => readln.split.map!(to!int).array).array;
 
    
    auto dp = new long[][][](R, R, 1 << R);
    foreach (i; 0..R) dp[i][i][1<<i] = 1;
    auto masks = (1<<R).iota.array.sort!((a, b) => a.popcnt < b.popcnt).array;
 
    foreach (i; 0..R) // 出発
        foreach (mask; masks)
            foreach (j; 0..R) // 経由
                foreach (k; 0..R) { // 到着
                    if (!(mask & (1 << i))) continue;
                    if (!(mask & (1 << j))) continue;
                    if ((mask & (1 << k))) continue;
                    if (!G[j][k]) continue;
                    (dp[i][k][mask|(1<<k)] += dp[i][j][mask]) %= MOD;
                }
 
    
    auto mat = new long[][](R, R);
    foreach (i; 0..R)
        foreach (j; 0..R)
            foreach (mask; 0..1<<R)
                (mat[i][j] += dp[i][j][mask]) %= MOD;
 
    matpow(R, H, mat)[0][0].writeln;
}
 
 
long[][] matmul(int N, long[][] m1, long[][] m2) {
    auto ret = new long[][](N, N);
    foreach (i; 0..N) {
        foreach (j; 0..N) {
            ret[i][j] = 0;
            foreach (k; 0..N) {
                (ret[i][j] += m1[i][k] * m2[k][j] % MOD) %= MOD;
            }
        }
    }
    return ret;
}
 
long[][] matpow(int N, long K, long[][] mat) {
    auto ret = new long[][](N, N);
    foreach (i; 0..N)
        foreach (j; 0..N)
            ret[i][j] = i == j ? 1 : 0;
    
    while (K > 0) {
        if (K % 2 == 1)
            ret = matmul(N, ret, mat);
        mat = matmul(N, mat, mat);
        K /= 2;
    }
 
    return ret;
}

2017-11-07

AtCoder Regular Contest 084 D - Small Multiple

AtCoder ARC ARC #084 問題記録

http://arc084.contest.atcoder.jp/tasks/arc084_b

問題概要

正整数Kのある正の倍数を10進法で表したときの各桁の和の最小値を求めよ。

2 <= K <= 10⁵

解法

以下のようなグラフを考え、最短経路問題を解く。

頂点は0～(K-1)のK個
頂点x → 頂点(x+1)%K にコスト1の辺が出る
頂点x → 頂点(x×10)%K にコスト0の辺が出る
コスト1を持って頂点1からスタートし、頂点0をゴールとする

K <= 10⁵ よりダイクストラで解いてもO(KlogK)で間に合う。

この最短経路問題で解いているのは「mod K が x であるすべての正整数の集合における各桁の和の最小値」である。つまり0～(K-1)の各頂点が「mod K で x である正整数の集合」を表し、頂点1から頂点xまでの最短距離が「各桁の和の最小値」を表す。イメージとしては、「1」という数字からスタートしてその数に＋1するか×10するかの遷移を繰り返している、という感じになる。頂点0が「modKが0であるすべての正整数の集合」、すなわちKの正の倍数ということになるので、頂点0までのコストが解となる。

感想

mod Kで0の集合 = Kの倍数の集合というの自明に見えるけど、なんか頭の中で結びついてなかったので認識しておきたいですね

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

const int INF = 1 << 29;

void main() {
    auto N = readln.chomp.to!int;

    auto dist = new int[](N);
    dist.fill(INF);

    auto pq = new BinaryHeap!(Array!(Tuple!(int, int)), "a[1] > b[1]");
    pq.insert(tuple(1, 1));

    while (!pq.empty) {
        auto n = pq.front[0];
        auto c = pq.front[1];
        pq.removeFront;
        if (dist[n] <= c) continue;
        dist[n] = c;
        if (dist[(n+1)%N] > c+1) pq.insert(tuple((n+1)%N, c+1));
        if (dist[(n*10)%N] > c) pq.insert(tuple((n*10)%N, c));
    }

    dist[0].writeln;
}

2017-11-04

DDCC2017本戦に参加しました

参加記

11/3に行われた「DISCO presents ディスカバリーチャンネルコードコンテスト2017」(DDCC2017)の本戦に参加しました。新卒枠100人＋それ以外100人という非常に大規模なオンサイトコンテストで、枠の大きさに助けられて本戦に行くことができました。社会人にとってここまで本戦チャンスが大きいオンサイトコンテストは他にないので本当にありがたい限りです。ありがとうございます。ありがとうございました。

コンテスト

A, Bで2完の75位という何ともいえない結果でした。始まってまず思ったのが、Aからむずない？ということで、最終的に角だけ見ればええやんというところにたどり着くまで結構時間がかかってしまい焦りました。Bはサンプル見てパッと出てくるGCD->LCMを書いて通したけど何でこれでいいのかはいまだによくわかってないです。C問題はあまりにもわからないのでサイクルの列挙方法についてググったり、窓の外のイトーヨーカドーを眺めたりしていました。電源が少ないということでバッテリーが不安だったんですが、1時間半その状態だったのでメチャクチャ余裕でした。

イベント

コンテスト終了後にもイベントがあり、Ponanzaの山本一成さん、プロ棋士の西尾明さん、司会としてAtCoderの高橋直大さん、の対談企画がありました。将棋やらないので普段聞く機会のないような新鮮な話を多く聞けて楽しかったですが、やはり個人的に一番興味深かったのは既にレーティング1000くらいの実力はあるという競プロAIの話でした。あと社内見学ということで、自分は初参加なのでAコースに参加して機械とかいろいろ見せてもらいました。結構な時間が福利厚生施設の紹介に当てられており温かい気持ちになりました。

交流

コンテストが終わったあと、kosakkunさんに声をかけてもらって色々喋りました（話してる途中で判明したが奇跡的に順位が一つ違いだった）。他にもiwashi31さん、kuusoさんなどツイッターでフォローしている方々やkosakkunさんのお友達とも少しお話ができて望外の楽しい時間を過ごすことができました。普段周りに競プロどころかプログラミングやってる人すらマジで全然存在しないので、声に出して競技プログラミングのことを喋れるのこんなに楽しいんかいという感じでした。皆さんありがとうございました！

2017-10-27

Topcoder SRM 714 Div.1 Easy - ParenthesisRemoval

問題記録 Topcoder SRM SRM #714

問題概要

開き括弧と閉じ括弧のみからなる文字列Sが与えられる。初めSの括弧は正しく対応している。Sの一番前にある開き括弧と任意の閉じ括弧のペアを括弧の対応が不正にならないよう取り除く、という操作をSが空になるまで繰り返すとき、括弧の選び方の順番が何通りあるか答えよ。すべての括弧は一番最初のインデックスによって区別されるものとする。

|S| <= 2500

解法

閉じ括弧の側から考える。Sを前から見ていって最初の閉じ括弧に当たったとき、その閉じ括弧と一緒に消せる可能性があるのはそれより前にある開き括弧だけである。よって以下の手順で計算を行える。Sを前から見ていき、その文字が開き括弧ならカウンターを1増やす、閉じ括弧ならばカウンターを1減らす。閉じ括弧に当たった時点でのカウンターの数を掛け合わせたものが答え。O(|S|)

感想

視点を変えると一瞬で答えが出て面白かった

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

class ParenthesisRemoval {
public:
    int countWays(string s) {
        int N = s.length();
        ll ans = 1;
        ll open = 0;
        
        REP(i, N) {
            if (s[i] == '(') {
                open += 1;
            } else {
                ans = ans * open % MOD;
                open -= 1;
            }
        }
        
        return (int)ans;
    }
};

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