AtCoder Regular Contest 005 C - 器物損壊！高橋君

問題

　の格子状の区画において、各マスは通行可能か不可能かのどちらかとなっている。2回だけ通行不可能なマスを通行できるとき、スタートからゴールまでたどり着けるか判定せよ。

解法

　通行可能ならコスト0、不可能ならコスト1として辺を構築してスタート地点からダイクストラ法を行い、ゴールまでの最短距離が2ならOK。

反省

　一度priority_queueに突っ込む構造体に対する変数の順番を縦と横で逆にしてしまいWA。それ以外は特に詰まることもなかった。

　ダイクストラは流石に書きなれて特に考えることもなくなってきたしなんかライブラリ化したくなってきたが、ノートパソコンだったりデスクトップだったり研究室だったりで複数の環境を使いうるので、共有が面倒くさそうと思ってしまいなかなか。全部Visual Studio使っているしgitとteam servicesで管理してしまえば楽なのかな。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll H, W;
    cin >> H >> W;
    vector<string> c(H);
    for (ll i = 0; i < H; i++) {
        cin >> c[i];
    }

    pair<ll, ll> s, g;
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            if (c[i][j] == 's') {
                s = { i, j };
            } else if (c[i][j] == 'g') {
                g = { i, j };
                c[i][j] = '.';
            }
        }
    }

    vector<vector<ll>> cost(H, vector<ll>(W, INT_MAX));
    struct Element {
        ll cost, x, y;
        bool operator<(const Element& rhs) const {
            return cost > rhs.cost;
        }
    };

    priority_queue<Element> pq;
    cost[s.first][s.second] = 0;
    pq.push({ 0, s.second, s.first });

    auto isOK = [&](ll x, ll y) {
        return (0 <= x && x < W && 0 <= y && y < H);
    };

    ll dx[4] = { 0, 1, 0, -1 };
    ll dy[4] = { 1, 0, -1, 0 };

    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();

        for (ll i = 0; i < 4; i++) {
            ll nx = t.x + dx[i];
            ll ny = t.y + dy[i];
            if (!isOK(nx, ny)) {
                continue;
            }
            ll nc = t.cost + (c[ny][nx] == '.' ? 0 : 1);

            if (nc < cost[ny][nx]) {
                cost[ny][nx] = nc;
                pq.push({ nc, nx, ny });
            }
        }
    }

    cout << (cost[g.first][g.second] <= 2 ? "YES" : "NO") << endl;
}

AtCoder Regular Contest 004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

問題

　が与えられるのでを満たし$$ \frac{\frac{N (N + 1)}{2} - M}{N} = \frac{X}{Y}$$であるを全て求めて列挙せよ。

解法

　式変形をすると$$N = 2\frac{X}{Y} + 2\frac{M}{N} - 1$$でありであるので、としてあり得るのはまたはの2通り。それらについてを計算して条件を満たすかチェックすればよい。

反省

　30WAくらい出してしまった。原因は範囲の絞り方がおかしかったりPythonでよくわからないWAを出しまくったり、順番を逆にしていたりなど。

　式変形で上のような絞り方をするのが思いついてこなかった。数字が大きいのでオーバーフローに気を付けて式変形しなければならない。大小関係から]の範囲に落とし込むテクは重要そう。特に整数の問題ならそれでかなり絞れる。

　とにかく苦労が多い問題だった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

int main() {
    string s;
    cin >> s;
    ll X = 0, Y = 0;
    bool slash = false;
    for (char c : s) {
        if (c == '/') {
            slash = true;
        } else if (!slash) {
            X *= 10;
            X += c - '0';
        } else {
            Y *= 10;
            Y += c - '0';
        }
    }

    ll k = gcd(X, Y);
    X /= k;
    Y /= k;

    vector<pair<ll, ll>> ans;
    for (ll i = 0; i < 2; i++) {
        ll N = 2 * X / Y + i;
        if (N % Y == 0) {
            ll M = N * (N + 1) / 2 - N / Y * X;
            if (1 <= M && M <= N) {
                ans.push_back({ N, M });
            }
        }
    }

    if (ans.size()) {
        for (auto p : ans) {
            cout << p.first << " " << p.second << endl;
        }
    } else {
        cout << "Impossible" << endl;
    }
}

SRM505 Div1 Easy - RectangleArea

問題

　の長方形を本の横棒、本の縦棒を用いて個の長方形に分割する。いくらかの小長方形の面積がわかっているとき、全体の面積を特定するために知る必要がある小長方形の個数を求めよ。

解法

　この記事にある通りunion find。

反省

　何か共有しているかどうかを見るんだろうなというところでunion-findが思いつかなかった。いろいろググって自分の考えていた方法と近いものを見つけてようやく理解できた。

　メタ読みばかりしてしまうのでTopCoderのレベル感に慣れないと全然問題が解けない。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

class RectangleArea {
public:
    int minimumQueries(vector <string> known) {
        const int N = (int)known.size();
        const int M = (int)known.front().size();
        initNodes(N + M);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (known[i][j] == 'Y') {
                    unite(i, N + j);
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < N + M; i++) {
            if (parent[i] < 0) {
                ans++;
            }
        }

        return ans;
    }
private:
    vector<int> parent;
    void initNodes(int num) {
        parent.resize(num);
        for (auto& node : parent) {
            node = -1;
        }
    }
    int root(int x) {
        return (parent[x] < 0 ? x : parent[x] = root(parent[x]));
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            parent[y] = x;
        }
    }
};

AtCoder Regular Contest 003 C - 暗闇帰り道

問題

　のマスが与えられ、各マスには障害物か1桁の数字が書き込まれている。各マスのコストはで与えられ、スタートからゴールまでの区間のコストの最小値がその経路のコストとなる。スタートからゴールまでのコストの最大値を求めよ。

解法

　2分探索でコストの最大値を決めていく。各コストでスタートからゴールまで行けるかどうかは幅優先探索で求まる。

反省

　ずっとダイクストラ法でやろうとしてTLEやらMLEやらを起こしていた。しばらく考えてもわからなかったので問題名でググって出てきたブログに上の解法が書かれていたのでそれを書いてAC。疲労から頭が回っていないのもあって正常な思考ができなかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

ll N, M;
vector<string> c;
pair<ll, ll> start, goal;


bool canGoal(double cost) {
    struct Element {
        ll x, y, time;
    };
    queue<Element> q;
    q.push({ start.second, start.first, 0 });

    vector<vector<bool>> visit(N, vector<bool>(M, false));
    visit[start.first][start.second] = true;

    auto isOK = [&](ll x, ll y, ll time) {
        return (0 <= x && x < M && 0 <= y && y < N && c[y][x] != '#'
            && !visit[y][x]
            && (c[y][x] - '0') * pow(0.99, time) >= cost);
    };

    constexpr ll dx[4] = { 1, 0, -1, 0 };
    constexpr ll dy[4] = { 0, 1, 0, -1 };

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        for (ll i = 0; i < 4; i++) {
            ll nx = curr.x + dx[i];
            ll ny = curr.y + dy[i];
            ll nt = curr.time + 1;

            if (!isOK(nx, ny, nt)) {
                continue;
            }

            if (c[ny][nx] == 'g') {
                return true;
            }

            q.push({ nx, ny, nt });
            visit[ny][nx] = true;
        }
    }

    return false;
}

int main() {
    cin >> N >> M;
    c.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> c[i];
    }

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < M; j++) {
            if (c[i][j] == 's') {
                start = { i, j };
            } else if (c[i][j] == 'g') {
                goal = { i, j };
            }
        }
    }

    double ok = -1, ng = INT_MAX;
    for (ll i = 0; i < 100; i++) {
        double mid = (ok + ng) / 2;
        (canGoal(mid) ? ok = mid : ng = mid);
    }

    if (ok < 0) {
        cout << "-1" << endl;
    } else {
        printf("%.10f\n", ok);
    }
}

SRM504 Div1 Easy - MathContest

問題

　白か黒で塗られているボールが入ったスタックが与えられる。「上からボールを1個を取り出し、黒だったら残りのボールを全て色反転、白だったら残りのボールの順序を反転し、取り出したボールは捨てる」という操作を繰り返したとき、黒いボールを取り出す回数はいくらか。

解法

　制約が緩いのでシミュレーションする。順序反転や色反転は、どちらから見るかという方向やカウントするべき色を保持することでで行える。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

class MathContest {
public:
    int countBlack(string ballSequence, int repetitions) {
        string all;
        for (int i = 0; i < repetitions; i++) {
            all += ballSequence;
        }

        enum {
            FRONT, BACK
        };
        int pop_dir = FRONT;
        char count_color = 'B';

        int ans = 0;
        const auto size = all.size();
        for (int i = 0; i < size; i++) {
            auto pop_ball = (pop_dir == FRONT ? all.front() : all.back());
            (pop_dir == FRONT ? all.erase(0, 1) : all.erase(all.size() - 1));
            if (pop_ball == count_color) {
                ans++;
                count_color = (count_color == 'B' ? 'W' : 'B');
            } else {
                pop_dir = (pop_dir == FRONT ? BACK : FRONT);
            }
        }

        return ans;
    }
};

AtCoder Regular Contest 001 C - パズルのお手伝い

問題

　8クイーンパズルについて3つクイーンを置いた状況の盤面を与えるので、残り5つを制約を満たすように置けるならそのうち一つを出力せよ。

解法

　制約を満たすような置き方について全探索をする。各行、列、および右斜め左斜めのラインについてクイーンの数を記録していき、置けるところだけ考えてDFS。

反省

　特に詰まることもなく十数分でAC。ARCの3問目とは言っても難易度のバラつきは大きそう。

　全探索を真っ先に考えるという発想は基本なので大事。こういうサイズ感に慣れていればICPC2018のD問題とかもあっさり解けるのだろう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

struct State {
    vector<ll> col, raw, diag1, diag2;
    vector<pair<ll, ll>> queens;
};

State ans;

bool solve(State st) {
    if (st.queens.size() == 8) {
        ans = st;
        return true;
    }

    //可能な置き方を探る
    for (ll i = 0; i < 8; i++) {
        if (st.col[i] == 1) {
            continue;
        }
        for (ll j = 0; j < 8; j++) {
            if (st.raw[j] == 1) {
                continue;
            }
            if (st.diag1[i + j] == 0 && st.diag2[i - j + 7] == 0) {
                auto copy = st;
                //置ける
                copy.col[i]++;
                copy.raw[j]++;
                copy.diag1[i + j]++;
                copy.diag2[i - j + 7]++;
                copy.queens.emplace_back(i, j);
                if (solve(copy)) {
                    return true;
                }
            }
        }
    }

    return false;
}

int main() {
    vector<string> c(8);
    for (ll i = 0; i < 8; i++) {
        cin >> c[i];
    }

    State st;
    st.col.resize(8, 0);
    st.raw.resize(8, 0);
    st.diag1.resize(15, 0);
    st.diag2.resize(15, 0);
    for (ll i = 0; i < 8; i++) {
        for (ll j = 0; j < 8; j++) {
            if (c[i][j] == 'Q') {
                bool flag = true;
                if (++st.col[i] == 2) {
                    flag = false;
                }
                if (++st.raw[j] == 2) {
                    flag = false;
                }
                if (++st.diag1[i + j] == 2) {
                    flag = false;
                }
                if (++st.diag2[i - j + 7] == 2) {
                    flag = false;
                }
                if (!flag) {
                    cout << "No Answer" << endl;
                    return 0;
                }
                st.queens.emplace_back(i, j);
            }
        }
    }

    if (solve(st)) {
        vector<string> result(8, "........");
        for (auto q : ans.queens) {
            result[q.first][q.second] = 'Q';
        }
        for (ll i = 0; i < 8; i++) {
            cout << result[i] << endl;
        }
    } else {
        cout << "No Answer" << endl;
    }
}

KPPT型評価関数のボナンザメソッドによる学習

　第28回世界コンピュータ将棋選手権の時はKP,PPを用いた2駒関係を特徴量とするの評価関数を使用していたが、選手権後からKPPT型のオーソドックスな手番付き3駒関係を特徴量とする評価関数に変更した。

　学習をし直さないといけないため、まずは手始めにボナンザメソッドから始めることとした。使用した棋譜はfloodgate上にある2015年から2017年までの棋譜のうち、レートが両者2800以上のものかつ手数が50手以上のものとした。

　1周分を回した学習曲線は次のようになった。

　

　損失は下がり、一致率は上がっていることから上手く学習できていることがわかる。Apery(WCSC28)の評価パラメータを読み込んで同様の条件で損失、一致率を計算すると損失は120台中盤、一致率は38%ほどとなる。Apery(WCSC28)からするとレートの低いソフトの対局も含まれているため一致率などは不当に低くなっている可能性もあるが、目安としてこの程度まで高めることができるものと考えられる。

　学習させたものを1手1秒でWCSC28と対局させた結果が以下のようになる。

対局数	勝ち	引き分け	負け
2164	1272	42	850

　引き分けを0.5勝として勝率は約59.75%、Eloレート差にして68.6となった。

　探索部の改善も多少あるとはいえ、1周回しただけでWCSC28版を超える結果となりKPPTの優秀さが伺える。

　評価関数の形式を上位ソフトと揃えたためAperyややねうら王などの評価パラメータも読み込めるようになった。正確な検証はしていないが、これらのパラメータで対局を行うとWCSC28版に十数局の段階では無敗だったため、評価関数だけの伸びしろとしてもそこまではあると思われる。

AtCoder Grand Contest 026 B - rng_10s

問題

　を初期値として

• を引く
• 以下だったらを足す

　という操作を繰り返したとき以上で無限ループになるか判定せよ。

解法

　1時間考えてもわからなかったので解説PDFを読んだ。以下はそのまま。

　まずすぐわかる場合を省きにいく。なら初日で買えないのでfalse。ならどうあがいても減っていくのでfalse。なら全て無くなる前に必ず入荷が入り、先の条件からは仮定できるのでtrue。

　残りの場合について、個数の遷移をで見ていくと

• 最初は
• 購入では不変
• 入荷すると増える

　であり、これがを超えることがあるかどうかが判定結果。これの最大値はとしてであるため、これをと比較すればいい。

　最後の理屈は少しわかりにくいが、解説放送を観るとわかりやすいかもしれない。

反省

　tex:\mathrm{mod} \; Bで考えるという発想が出てこなかった。毎回は引かれるわけで、この操作で不変な量ということでに着目するというのはきっと普通のことなのだろう。ずっととの2通りの操作と考えてしまっていて、たいてい操作が複数あると難しい。

　しかしそこまでたどり着いたとしても正解が導ける自信はない。gcdを考えたりするのもある種の定跡なんだろうが、まだそこまでこの手の考え方には慣れていないと感じる。もっと鍛錬を積まなくては。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

bool solve(ll A, ll B, ll C, ll D) {
    if (B > A) {
        return false;
    } else if (B > D) {
        return false;
    } else if (C >= B) {
        return true;
    } else {
        ll g = gcd(B, D);
        return B - g + A % g <= C;
    }
}

int main() {
    ll T;
    cin >> T;
    vector<ll> A(T), B(T), C(T), D(T);
    for (ll i = 0; i < T; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    for (ll i = 0; i < T; i++) {
        cout << (solve(A[i], B[i], C[i], D[i]) ? "Yes" : "No") << endl;
    }
}

AtCoder Grand Contest 025 B - RGB Coloring

問題

　最初全て無色である個のブロックを赤緑青の3色で塗り分けることを考える。各ブロックがそれぞれ赤であれば点、緑であれば点、青であれば点、無色のままなら点として、個のブロックの合計得点がになる塗り方は何通りか求めよ。

解法

　解説PDFの通り。

　緑で塗られたブロックを赤と青で同時に塗られたと考えれば赤と青を独立にそれぞれ個、個塗る問題に帰着する。 $$ K = i A + j B $$

としてを全探索すればと求まるのでで解ける。

反省

　さすがにたった2か月前のコンテストということで解法を覚えてしまっていた。10分ほどでAC。コンテスト中は解けなかったわけだけど、なかなかこういう発想の転換ができてこない。緑の点数がということで露骨に怪しいとは思っていた記憶があるが、こうやって扱うと簡単に解けるんだなぁ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

constexpr ll MOD = 998244353;

vector<ll> fact, inv_fact;

ll combination(ll n, ll m) {
    return fact[n] * inv_fact[n - m] % MOD * inv_fact[m] % MOD;
}

ll POW(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m & 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }
    return result;
}

int main() {
    ll N, A, B, K;
    cin >> N >> A >> B >> K;

    //緑→紫として紫は赤と青が同時に塗られている場所とすると
    //N個のブロックから赤をi個,青をj個それぞれ独立に選んで色
    //を塗ることとして良い

    //fact, inv_factの準備
    fact.resize(N + 1, 1);
    inv_fact.resize(N + 1, 1);
    for (ll i = 2; i <= N; i++) {
        fact[i] = i * fact[i - 1] % MOD;
        inv_fact[i] = POW(fact[i], MOD - 2);
        assert(fact[i] * inv_fact[i] % MOD == 1);
    }

    ll ans = 0;
    for (ll i = 0; i <= N; i++) {
        if (i * A > K) {
            continue;
        }

        if ((K - i * A) % B == 0) {
            ll j = (K - i * A) / B;
            if (j > N) {
                continue;
            }
            ans += combination(N, i) * combination(N, j) % MOD;
            ans %= MOD;
        }
    }

    cout << ans << endl;
}

AtCoder Grand Contest 022 B - GCD Sequence

問題

　異なる正の整数の集合に対して、どのについてもとのその他の要素の和の最大公約数が1でないとき特別であるということとする。要素数の特別な集合であり、全ての要素の最大公約数が1であり、どの要素も30000以下であるものを求めよ。

解法

　1時間半ほど考えたがわからなかったので解説PDFを読んだ。

　が6の倍数であり、が全て2か3の倍数の倍数であれば特別となる。そして2と3を含むとき全要素の最大公約数が1となるため条件も満たされる。が2か3の倍数であることは、6で割ったあまりが0,2,3,4のどれかだということなので、30000までの正の整数の、つまり20000個は存在するため十分にある。

　2か3の倍数である整数を小さいほうから個取っていき、和を計算する。すでに6の倍数であればそのまま出力良いため、そうでない場合を考える。

　mod 6において0, 2, 3, 4, 0, 2, 3, 4 ... と取っていくため、和を6で割った余りとしてありえるのは0, 2, 5, 3, 3, 5, 2, 0, 0 ...であり、つまり0, 2, 3, 5の4通りである。

　余りが2の時は、取った整数列の中から6で割った余りが2であるものを一つ取り除き、6で割った余りが0であるものを一つ追加すればよい。ほかの場合も同様に一つ取り除いて一つ追加することで上手く和を6の倍数にできる。

　取り除くものが必ず取れるようにが小さいケースは特別に処理すれば、上記の操作によって解ける。

反省

　以前解説を読んだときのおぼろげな記憶により、30000という数字が重要であるということは思い出した。そしての制約との関係からおおよそ取れれば良いことには気づき、3の倍数の余りに着目してそのうち二つを取るなどということを考えていた。

　しばらくして"特別"となる条件のために偶奇性も考えたほうが良さそうとなり、6の倍数の余りが0, 2, 3, 4であるものに着目するところまでは気が付いた。しかしそれぞれの数を個,個,個,[tex;N - i - j - k]個と置いてループを回すと計算量が大きすぎる……というところでずっと詰まってしまった。和についても6の倍数になっているかどうかを考えるという方向に行っていないため、考察としては良くなかった。

　教訓としては、制約を見て割合を確認→余りに着目という感じだろうか。600点問題の中では結構難しいほうだと感じた。

コード

　かなり愚直に解説をコードに落としただけ。長いのでリンクで。