2018-01-16

第4回ドワンゴからの挑戦状予選 C - Kill/Death

問題概要

AチームとBチームにわかれて対戦するゲームがある。このゲームでは試合終了後に各プレイヤーのリザルトとしてkill数とdeath数が表示される。リザルトは各チームごとにkill数の多いプレイヤーから順に表示される。kill数が同数の場合はdeath数の少ない順になる。ある試合が終わったあとのAチーム(N人)のリザルトとBチーム(M人)のリザルトがkill数のみ表示された状態で与えられるので、ありうるdeath数の組合せが何通りあるか求めよ。ただしAチームのdeathはBチームのkillによってしか起こらず、BチームのdeathはAチームのkillによってしか起こらないものとする。

N, M <= 100, 各チームのkill数の合計 <= 1000

解法

もし「kill数が同数の場合はdeath数の少ない順になる」という制約がなければ、以下のようなDPで答えを求めることができる。

dp(i, j): i人目までにj個のdeathを割り当てたときの、deathの配り方

DPの遷移は単純にi人目に何個のdeathを配るかということになるので、0～sum(kill数の合計)を総当たりすればよい。このDPの計算量はO(N×sum(kill数)²)でおおよそ10⁸くらいになる。このくらいであればやたら定数倍が重いデータ構造を使うのでもない限り間に合う範疇である（と感覚的には思っている）。

次に「kill数が同数の場合はdeath数の少ない順になる」という制約を入れた場合であるが、これも基本的には上のDPと同じ形で解くことができる。そのために必要な考え方は「ある人にdeathを1つ割り当てるとき、後ろに同じkill数の人たちが並んでいるのであれば、その人たちにも必ずdeathを1配ることにする」ということである。このような配り方をすると昇順のルールが崩れず、しかもdeathの割り当てを各人で独立に考えることができるようになる。

これを踏まえて上のDPを書き直すと、まずDPの状態は↑と同じである。遷移だけが少し変わっており、配るdeathの数を「自分＋自分の後ろにいてkill数が同じ人の数」の倍数に限ることにする（これが「後ろのひとたちにも同じ数deathを配る」に当たる）。最終的にはdp(N, sum(kill数))が答えとなる。計算量は前述のものと同様。

追記(2018/1/21)

コメント欄で id:nanae1914 さんに全体の計算量が O(N×sum(kill数)²) から O(N×sum(kill数)) に落ちるDP遷移を教えてもらいました。これだと10⁸が10⁵に落ちるので圧倒的に間に合いますね（というか想定解をブチ抜いている）。詳しく書いていただいたのでぜひコメントの方を見てみてください。

感想

解けたはいいものの、分割数という概念をよく知らないので要勉強

コード

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;


long calc(int n, int[] a, int kills) {
    auto same = new long[](n);
    same[n-1] = 1;

    for (int i = n-2; i >= 0; --i) {
        if (a[i] == a[i+1]) same[i] = same[i+1]+1;
        else same[i] = 1;
    }

    auto dp = new long[][](n+1, kills+1);
    dp[0][0] = 1;

    foreach (i; 0..n) {
        foreach (j; 0..kills+1) {
            for (int k = 0; j + k <= kills; k += same[i]) {
                dp[i+1][j+k] += dp[i][j];
                dp[i+1][j+k] %= MOD;
            }
        }
    }

    return dp[n][kills];
}


void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto A = readln.split.map!(to!int).array;
    auto B = readln.split.map!(to!int).array;
    long ans = calc(N, A, B.sum) * calc(M, B, A.sum) % MOD;
    ans.writeln;
}

2018-01-11

yukicoder No.614 壊れたキャンパス

問題記録 yukicoder

問題概要

K階建ての棟がN個あり、棟a_iのある階と棟(a_i+1)のある階を結ぶ渡り廊下がM個ある。「コスト0で渡り廊下を渡る」「コスト1で同じ棟の1つ上または1つ下の階に移動する」の2種類の移動が行えるとき、棟1のS階から棟NのT階へ移動するために必要なコストの最小値を求めよ。

N <= 2×10⁵, M <= 2×10⁵, K <= 10⁹

解法

頂点と辺をうまいこと張ってダイクストラをする。

頂点は（棟, 階）のペアとする。ここで頂点として考える必要があるのは各渡り廊下の両端と(1, S)と(N, T)のみである。渡り廊下の両端は高々2M個なので、頂点数はO(M)で抑えられる。

次に辺を張る。まず渡り廊下に関しては定義通りに普通に辺を張ればよい。問題になるのが同じ棟内での移動で、ここを愚直にやろうとすると辺の数がO(M²)になってしまうが、実はそんなことをする必要はなく、各頂点から見て同じ棟の上下でそれぞれ一番近い階だけに辺を張ればよい（それより遠くに行く場合でもそこは絶対通るので）。これで辺の数もO(M)になる。ダイクストラを回すとO(MlogM)。

感想

1ヶ月くらい競プロ的に死んでたのでぼちぼち元に戻していきたい

コード

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 INF = 1L << 60;
alias Edge = Tuple!(int, "bld", int, "floor");

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto S = s[3];
    auto T = s[4];
    auto G = new Edge[][int][](N);
    auto floors = new int[][](N);
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1][s[1]] ~= Edge(s[0], s[2]);
        floors[s[0]-1] ~= s[1];
        floors[s[0]] ~= s[2];
    }
    floors[0] ~= S;
    floors[N-1] ~= T;

    foreach (i; 0..N) {
        floors[i].sort();
        foreach (j; 0..floors[i].length.to!int-1) {
            G[i][floors[i][j]] ~= Edge(i, floors[i][j+1]);
            G[i][floors[i][j+1]] ~= Edge(i, floors[i][j]);
        }
    }


    auto dist = new long[int][](N);
    foreach (i; 0..N)
        foreach (j; floors[i])
            dist[i][j] = INF;
    
    auto pq = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[2] > b[2]");
    pq.insert(tuple(0, S, 0L));

    while (!pq.empty) {
        auto tt = pq.front;
        pq.removeFront;
        auto b = tt[0];
        auto f = tt[1];
        auto cost = tt[2];
        if (dist[b][f] <= cost) continue;
        dist[b][f] = cost;
        if (!(f in G[b])) continue;
        
        foreach (e; G[b][f]) {
            auto nb = e.bld;
            auto nf = e.floor;
            auto nc = cost + (b == nb ? abs(f-nf) : 0L);
            if (nc < dist[nb][nf]) pq.insert(tuple(nb, nf, nc));
        }
    }

    if (dist[N-1][T] >= INF) dist[N-1][T] = -1;
    dist[N-1][T].writeln; 
}

2017-12-04

競プロ始めて1年半

競プロ雑記

はじめに

ちょうどいいタイミングなので振り返りの記事を書きます。過去の同じような記事は以下

レーティング

半年前とのhighest比較がこちら

AtCoder: 1919 -> 2177
Codeforces: 1952 -> 2064
Topcoder: 1428 -> 1549

AtCoderは8月あたり、Topcoderはつい先日黄色に上がり、とうとう3つ全部で青より上に行くことができました。特にAtCoderは結構な期間同じようなレーティング帯を彷徨っていたので、ここで黄色になれたのは競プロ始めて一番達成感のあったことかもしれません。あとおれはどこかでレッドコーダーだったような気がするがそんなことはなかったぜ

ここ半年での進捗

解いた問題の記録をブログに書き始めた

8月辺りからこのブログに解いた問題の解法を自分なりにまとめてぼちぼち書いています。これは100パーセント自分のためで、考察を詰め切らずに実装を始める悪癖を矯正するためにやっています。コンテスト本番で間違った方針の実装を始めて時間を吹っ飛ばすことがよくあるので…。今のところは自力では解けず解説を見て通した問題とか頑張って考えてなんとか自力で解けたくらいの問題を記事書く対象にしています。実際書こうとすると一度通した問題であっても自分の中で納得するレベルまで正当性を詰めて文章に起こすのは意外と難しく、いかに雰囲気で競プロしてるか実感させられます。効果のほどですが、まあある程度は合ってるかよくわかんないうちから実装始めることは減ったかなあという気はしてます。代わりに座る時間が増えた（コンテストを終えた時おれの解答は実装を置き去りにした）

企業コンテストの本戦オンサイトに参加できた

DDCC2017の本戦に参加させてもらうことができました。今年頭の日本橋ハーフマラソンに続いて2回目の企業コン本戦でした。

Kaggleをちょっとやってみた

札束殴りゲームと聞いているので怖いですが、入門以外のコンペにもコミットしていきたいところ

全体的に

結構レーティング上がったし長いこと目標だったAtCoder黄に届いたしオンサイトで声をかけてもらったりして人との交流もできたしで割と充実した期間だったんじゃないでしょうか。競プロたのしいね。

今後の目標

AtCoderオレンジ
また企業コン本戦に
長期コンテストもがんばる
創作活動

2017-11-14

Topcoder SRM 711 Div.1 Easy - ConsecutiveOnes

問題記録 Topcoder SRM SRM #711

問題概要

整数n, kが与えられる。n以上の整数のうち、2進表現で1がk個続く部分を持つような数で最小のものを求めよ。

0 <= n < 2⁵⁰
k <= 50

解法

1がk個続く箇所を全探索する。1が続く箇所より上位の桁はnと同じになるよう埋めるのが最善。より下位の桁は、場合分けする。(1) k個の1で埋めた箇所が、元のnでも全部1である場合→上位の桁同様、下位の桁もnと同じ数で埋める（こうしないとnを下回ってしまう） (2) そうでない場合→下位の桁は全部0で埋めてOK （こうしてもnを下回らない）

感想

地味にややこしく見えるがビット操作に慣れてきて結構簡潔に書けた

コード (C++)

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

class ConsecutiveOnes {
public:
    ll get(ll n, int k) {
        ll ans = 1LL << 59;
        ll a = (1LL << k) - 1;
        
        for (int i = 0; i <= 60-k; ++i) {
            ll tmp = n | (a << i);
            if (tmp != n)
                for (int j = 0; j < i; ++j)
                    tmp &= ~(1LL << j);
            ans = min(ans, tmp);
        }

        return ans;
    }
};

2017-11-14

Topcoder SRM 712 Div.1 Easy - LR

Topcoder SRM SRM #712 問題記録

問題概要

N要素の数列S, Tが与えられる。Sに対してLとRという2種類の操作を行うことができる。操作の結果SをTに等しくできるか判定せよ。できるならば具体的に操作の列をひとつ示せ。なおTに等しくできる場合、操作の回数は100回以下になることが証明できる。

操作L: S[i]の値をS[i]+S[i-1]とする。ただしi=0のときはS[i]+S[N-1]
操作R: S[i]の値をS[i]+S[i+1]とする。ただしi=N-1のときはS[i]+S[0]

N <= 50, 0 <= S[i], T[i] <= 10¹⁵

解法

最終的にそれぞれの回数が同じであるならば、L, Rを行う順番は結果に影響しない。つまりLLLRRRもRRRLLLもRLRLRLも結果として出てくる数列は同じである。ゆえにまず操作を行う全体回数を決め打ちし、その中でまたLを行う回数を決め打ちするという全探索を行えばよい。操作の全体回数はO(log(max(T[i])))で抑えられそうだが、問題文で100回でOKといっているのでこれを素直に使えばいい。オーバーフローには注意が必要で、足し算を行うたび毎回Sの各要素がTを超えていないかチェックするとこれを避けることができる。

感想

オーバーフローが罠い

コード (C++)

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

int N;
ll A[55];
ll B[55];
ll C[2][55];
const ll MAX = 1000000000000000;

class LR {
public:
    bool check(int L, int R) {
        REP(i, N) C[0][i] = A[i];
        int cur = 0, tar = 1;
        
        REP(l, L) {
            REP(i, N) C[tar][i] = C[cur][i] + C[cur][(i-1+N)%N];
            REP(i, N) if (C[tar][i] > MAX) return false;
            cur ^= 1;
            tar ^= 1;
        }
        
        REP(r, R) {
            REP(i, N) C[tar][i] = C[cur][i] + C[cur][(i+1)%N];
            REP(i, N) if (C[tar][i] > MAX) return false;
            cur ^= 1;
            tar ^= 1;
        }

        REP(i, N) if (B[i] != C[cur][i])
            return false;

        return true;
    }
    
    string construct(vector<ll> s, vector<ll> t) {
        N = s.size();
        REP(i, N) A[i] = s[i];
        REP(i, N) B[i] = t[i];

        REP(i, 101) REP(L, i+1) {
            int R = i - L;
            if (check(L, R)) {
                string ans = "";
                REP(_, L) ans += "L";
                REP(_, R) ans += "R";
                return ans;
            }
        }

        return "No solution";
    }
};

2017-11-13

yukicoder No.109 N! mod M

yukicoder 問題記録ウィルソンの定理

https://yukicoder.me/problems/no/109

問題概要

T個の数の組(N, M)が与えられるので、それぞれでN! mod Mを求めよ

1 <= T <= 100
1 <= M <= 10⁹
max(0,M−10⁵) <= N <= 10⁹

解法

まず自明なケースとして、NがM以上の場合答えは0である(N!で掛ける数の中に必ずMが登場するため）。以下では N < Mとして考える。

サンプルを見ると、N=999999936, M=999999937 で答えが 999999936 というのが目につく。もしかしてMが素数ならば (M-1)! ≡ M-1 (mod M) というような法則でも成り立っているのだろうか…と思っていくつかの素数で実験してみると、どうやら当たっているように思える（実際にはウィルソンの定理として知られている）。この仮定に基づくとMが素数の場合にはM-1から始めてどんどん逆元をたどっていけば求めることが可能になる。ここで N >= M-10⁵ という怪しげな制約が生きてきて、この遡りが10⁵ステップ以内に終了することを保証してくれる。これでMが素数の場合は解けた。

次にMが合成数の場合。まずMが十分大きければ答えは必ず0になる。例えば M >= 10⁶ とすると、制約より N >= 10⁶-10⁵ になる。ここでMを2以上の正整数2つ(m1, m2)の積で表すことにすると、その最大値は M/2 である。M > N > M/2 より m1, m2がともにN!の途中に現れることになるので、答えは0になる。一方、Mがそれより小さい場合には普通にmodをとりながら階乗を計算していけば答えを出すことができる。

感想

サンプルが優しいおかげでできた

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

bool is_prime(long n) {
    for (long i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

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

long solve() {
    auto s = readln.split.map!(to!long);
    auto N = s[0];
    auto M = s[1];

    if (M == 1)
        return 0;
    if (N == 0)
        return 1;
    if (N >= M)
        return 0;

    if (is_prime(M)) {
        long ret = M - 1;
        for (long cnt = M - 1; cnt > N; --cnt)
            ret = ret * powmod(cnt, M-2, M) % M;
        return ret;
    } else if (M < 10^^6) {
        long ret = 1;
        for (long i = 2; i <= N; ++i)
            ret = ret * i % M;
        return ret;
    } else {
        return 0;
    }
}

void main() {
    auto T = readln.chomp.to!int;
    while (T--)
        solve.writeln;
}

2017-11-13

yukicoder No.387 ハンコ

yukicoder 問題記録

https://yukicoder.me/problems/no/387

問題概要

Nマスが横に連なったハンコがあり、マスiには色Aiのインクがついている。(2N-1)マスの紙に対し、はじめこのハンコを左端が合うように置き、「ハンコを押すor押さない」→「ハンコを右に1マスずらす」という操作をN回繰り返す。各操作においてハンコを押すか押さないかは0/1の数列Bとして与えられる。紙の(2N-1)の各マスにおいて、最終的に押される色数の偶奇を答えよ。

N, A <= 10⁵

解法

同じ色は何回押しても1色とカウントされる → orっぽい
押される色数の偶奇を知りたい → xorっぽい

ということからビット操作に落とせないか考える。

まずハンコ側の視点で考えると、ハンコ側のマスiが紙側のどのマスに押されることになるかは、単純にビット列Bをiだけシフトさせればわかる（B=101のとき、ハンコの0マス目は紙の0マス目、2マス目に押される。ハンコの1マス目は2マス目、4マス目に押される。…）。よって、同じ色のマスについてこのビット列のbitwise orをとれば、最終的にその色が押されるマスを出すことができる。あとはすべての色についてそのビット列を計算し、bitwise xorをとっていけばあるマスに押される色数の偶奇を出すことができる。

ビット列の長さが 2N-1 なので各操作にO(N)かかりO(N²)となるが、ビット操作にC++のbitsetみたいなのを使うとワード長分（？）定数倍高速化がかかって 10¹⁰ / 64 ≒ 10⁸ くらいになって間に合うようになる。

感想

AtCoderでは絶対出ないタイプの問題だけど、前にhackerrankか何かでもN=10⁵でO(N²)をbitsetドーンが想定解なのを見たことあるなあ

コード (C++)

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

int N;
int A[101010];
int B[101010];
bitset<202020> bs;
bitset<202020> ans;
bitset<202020> tmp;
vector<int> rev[101010];

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];

    REP(i, N) rev[A[i]].push_back(i);
    REP(i, N) bs[i] = B[i] == 1;

    REP(c, 101010) {
        tmp = 0;
        for (auto i: rev[c]) 
            tmp |= (bs << i);
        ans ^= tmp;
    }

    REP(i, 2*N-1) cout << (ans[i] ? "ODD" : "EVEN") << "\n";
}