第3回 ドワンゴからの挑戦状 本選 A - 計算ドリル

http://dwacon2017-honsen.contest.atcoder.jp/tasks/dwango2017final_a

問題概要

0～9の数字と+, -の演算子のみからなる文字列Sが与えられる。この文字列を逆ポーランド記法とみなして計算を行ったときの最終的な計算結果をこの文字列の値とする。ただしこのとき文字列中に最初に含まれている0～9の文字は必ず一桁の数字とみなす。文字列SをK文字まで書き換えたとき、正しい逆ポーランド記法の式にすることができるかを判定せよ。またできるならば書き換えによって得られる最大の値を求めよ。

1 <= |S| <= 52, 0 <= K <= |S|

解法

この問題の制限の中での逆ポーランド記法は、以下のような文脈自由文法として表すことができる。

• <数> ::= ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’
• <演算子> ::= ‘+’ | ‘-’
• <数> ::= <数><数><演算子>

この定義に従えば、この問題はある区間を<数><数><演算子>の3つの区間に区切って再帰的に最大値を求めていく問題と考えることができる。つまり以下のようなDPで解くことができる。

dp(i, j, k) = i文字目からj文字目までの区間をひとつの<数>とみなしたとき、k文字まで書き換えて得られる最大の値（と最小の値）

DPの遷移を考えると、区間i～jの区切りを全部試すのにO(|S|), 区間にkをいくつ割り振るかでもO(|S|)かかるので、状態数のO(|S|^3)と合わせて結局O(|S|^5)となる。52⁵≒4*10⁸で結構不安になるが、実際には区間がどんどん短くなっていくため定数倍はだいぶ軽い。

細かい話として、演算子にはマイナスもあるのでDPでは最小の値も保持しておく必要がある（演算子がマイナスの場合、例えば最大値－最小値が最大になりうる）。また「正しいポーランド記法にできない」を表すのにも特別な値を割り当てるなどの処理が必要。

感想

DPを思いつくのが大変だったし、実装はもっと大変だった。こういう細かい部分の実装がめんどくさい問題ってAtcoderだと珍しい印象。

コード (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;
 
int INF = 1 << 29;
 
bool isDigit(char c) {
    return c - '0' >= 0 && c - '9' <= 9;
}
 
void main() {
    auto K = readln.chomp.to!int;
    auto S = readln.chomp;
    auto N = S.length.to!int;
 
    auto mem = new Tuple!(int, int)[][][](N, N, K + 1); // (min, max)
    foreach (i; 0..N) foreach (j; 0..N) fill(mem[i][j], tuple(INF, INF));
    
    Tuple!(int, int) dfs(int l, int r, int k) {
        if (mem[l][r][k][0] != INF) return mem[l][r][k];
 
        int L = r - l + 1;
        
        if (L % 2 == 0) {
            return tuple(-INF, -INF);
        } else if (L == 1) {
            if (k > 0) return tuple(0, 9);
            else if (S[l].isDigit) return tuple(S[l] - '0', S[l] - '0');
            else return tuple(-INF, -INF);
        } else {
            if (k == 0 && S[r].isDigit) return tuple(-INF, -INF);
            int mn = INF;
            int mx = -INF;
            foreach (kk; max(0, k-1)..k+1) {
                char[] op;
                if (kk == k) {
                    if (S[r] == '+') op = ['+'];
                    else if (S[r] == '-') op = ['-'];
                    else continue;
                } else {
                    op = ['+', '-'];
                }
 
                for (int i = l; i < r; i += 2) {
                    foreach (j; 0..kk+1) {
                        auto t1 = dfs(l, i, j);
                        auto t2 = dfs(i + 1, r - 1, kk - j);
                        if (t1[0] == -INF || t2[0] == -INF) continue;
                        foreach (opp; op) {
                            if (opp == '+') {
                                mn = min(mn, t1[0] + t2[0]);
                                mx = max(mx, t1[1] + t2[1]);
                            } else {
                                mn = min(mn, t1[0] - t2[1]);
                                mx = max(mx, t1[1] - t2[0]);
                            }
                        }
                    }
                }
            }
 
            mem[l][r][k] = mn == INF ? tuple(-INF, -INF) : tuple(mn, mx);
            return mem[l][r][k];
        }
    }
 
    auto ans = dfs(0, N - 1, K);
    if (ans[0] == -INF) writeln("NG");
    else {
        writeln("OK");
        writeln(ans[1]);
    }
}

AtCoder Regular Contest 080 E - Young Maids

http://arc080.contest.atcoder.jp/tasks/arc080_c

問題概要

偶数N、1～Nの順列P、空の数列Qがある。Pが空になるまで以下の操作を行う。

操作: Pの隣り合う2要素を選び、順序を保ったままQの先頭に追加する。

これによってできるQのうち、辞書順で最小のものを求めよ。

N <= 2 * 10⁵

解法

操作を逆順で考え、前から順に値を確定させていく。ここで逆操作は以下のように言うことができる。

1. 「手持ちの区間」からひとつの区間[l, r]を選び、「手持ちの区間」から取り除く
2. 選んだ区間の「先頭から数えて奇数番目の要素」をひとつ選び、そのindexをaとする
3. 選んだ区間の「先頭から数えて偶数番目かつaより後ろにある要素」をひとつ選び、そのindexをbとする
4. (P[a], P[b])をこの順でQの末尾に追加する
5. 区間[l, a-1], [a+1, b-1], [b+1, r]のうち空でないものをすべて「手持ちの区間」に追加する

解を得るためには選びうる(a, b)のうちで(P[a], P[b])が辞書順最小のものを貪欲に取っていく必要がある。すなわち「手持ちの区間」のすべてについて「先頭から数えて奇数番目の要素の最小値」を調べてそれが最小となる区間を取ってくること、さらにそれに対応する偶数番目の最小値を取ってくることが必要になる。ここで「手持ちの区間」全部を毎回愚直調べているとO(N²)になって間に合わない。必要なのは以下の操作を高速に行うことである。

1. ある区間における「先頭から奇数番目の要素の最小値」を求める
2. ある区間における「先頭から偶数番目の要素の最小値」を求める
3. 「手持ちの区間」の中から「先頭から数えて奇数番目の要素の最小値」が最小の区間を求める

このうち1, 2の操作はセグメント木を2本持つことで行うことができる。片方のセグメント木にはPのindexが奇数のものを詰め、もう片方には偶数のものを詰める。「先頭から奇数番目の要素の最小値」を求めたいときは区間の始まりのindexの偶奇を見、対応する方のセグ木にクエリを投げればよい。

3は「手持ちの区間」をpriority queueで管理すればよい。priority queueで見る値として、その区間の「先頭から奇数番目の要素の最小値」を入れておく。これはpriority queueに突っ込むときに一度だけ計算すればよい。

以上で区間の選択, 最小値の取得, 区間の分割の各操作がO(logN)で行え、全体としてO(NlogN)になる。

感想

やった〜〜〜〜黄色になれたよ〜〜〜〜〜〜〜〜〜〜〜〜〜〜おかあさ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜ん

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

alias Tuple!(int, "a", int, "l", int, "r") Seg;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto B = new int[](N+1);
    foreach (i; 0..N) B[A[i]] = i;

    auto st1 = new SegmentTree(N + 1);
    auto st2 = new SegmentTree(N + 1);

    for (int i = 0; i < N; i += 2) st1.assign(i, A[i]);
    for (int i = 0; i < N; i += 2) st2.assign(i+1, A[i+1]);

    int query(int l, int r) {
        if (l % 2 == 0) return st1.query(l, r);
        else return st2.query(l, r);
    }

    auto ans = new int[](N);
    int p = 0;

    auto pq = new BinaryHeap!(Array!Seg, "a[0] > b[0]");
    pq.insert(Seg(query(0, N-1), 0, N-1));

    while (!pq.empty) {
        auto seg = pq.front;
        pq.popFront;
        auto l = seg.l;
        auto r = seg.r;
        int a = seg.a;
        int ai = B[a];
        int b = query(ai+1, r);
        int bi = B[b];
        ans[p++] = a;
        ans[p++] = b;
        if (ai != l) pq.insert(Seg(query(l, ai-1), l, ai-1));
        if (bi != r) pq.insert(Seg(query(bi+1, r), bi+1, r));
        if (ai + 1 != bi) pq.insert(Seg(query(ai+1, bi-1), ai+1, bi-1));
    }

    ans.map!(a => a.to!string).join(" ").writeln;
}


class SegmentTree {
    int[] table;
    int size;
    immutable int INF = 1 << 29;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new int[](size);
        fill(table, INF);
    }

    void assign(int pos, int num) {
        return assign(pos, num, 0, 0, size/2-1);
    }

    void assign(int pos, int num, int i, int left, int right) {
        if (left == right) {
            table[i] = num;
            return;
        }
        auto mid = (left + right) / 2;
        if (pos <= mid)
            assign(pos, num, i*2+1, left, mid);
        else
            assign(pos, num, i*2+2, mid+1, right);
        table[i] = min(table[i * 2 + 1], table[i * 2 + 2]);
    }

    int query(int pl, int pr) {
        return query(pl, pr, 0, 0, size/2-1);
    }

    int query(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return INF;
        else if (pl <= left && right <= pr)
            return table[i];
        else
            return
                min(query(pl, pr, i*2+1, left, (left+right)/2),
                    query(pl, pr, i*2+2, (left+right)/2+1, right));
    }
}

Codeforces Round #427 Div. 2 E - The penguin's game

http://codeforces.com/contest/835/problem/E

問題概要

N要素の数列があり、そのうち2要素はYで残りの要素はXである。質問クエリとして数列のインデックスの部分集合を指定すると、それらの値のXORを知ることができる。19回以内の質問クエリで値Yを持つ2要素のインデックスを特定せよ。

2 <= N <= 1000

解法

求めたい2要素のインデックスをp1, p2とする。

場合分けして考えてみると、1回の質問クエリによって得られる情報は①「その部分集合内にYが1個ある」②「その部分集合内にYが0個or2個ある」のいずれかであることがわかる。

重要な観察として「数列のインデックスを2進数で表現したとき、n桁目のbitが立っているインデックスの集合を質問クエリで投げると、(p1 xor p2)のn桁目の値が得られる」という事実がある。なぜなら、この質問クエリの回答が①であればp1とp2は違うグループにいる＝その桁の値が異なる＝xorが1であり、②であればp1とp2は同じグループにいる＝その桁の値が同じ＝xorが0になるからである。N <= 1000より高々10回の質問クエリですべての桁のxor, すなわち(p1 xor p2)の値そのものを得ることができる。

ここで得られた(p1 xor p2)からbitが立っている桁をひとつ選び、これをx桁目と呼ぶことにする（p1 != p2より、少なくとも1桁は必ずbitが立っている）。あとはx桁目を除く各桁iに対して(x桁目のbitが立っている && i桁目のbitが立っている)という集合の質問クエリを投げると。p1かp2の片方が特定できる。(p1 xor p2)は既知なので、片方がわかればもう片方もわかる。以上でp1とp2が求まった。

前半のxorを求めるパートで高々10回、後半の特定パートで高々9回の合計19回ちょうどで制限内に質問クエリが収まる。

感想

本番結構考えてまったくわからなかったんですがnvipさんのツイートのおかげで理解できました。 ビットごとに絞り込むの自分では絶対思いつかないけど色々使えそうなんで覚えておきたい

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


int ask(int[] q) {
    writeln("? " ~ q.length.to!string ~ " " ~ q.map!(a => a.to!string).join(" "));
    stdout.flush;
    return readln.chomp.to!int;
}

void answer(int x, int y) {
    writeln("! ", x, " ", y);
    stdout.flush;
}

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto X = s[1];
    auto Y = s[2];

    int xor = 0;
    foreach (mask; 0..10) {
        int[] q;
        foreach (i; 1..N+1) if (i & (1 << mask)) q ~= i;
        if (q.length == 0) continue;
        int ret = ask(q);
        ret = ret == X || ret == 0 ? 0 : 1;
        xor |= (ret << mask);
    }

    int b;
    foreach (mask; 0..10) if (xor & (1 << mask)) b = mask;

    int ans = 1 << b;
    foreach (mask; 0..10) {
        if (mask == b) continue;
        int[] q;
        foreach (i; 1..N+1) if ((i & (1 << mask)) && (i & (1 << b))) q ~= i;
        if (q.length == 0) continue;
        int ret = ask(q);
        ret = ret == X || ret == 0 ? 0 : 1;
        ans |= (ret << mask);
    }

    int ans2 = xor ^ ans;
    answer(min(ans, ans2), max(ans, ans2));
}

Codeforces Round #427 Div. 2 D - Palindromic characteristics

http://codeforces.com/problemset/problem/835/D

問題概要

ある文字列に対して以下のようにk-palindromesが定義される。

• 1. 文字列が回文ならば、その文字列は 1-palindrome である
• 1. k > 1 のとき、文字列の左半分と右半分が等しく、かつ左半分が (k-1)-palindromeならば、その文字列は k-palindromeである

文字列Sが与えられるので、Sのすべての連続部分文字列においてk-palindromeが何個存在するかを、すべてのkについて求めよ。

|S| <= 5000

解法

i, j (0 <= i <= j < N) について

dp(i, j) = 部分文字列S[i..j]の最大のk

を求める。

dpの中で毎回愚直に回文判定してるとO(|S|^3)とかになるので事前に回文テーブルを作っておく。ある文字Xを中心にしたときに作れる最長の回文を考えると、テーブルはO(|S|^2)で作れる。部分文字列S[i..j]が回文かどうかはi, jの真ん中の点を中心にしたときに作れる回文の長さがi~jの長さを超えているかどうかで判定できる。これで前処理・dpともにO(|S|^2)になって間に合う。

またある文字列が k-palindrome であれば必ず (k-1) palindrome でもあるので、dpで最大のkを求めたら最後に累積和をとって答えが出せる。

この問題ではオーダーに効いてこないので意味ないが、Manacherのアルゴリズムとかいうのを用いると上で作ったような回文テーブルの計算がO(|S|)でできるらしいです。参考：文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

感想

本番ではdp部分をループで書こうとしてわけわかんなくなってたけど再帰で書き直したらだいぶすっきりしました。とはいえ「k-palindrome であれば必ず (k-1) palindrome」のところがちゃんとわかってればどっちで書こうと大差ないですね。本番ではわかってなかったので終了でした。

コード (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 P_odd = new int[](N);
    auto P_even = new int[](N);

    foreach (i; 0..N) {
        P_odd[i] = 1;
        for (int j = 1; i - j >= 0 && i + j < N && S[i - j] == S[i + j]; ++j) {
            P_odd[i] += 2;
        }
    }

    foreach (i; 0..N-1) {
        for (int j = 0; i - j >= 0 && i + j + 1 < N && S[i - j] == S[i + j + 1]; ++j) {
            P_even[i] += 2;
        }
    }


    auto mem = new int[][](N, N);
    foreach (i; 0..N) fill(mem[i], -1);

    int dfs(int i, int j) {
        if (mem[i][j] >= 0) return mem[i][j];
        if (i > j) return 0;
        if (i == j) return 1;

        int L = j - i + 1;
        int m = (i + j) / 2;
        int ret;
        
        if (L % 2 == 1) {
            if (P_odd[m] >= L)
                ret = dfs(i, m - 1) + 1;
            else
                ret = 0;
        } else {
            if (P_even[m] >= L)
                ret = dfs(i, m) + 1;
            else
                ret = 0;
        }

        return mem[i][j] = ret;
    }

    
    auto A = new int[](N + 2);
    foreach (i; 0..N) {
        foreach (j; i..N) {
            int ret = dfs(i, j);
            A[0] += 1;
            A[ret + 1] -= 1;
        }
    }

    foreach (i; 0..N) A[i + 1] += A[i];

    A[1..$-1].map!(a => a.to!string).join(" ").writeln;
}

Topcoder SRM 718 Div1 Easy - InterleavingParenthesis

これまで全然やっていなかったSRMの過去問埋めをぼちぼちやっていこうという気持ちになりまして、せっかくだから解いた問題に関しては記録をつけていこうと思います。当面はDiv1 Easyを新しいものからやっていく予定です。この1回で飽きる可能性もありますがその時は察してください。記事の形式はkmjpさんのブログの影響をめちゃめちゃ受けています（僕はkmjpさんのブログをめちゃめちゃ見過ぎているので）。

問題概要

開き括弧と閉じ括弧の2種類の文字のみからなる文字列s1, s2が与えられる。次の操作を行って得られる文字列のうち、括弧の対応が正しくなるものは何通りか。

操作: s1, s2のうち空でないものをひとつ選び、選んだ方の先頭の文字を削除して新文字列の末尾に加える。これを両方の文字列が空になるまで続ける。

|s1| <= 2500, |s2| <= 2500

解法

dp[i][j] = s1をi文字目、s2をj文字目まで見たときの文字の取り方　としてdp.

遷移を考えると(s1から何文字取ったか, s2から何文字取ったか, 開かれている括弧の数)でdpしたくなるが、それだと2500³で間に合わない。よくよく考えると何文字目まで見たかがわかってるなら開かれ括弧の数は一意に定まるので状態として持つ必要はなく、結局s1, s2から何文字取ったかの2つだけ見ればよいことがわかってO(|S|^2)。

遷移はこんな感じでやった

• 開かれ括弧が0より多い → 開き括弧も閉じ括弧も取れる
• 開かれ括弧がちょうど0 → 開き括弧しか取れない
• 開かれ括弧が0より少ない → 取れない

感想

解けてみれば至って普通のdpなんですが、3乗から2乗に落とすのにちょっと困ってしまいました。

コード (C++)

const ll MOD = 1000000007;

class InterleavingParenthesis {
    public:
    int countWays(string s1, string s2) {
        int N = s1.size();
        int M = s2.size();
        vector<int> A(N + 1, 0);
        vector<int> B(M + 1, 0);
        REP(i, N) A[i + 1] = A[i] + (s1[i] == '(');
        REP(i, M) B[i + 1] = B[i] + (s2[i] == '(');
        cout << A[N] << " " << B[M] << endl;

        if ((A[N] + B[M]) * 2 != N + M) return 0;


        vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
        dp[0][0] = 1;

        REP(i, N + 1) REP(j, M + 1) {
            int open = A[i] + B[j] - (i + j - A[i] - B[j]);
            if (open > 0) {
                if (i < N) (dp[i + 1][j] += dp[i][j]) %= MOD;
                if (j < M) (dp[i][j + 1] += dp[i][j]) %= MOD;
            } else if (open == 0) {
                if (i < N && s1[i] == '(') (dp[i + 1][j] += dp[i][j]) %= MOD;
                if (j < M && s2[j] == '(') (dp[i][j + 1] += dp[i][j]) %= MOD;
            }
        }

        return dp[N][M];
    }
};

主人が競技プログラミングを始めて一年が経ちました

はじめに

いきなりの投稿失礼します。 久光さやか、29歳の未亡人です。 お互いのニーズに合致しそうだと思い、記事を書いてみました。 自分のことを少し語ります。 昨年の5月、わけあって競技プログラミングをはじめました。 自分は…アルゴリズムのことを…死ぬまで何も理解していなかったのが とても悔やまれます。 主人はTopcoderに頻繁に参加していたのですが、 それは遊びの為のプログラミングコンテストではなかったのです。 レーティングを得るために、私に内緒であんな危険なchallengeをしていたなんて。 一年が経過して、ようやく主人の0完＋チャレンジ失敗から立ち直ってきました。 ですが、お恥ずかしい話ですが、毎日の孤独な夜に、 身体の火照りが止まらなくなる時間も増えてきました。 主人の残した財産は僅少なレーティングです。 つまり、WAは幾らでも出きますので、 私の競プロ欲を満たして欲しいのです。 お返事を頂けましたら、もっと詳しい話をしたいと 考えています。連絡、待っていますね。

レーティング

AtCoder

半年前: 1728（青）→ 現在: 1930（青） / highest: 1930 (2017/06/24)

メインで参加しているプロコンサイトです。レーティングの面では残念ながら色を変えるほどには上げられませんでした。 きりよく一年で黄色になれましたと言いたいところだったんですが……。ただ最近は全然振るわない時期を抜けて少しずつhighestを更新できているので、1年半経つ前には黄色に届きたいですね。

Codeforces

半年前: 1579（緑）→ 現在: 1928（紫） / highest: 1952 (2017/04/21)

AtCoderほどではないですがこっちも結構参加しています。振り返ると半年前は4回しか参加してなかったんですね。一時期全然解けないしシステムテスト落ちるし問題文が読みづらすぎるしでマジで苦手だったんですが最近は結構解けるので好きです。あとAtCoder, Codeforces, Topcoderの中で唯一青より上に行けているので好きです。Div1残留安定が目標。

Topcoder SRM

半年前: 参加経験なし → 現在: 1215（青） / highest: 1428 (2017/02/09)

微妙なところです。最初結構順調で黄色楽勝じゃんとか調子こいてたんですが負の点数取って一気に緑に落ちたりして今は間くらいで落ち着いてます。開催自体が少ないのと平日昼間にやることが多くて参加回数増えない・フィードバックなしのチャレンジありなので点数も安定しないといった理由でレーティングが収束してるような感触が全然ありません。とはいえ分散がでかければその分上振れする余地もでかいと思うので黄色に一番近いのはここかな〜と勝手に思ってます。

その他のコンテスト

CSAcademyとかHackerRankとかCodechefとかにたまに参加しています。

過去問埋め

だいたいAtCoderかyukicoderの過去問を埋めています。yukicoderは最近レベル75になりました。しばらく考えてわからない問題は割とホイホイ解説を見てしまっています。知識面に関しては黄色目標レベルなら「知らなかったから解けなかった」はもうほぼないかなとなってきたので最近は考え方とか発想とかそういうところを吸収するようにしたいな〜〜って感じです。

今日ツイッターで流行っていたやつだとこんな感じ

The Number of Solved Problems By fluffyowl
TopCoder: 8
CodeForces: 122
AtCoder: 698
AOJ: 46
Sum: 874
https://t.co/U9iUufPPxU

— アルハンブラ宮殿のゆるキャラ (@nebukuro09) 2017年6月26日

そろそろTopcoderとかCodeforcesも埋めていきたいですね。

その他の進捗

オンサイトに出れた

前の記事の話ですが、RCOさんの日本橋ハーフマラソンの本戦に出ることができました。念願の初競プロ衣服も頂けてとても嬉しい経験でした。思い返すとこのコンテストは突出しなくていい（2問両方でそこそこの得点を取るのでも上位に行ける可能性がある）という点で自分に合っていて運が良かったな〜〜と思います。

GCJでTシャツ

Google Code JamでTシャツがもらえました。1000位以内でTシャツのところ999位に滑り込み（終了時点では1004位とかで一日経ったらなぜか順位上がっていてマジで滑り込みだった）、2つ目の競プロ衣服獲得となりました。パーカー・Tシャツときてるのでズボンとか靴下とかを配るプログラミングコンテストが待たれます。

マラソンにも手を出した

上の日本橋ハーフマラソンの件とも関連しますが長期間のコンテストにもちょいちょい手を出したりしています。Topcoder MM, Codingameなど。実力不足による徒労感があったりして最初の方ほどモチベーションは高くないですが…。

競技プログラミングの効能

• 楽しい！
• コーディング欲が満たせる！
• 日々の生活に小さな目標ができる！
• 10歳下の人にボコボコにされる！
  • 老害になりたくない人は競技プログラミングをやろう！

おわりに

半年時点で記事書いておいて今回書かないのもあれかな〜と思いつつぐだぐだ引き伸ばしてたら1年と1ヶ月になってしまいました。他にすることないし競プロはまだまだ楽しいし、今のところ飽きる気配はなさそうです。最近はKaggleとか、あと大学の数学をちゃんとやるのとかに興味が発展してきてるのでそっちの方もやっていってよい循環を作れたらいいですね。あとこれは競プロだけじゃないんですがなにかしらを作ることに取り組んでいきたいという気持ちも出始めました。競プロの作問でもいいし競プロ関係ないプログラミングでもいいし絵でも小説でもいいのでなんか創作物を作ることも日常の活動に加えていけたらな〜という感じです。どうもありがとうございました。

RCO presents 日本橋ハーフマラソンに参加しました

3/20にRCO presents 日本橋ハーフマラソンに参加しました。競プロをやりだしたのが学生じゃなくなってからなので、予選付きコンテストでオンサイトに出ることは半ばあきらめていたんですが、予選でギリギリ引っかかって上げてもらいました。感謝です。

予選

A問題 Multiple Pieces

最初山登り的なものを実装しようとするが、実装が難しく最初の提出まで1時間かかった上に点数が泡を吹くほど低い。ただ低すぎたおかげで逆にそこまでの方針を捨てる踏ん切りがついて、ごくごく単純な貪欲で書き直したら点数が10倍くらい上がってそこそこの順位に。具体的には「全マスを大きい順のpriority queueに突っ込む→順に取り出して周りの大きいマスと貪欲にくっつけていく」という感じ。単純すぎて制限時間10sのところ6msで終わってしまう。このあたりで3時間中の1時間半くらいが経っていたので一旦よしとしてB問題へ行くことにする。

B問題 Food Collector

今度は時間をかけすぎたら終わりなのでA問題の教訓を活かしてとにかくまずは単純な方針からやっていこうと考える。ということで「初期解として完全ランダムにターン数分の移動命令を生成 → 何ターン分かの移動をランダムに変えてシミュレート → よくなるならその解に乗り換える」という山登りを10秒いっぱい回す。割とまともな点数が出て一安心し、残りの時間はこの方針をベースにして逐次改善していこうとしたが大して変わらず終了。

結果

A問題50位＋B問題73位で、全体49位。だいぶ微妙でしたが上位にオンサイト不参加者も何名かいたようで、「学生の上位40名を抜いたあとの上位10名枠」の9番目につけてギリギリ本戦に通してもらえました。

本戦

開始前

開始までは後ろの方に座ってぼやぼやしながらオンサイトの雰囲気を味わった。あと参加賞ということでパーカーをもらった。競技プログラミングで衣服をもらうのがひそかな目標だったのでとても嬉しかったです。あと気がつくと真後ろの席にAtCoderの社長が座っていてヒョエ〜〜〜〜となった。あと業務の説明を聞いてたのしそ〜〜〜となった。

A問題 石油王Xの憂鬱

問題文を読んだだけで変な汗が出た。めちゃくちゃ苦手な算数パズル（天秤をn回使って偽物の金貨を特定してくださいみたいな類のやつ）っぽかったからである。ちょっと考えるけど取れる行動も多いし方針すらまったく立たないのでさっさとB問題へ。

B問題 日本橋大渋滞

こっちはA問題と比べるとだいぶ素直な印象を受けた。まず何も考えず全車を目的地に向かわせる貪欲解を書いたところ、0だけの自明解(3331点)をちょっとだけ超える(4613点)。ここでビジュアライザを見てみると、どうやら車が多すぎてほとんどの車がまともに動けてないことがわかった。要するにこれをどうにかする問題なんだな〜〜〜とやっとこの段階で気づく。とにかくどこかで回り道させないといけないので、ある車が目的地に近づけない場合はランダムな移動を行うようにするとちょっと上がる(6513点)。たしかこの時点でB問題だと2位か3位を取れていてかなりウキウキしたが、1位の人を見ると60万点とかいう異次元のスコアを出していて最初真剣にバグか？？？？？と思った。さすがにここまでスコア差がつくということは根本的にもっといいやり方がなんかあると思ってスコアの計算式をよく読んでみると、かかったターン数で割り算が発生しており桁違いの差が付くならこの辺が鍵かなあなどと考える。自分の解を省みると制限ターンいっぱい使っていたのでこれは明らかにダメだろうと思い、解を得た段階でスコアの動きをシミュレートし一番よいターンで打ちきって出力とすることしてみる(12478点)。数十万のオーダーには全然届かないが順位的にはかなりよかったのでB問題はここで一旦やめにしてA問題へ。

A問題ふたたび

相変わらずアイデアは一切なかったが、ここで予選A問題の教訓（そんなんでいいの？という単純な方針でも割と点数取れることがある）を思い出し、めちゃくちゃ単純なやり方が何かないか考え始める。そこで「自分が持ってるどれかの容器1個とまったく同じ容量の注文を出してきた客には売る、そうでなければパス」というやり方で出してみたところ、とりあえず正の点数を得ることができた(154272点)。上位陣は700万とかで争っているので順位的にはアレだけどこれでだいぶ落ち着いた。ちょっとB問題で試したいことが浮かんでもう一回戻る。

B問題ふたたび

これまでの解答だと各ターンで車の移動を考えるとき与えられたインデックス順に動かしていたのをランダムな順番にするよう変更したらスコアが4倍くらいになった(52297点)。同じ順番で動かしているとデッドロックがとれづらいとかそういう理由だろうか？ともかく今度こそA問題にちゃんと向き合うことにする。

A問題みたび

さっきの超単純貪欲からもう一歩進んで、「自分の持ってる容器を足して作れる数字の注文が来たときは売る、そうでなれけばパス」という方針にすることを考えてみる。手持ちの数列から作れる和を求めるのはDPでよくあるやつだからこれならできる！と思い実装を始める。バグを仕込みまくって泣きそうになりながら3, 40分くらいかけてやっと書き上げて提出(5576164点)。これでA問題もオーダー的にはまともなスコアが出たので、あとはここからの改善だけを考えることにした。で思ったのが同じ和に対して組み合わせが複数通りあるときどの容器を売っぱらうかは大事だなということで、dpつくるとき保存しておく組み合わせの条件をいじったりしてたら結構よかった。いろいろあって最終的には100万点底上げできた(6657203点)

結果

A問題が11位、B問題が7位の合計18で全体6位（提出者48名）でした。まさかこんな順位を取れると思ってなかったのでマジか〜〜〜ウレシ〜〜〜〜〜と思いました。いい大人だったのでお金はもらえませんでした。（事前に学生以外賞金出ませんという連絡があってそのときは自分には関係のないことだと思って気にも留めていなかったということを思い起こすと、それが関係ある順位に入れたということでむしろもらえないことが嬉しくもあった（複雑な心の動き））

まとめ

正直今後オンサイトに出れる機会があるかと考えると自分の実力だとなかなか難しいところがあると思うので、今回は本当に良い経験になりました。このような機会を与えてくださったみなさまに感謝します。あといまぜんぜんプログラミングとか関係ない仕事してるので転職してコード書く人になりたいです。PythonとC++とD言語をよく書いています。何とは言いませんがよろしくお願いします。