2018-08-25

AtCoder Regular Contest 018 C - 席替え

問題

　 $N$ 行 $M$ 列の長方形状に並べられた机に対して生徒が一人ずつ座っている。 $i$ 行目 $j$ 列目にいる生徒の成績を $G[i][j]$ としたとき、 $a \gt c$ ならば $G[a][b] \ge G[c][d]$ となるようにしたい。そのような席替えのうち、生徒の移動距離(マンハッタン距離)が最小になるものについてその最小値を求めよ。

解法

　まず各成績の人が何行目に来なければならないかを計算する。そして全員をその行に移動させてから、列が被っていれば被らないように横に振り分けることで目的の並び方が達成される。

　前半の操作について、 $a$ が $p$ で割り切れないとき $p \ge N \times M$ より同じ成績の人は発生しない。したがって出現した成績を一つのvectorに押し込んでソートしてそのインデックスを $M$ で割れば、ある成績の人が何行目へ行かなければならないかが求まる。

　後半の操作は各行について、列を順番に見ていって $j$ 列目までには $j$ 人いないといけないなので、累積和とのずれを計算するとちょうと移動させる量が求まる。

　 $a$ が $p$ で割り切れるときは同じ成績の人が発生しうる。 $x$ が $p$ より小さければ全員同じ成績なので答えは0。大きければ先頭の人だけ成績が大きいので、その人を一番後ろの人と交換するため $2(N - 1)$ が答えとなる。

反省

　1時間12分(6WA)でAC。40分ほどでコーナーケース以外の方針はわかったが、最後の10ケースが間違ってしまう理由がわからずかなり苦しんだ。てっきり成績は一意に定まると思い込んでいたが、 $a$ が $p$ で割り切れる場合があったのを失念していた。そして割り切れる場合も全て答えは0となるわけではないというところにも引っかかった。

　 $p$ で割ったものが成績となると明示的に問題文には書かれていないが、乱数生成といったらそれが常識なんだろうか。一番最初だけmodをとらないというのも罠で、かなりひっかけポイントが多い問題だったように感じる。

　後半の各行に対する操作は、厳密な証明はできないが感覚的にそんな感じで求まるんじゃないかと試してみたら答えが合っていたというものだった。これも典型問題だろうか。解説等を見ると行についても再度ソートしてどこへ行くかを計算すればよいだけだった。もっと簡単に考えなければ。

AtCoder Regular Contest 017 C - 無駄なものが嫌いな人

競技プログラミング

問題

　整数 $w_1, \dots, w_N$ と $X$ が与えられるので、総和が $X$ となるような選び方が何通りあるか求めよ。

解法

　半分全列挙。 $N$ 個の数字のうち前半について組み合わせを全て列挙してそれぞれの和を配列に確保しソートする。後半についても組み合わせを列挙して和を求め、 $X$ に足りない分を先ほど求めた配列の中から二分探索で探す。計算量は $O(\lceil \frac{N}{2} \rceil 2^{\lfloor \frac{N}{2} \rfloor})$ かな？正確さはともかく間に合う。

反省

　8分8秒でAC。パッと見で解法が浮かんだし実装も一発でできた。特に問題なし。

SRM508 Div1 Easy - DivideAndShift

競技プログラミング

問題

　 $N$ 個の箱が順番に並んでおり、左から $M$ 個目に目的のものが入っている。開けられる箱は一番左のものだけであり、箱の列に対しては次の操作が行える。

$N$ 以下の素数 $p$ について、 $M$ を $M % (N / p)$ 、 $N$ を $N / p$ で置き換える。
箱全体を $N$ 右か左に一つずらす。両端はループしているとする。

　上のいずれかの操作を繰り返し、目的にものを一番左に持っていく最小の操作回数を求めよ。

解法

　最終的に割る数が決まっているとき、割る操作を全て先に行い、シフトは最後にまとめて行えばよい。したがって $N$ を素因数分解して何回素因数で割るかを計算し、そこで得られた新しい $n, m$ についてシフトによる操作の必要数を求めていけば良い。

コード

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

class DivideAndShift {
public:
    int getLeast(int N, int M) {
        M--;
        auto fact = getFactor(N);
        vector<ll> num(fact.size(), 0);
        auto update = [&]() {
            for (ll i = fact.size() - 1; i >= 0; i--) {
                if (num[i] != fact[i].second) {
                    num[i]++;
                    for (ll j = i + 1; j < fact.size(); j++) {
                        num[j] = 0;
                    }
                    return true;
                }
            }
            return false;
        };

        ll ans = INT_MAX;
        while (true) {
            ll p = 1;
            ll op_num = 0;
            for (ll i = 0; i < num.size(); i++) {
                p *= pow(fact[i].first, num[i]);
                op_num += num[i];
            }

            ll curr_n = N / p;
            ll curr_m = M % curr_n;

            ans = min(ans, curr_m + op_num);
            ans = min(ans, curr_n - curr_m + op_num);

            if (!update()) {
                break;
            }
        }

        return ans;
    }
private:
    vector<pair<ll, ll>> getFactor(int N) {
        vector<pair<ll, ll>> fact;
        for (ll i = 2; i <= (ll)N; i++) {
            if (!isPrime(i)) {
                continue;
            }
            ll num = 0;
            while (N % i == 0) {
                N /= i;
                num++;
            }
            if (num) {
                fact.push_back({ i, num });
            }
        }
        return fact;
    }
    bool isPrime(ll n) {
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
};

2018-08-23

SRM504.5 Div1 Easy - TheNumbersWithLuckyLastDigit

競技プログラミング

問題

　1の位が4か7である整数を複数使えるとき和が $n$ となるようにできるか判定し、できる場合はその最小の個数を求めよ。

解法

　10の位以降の調整は自由にできるので1の位を $n$ に揃えるのに必要な最小個数を求め、それでできる数より $n$ が大きければ大丈夫。

反省

　もっときれいに書けたかもしれないが全部手打ちした。

コード

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

class TheNumbersWithLuckyLastDigit {
public:
    int find(int n) {
        if (n == 0) {
            return 0;
        }

        switch (n % 10) {
        case 0:
            return (n >= 20 ? 5 : -1);
        case 1:
            return (n >= 11 ? 2 : -1);
        case 2:
            return (n >= 12 ? 3 : -1);
        case 3:
            return (n >= 23 ? 5 : -1);
        case 4:
            return 1;
        case 5:
            return (n >= 15 ? 3 : -1);
        case 6:
            return (n >= 16 ? 4 : -1);
        case 7:
            return 1;
        case 8:
            return 2;
        case 9:
            return (n >= 19 ? 4 : -1);
        }
    }
};

2018-08-23

AtCoder Regular Contest 016 C - ソーシャルゲーム

競技プログラミング

問題

　アイドル $N$ 人を集めるために $M$ 種類のガシャを回すことを考える。それぞれのガシャは一回に一人のアイドルを排出する。各ガシャについて確率分布と回すためにかかる金額が与えられるとき、全てのアイドルを入手することについて最適な戦略の下での必要な金額の期待値を求めよ。

解法

　bitDPで後ろから求める。クリエイティヴなヴログに詳しく書かれていて、自分もこれを読んで理解できたので参照のこと。

反省

　1時間35分でAC。部分点を順番に取りに行ったが、40点のところで根本的に自分の考えていた期待値の式が間違っていたことに気づく。40点を得るのにかかったのが48分ほどで、そこからようやくコンプガチャ形式の部分点について考え始めたがわからず、開始から1時間ほど経ったので解説などを見る。しかし解説スライドはよくわからなくて、上に貼った記事を読んでやっと理解できた。かなり難しい気がする。

　確率系のDPは本当に苦手でさっぱりできない。基本的にDPができない。

　遷移できるかどうか、そして遷移できる中での確率、という二段構えで考えるのが肝心なところだったようだ。正直DPでやるという考えにすらたどり着いていないので、まだこういう考え方の習得には時間がかかりそう。

　しかし $N \le 2$ という部分点問題がかなりヒントになっているはずで、それを解いた時にDP的な考え方をしているにも関わらず次で拡張していけないのが本当にひどい。

AtCoder Regular Contest 015 C - 変わった単位

競技プログラミング

問題

　いくつかの単位換算表を与えるので最も大きい単位を最も小さい単位で表したときの関係を示せ。

解法

　ある単位から見ての他の単位の大きさを深さ優先探索で求めて、一番大きいものと一番小さいものを出力する。

反省

　2時間ほどでAC。最初はワーシャルフロイド法でやれると思ったが、小さいほうから大きいほうへ遷移する可能性を考えていなくてWA。結局1時間ほどたってしまったので解説や他の人のブログなどを読んで上の解法に行き着いたが、 $N = 1$ の場合でバグるコードを書いてしまいそれでずっとハマっていた。その原因に気づくまでに1時間くらいかかりこんな時間に。とてもつらかった……。

　解法としては野田さんのブログをほぼ写した感じで終わり。DFSをスタックで書いた経験が少なくて結構戸惑ってしまった。いつも再帰関数で書いているが、むしろこうやってデータ構造使う方が本筋という気もするし、書こうと思ったときにパッと書けないのはひどい。もっと精進せねば。

AtCoder Regular Contest 014 C - 魂の還る場所

競技プログラミング

問題

　円筒の左右から赤緑青の3色のいずれかで塗られているボールを入れていく。ボールは同じ色のボールと接触すると消えるという性質を持つ。左右どちらから入れるかは任意であり、ボールを入れる順番だけが与えられるとき、最終的に円筒内に残る最小のボール数を求めよ。

解法

　枝刈り全探索。消せるときは消したほうがいいので、dequeのfrontとbackを見て同じ色があったら消す。なかったら右からと左から2通り試す。

　非公式解説PDFを見たところ、1手先読みを行わなければTLEとなると書いてあるが、僕はメモ化による高速化でACとなった。また別解として各色のボールを2で割った余りの和が答えとなるらしい。おそらくそれが想定解なのだろう。

反省

　50分9秒でAC。パッと見では半分全列挙が頭に浮かび、それに囚われた考察をしていた。25分ごろに枝刈り全探索でそこそこいけるんじゃないかと思って書き始めるがTLE。メモ化をすれば間に合いそうだと考えて実装したところ、一つのケースだけがMLEとなった。MLEは珍しいし、一つのケースだけということもあって、想定解なのかどうかが迷うところだった。

　いろいろ試行錯誤した結果、最終的にはメモ化をする際のmapのキーをtuple<int i, deque<char>>からちょっと加工してstringに変えるとACとなった。メモリの使用効率が異なるのだろうか……？

　試しに

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

int main() {
    string s = "1RGBRGBRGBRGBRGB";
    deque<char> dq;
    for (ll i = 1; i < s.size(); i++) {
        dq.push_back(s[i]);
    }
    auto t = make_tuple((ll)1, dq);

    cout << sizeof(s) << endl;
    cout << sizeof(t) << endl;
}

　というコードを試したみたところ、出力は40 48だった。確かにstringにした方がわずかに消費量は小さい？しかしこのsのRGBという文字を増やしてもメモリ使用量は変わらないためsizeofが何を評価しているのかよくわからない。またAtCoderでの結果を見ると、メモリ使用量が大きいところではstringにした方が1/5ほどになっている。C++の理解が浅すぎて何が起こっているのかさっぱりわからない……。

　またusing ll = long longと定義してある部分をusing ll = intとしてもメモリ使用量は全く変わらなかった。using ll = int16_tとしても変わらなかったが、理由がわからない。少ししか変わらないとかならわかるが、まったく変わらないものなのだろうか。

　メモ化するときにこうやって適用にmapに詰め込んでしまえーというのをよくやるので、メモリ使用量の変化は理解しておきたいところなんだけど……。

コード

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

ll N;
string S;
map<string, pair<bool, ll>> memo;

ll solve(ll i, deque<char> dq) {
    if (i == N) {
        return dq.size();
    }

    string key;
    key += to_string(i);
    for (char c : dq) {
        key += c;
    }

    if (memo[key].first) {
        return memo[key].second;
    }
    memo[key].first = true;

    char curr = S[i];
    ll ans = 50;
    if (dq.size() == 0) {
        dq.push_back(curr);
        ans = min(ans, solve(i + 1, dq));
    } else if (dq.front() == curr) {
        //先頭に入れる(結果消える)
        dq.pop_front();
        ans = min(ans, solve(i + 1, dq));
    } else if (dq.back() == curr) {
        //末尾に入れる(結果消える)
        dq.pop_back();
        ans = min(ans, solve(i + 1, dq));
    } else {
        //2通り試す
        auto dq1 = dq;
        dq1.push_front(curr);
        ans = min(ans, solve(i + 1, dq1));

        auto dq2 = dq;
        dq2.push_back(curr);
        ll ans2 = solve(i + 1, dq2);
        ans = min(ans, solve(i + 1, dq2));
    }

    return memo[key].second = ans;
}

int main() {
    cin >> N >> S;
    cout << solve(0, deque<char>()) << endl;
}

2018-08-20

AtCoder Regular Contest 013 C - 笑いをとれるかな？

競技プログラミング

問題

　直方体の豆腐が複数用意される。各豆腐の中には1つ以上のハバネロが埋め込まれており、二人のプレイヤーがハバネロを避けながら豆腐をいずれかの面に平行な平面で切断していく。豆腐の個数、サイズ、ハバネロの位置を与えるので、どちらのプレイヤーも最善を尽くしたとき勝つ方を求めよ。

解法

　ある面に平行な切断の操作は他の面に平行な成分に対して影響を及ぼさないため、豆腐1個につき6個の山があるNimゲームに帰着できる。各豆腐に対してハバネロをすべて含む最小の直方体を求め、その周囲にある豆腐の厚みについてそれぞれxorを取っていけば答えが求まる。

反省

　1時間考えてもわからなかったので他人の提出やブログ等を読んだ。最終的には1時間6分でAC。

　全てのハバネロを含む最小の直方体を求め、それら周囲にある豆腐の厚みを考えるところまでは行っていたが、Nimというものを今まで書いたことがなかったのでそれに帰着させようと思えなかった。アドホックな考察として「2以上の厚みは全て同じとして扱える」と勘違いし、厚みが「0,1,または2以上」の三パターンで分けられると思ってそれらの数をカウントして、1である個数が奇数であるか、2以上である個数が奇数であるかを判定すれば良いとして提出したが、かなり多くのケースがWAとなり完全に行き詰ってしまった。

　Nimの答えを知ったあとで実験してみると、たとえば豆腐が一つとして、ハバネロの周囲6面の厚みが「0,0,0,0,2,3」のようなときに間違うことがわかった。当然だが2以上は全て同じなどということはなく、それぞれの数を別に考えなければならない。

　Nimというかgrundy numberについての理解が浅いため解けなかったという典型の問題だと感じる。Nimって取れるコインの枚数に制約があると思っていたが、そうではないらしい。この問題はまさにNimなんだな。grundy数を習得したかったを読んで多少わかったような、しかしまだ応用はできなさそうな、という感じ。

コード

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

int main() {
    ll N;
    cin >> N;
    vector<ll> X(N), Y(N), Z(N);
    vector<vector<ll>> x(N), y(N), z(N);
    for (ll i = 0; i < N; i++) {
        cin >> X[i] >> Y[i] >> Z[i];
        ll M;
        cin >> M;
        x[i].resize(M);
        y[i].resize(M);
        z[i].resize(M);
        for (ll j = 0; j < M; j++) {
            cin >> x[i][j] >> y[i][j] >> z[i][j];
        }
    }

    //各豆腐についてハバネロを囲う最小の立方体を求める
    //そして、その周りの豆腐の厚みがどれだけあるか

    ll grundy = 0;
    for (ll i = 0; i < N; i++) {
        vector<vector<ll>> habanero(3, vector<ll>(2));
        for (ll j = 0; j < 3; j++) {
            habanero[j][0] = INT_MAX;
            habanero[j][1] = INT_MIN;
        }

        for (ll j = 0; j < x[i].size(); j++) {
            habanero[0][0] = min(habanero[0][0], x[i][j]);
            habanero[0][1] = max(habanero[0][1], x[i][j]);
            habanero[1][0] = min(habanero[1][0], y[i][j]);
            habanero[1][1] = max(habanero[1][1], y[i][j]);
            habanero[2][0] = min(habanero[2][0], z[i][j]);
            habanero[2][1] = max(habanero[2][1], z[i][j]);
        }

        grundy ^= habanero[0][0];
        grundy ^= X[i] - 1 - habanero[0][1];
        grundy ^= habanero[1][0];
        grundy ^= Y[i] - 1 - habanero[1][1];
        grundy ^= habanero[2][0];
        grundy ^= Z[i] - 1 - habanero[2][1];
    }

    cout << (grundy ? "WIN" : "LOSE") << endl;
}

2018-08-19

AtCoder Regular Contest 012 C - 五目並べチェッカー

競技プログラミング

問題

　19×19の碁盤の状態を与えるので五目並べの盤面として正常かどうかを判定せよ。

解法

　盤面について先手後手それぞれが勝っているか(五目並んでいるか)を判定する関数を用意する。まず与えられた局面で先手後手それぞれについて勝っているかを判定し、次のように場合分けをする。

先手後手両方とも勝っている

　正常でない

先手後手両方とも勝っていない

　石の数が正常であるか確認するだけで良い

どちらかが勝っている

　勝っている方が最終手を着手し、最終手を着手する前はどちらも勝っていない状態であったはずである。したがって盤上にある勝った側の任意の石を一つ取り除いた盤面のうち、どれか一つはまだ勝ってない状況でなければならない。それを判定すればよい。

反省

　37分53秒でAC。最初は五目以上並んでいる成分の個数を数えればいいのかなどと思っていたが、交差する点に打って同時に2個以上五目が作れる場合があるのでこれは断念。いくらか考えたところでこの最終手を一手戻すという発想が出てきた。

　サイズが小さいのでどのようにしても解けそうな反面、実装が楽で場合分けが少ないようなものを考えないとバグが多くなりそうなので診療に考えなくてはならない問題だと感じた。

　問題とは関係のない話だけど、コンピュータ将棋でもこうやって個々の要素を問題化していったら最初の入り口として良いのではないかとか話されていた気がしますね。あれ？これはテスト駆動開発みたいなものか？

コード

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

bool isWin(vector<string> b, char c) {
    //cが勝っているかをチェック
    ll dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
    ll dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };

    auto isOK = [&](ll i, ll j, char c) {
        return (0 <= i && i < 19 && 0 <= j && j < 19 && b[i][j] == c);
    };

    for (ll i = 0; i < 19; i++) {
        for (ll j = 0; j < 19; j++) {
            if (b[i][j] != c) {
                continue;
            }
            for (ll k = 0; k < 8; k++) {
                ll num = 0;
                for (ll ni = i, nj = j; isOK(ni, nj, c); ni = ni + dy[k], nj = nj + dx[k]) {
                    num++;
                }

                if (num >= 5) {
                    return true;
                }
            }
        }
    }

    return false;
}

bool solve(vector<string> b) {
    //石の数のチェック
    vector<ll> all_num(2, 0);
    for (ll i = 0; i < 19; i++) {
        for (ll j = 0; j < 19; j++) {
            if (b[i][j] == 'o') {
                all_num[0]++;
            } else if (b[i][j] == 'x') {
                all_num[1]++;
            }
        }
    }

    vector<bool> win(2, false);
    win[0] = isWin(b, 'o');
    win[1] = isWin(b, 'x');

    if (win[0] && win[1]) {
        //両方勝っていたらおかしい
        return false;
    } else if (win[0]) {
        //先手勝ち
        //先手が打った瞬間でないといけないので
        if (all_num[0] != all_num[1] + 1) {
            return false;
        }

        //最後に打った石を除いてみてすでに勝っていたらおかしい
        for (ll i = 0; i < 19; i++) {
            for (ll j = 0; j < 19; j++) {
                if (b[i][j] == 'o') {
                    //ここが最終手と仮定する
                    //1手戻す
                    b[i][j] = '.';

                    //判定
                    if (!isWin(b, 'o')) {
                        return true;
                    }

                    //盤の状態を戻す
                    b[i][j] = 'o';
                }
            }
        }
        return false;
    } else if (win[1]) {
        //後手勝ち
        //後手が打った瞬間でないといけないので
        if (all_num[0] != all_num[1]) {
            return false;
        }

        //最後に打った石を除いてすでに勝っていたらおかしい
        for (ll i = 0; i < 19; i++) {
            for (ll j = 0; j < 19; j++) {
                if (b[i][j] == 'x') {
                    //ここが最終手と仮定する
                    //1手戻す
                    b[i][j] = '.';

                    //判定
                    if (!isWin(b, 'x')) {
                        return true;
                    }

                    //盤の状態を戻す
                    b[i][j] = 'x';
                }
            }
        }
        return false;
    } else {
        //勝敗はついていないので数だけ
        return (all_num[0] == all_num[1] || all_num[0] == all_num[1] + 1);
    }
}

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

    cout << (solve(b) ? "YES" : "NO") << endl;
}

2018-08-18

AtCoder Regular Contest 011 C - ダブレット

競技プログラミング

問題

　小文字からなる英単語を変換していく遊びを考える。可能な変換は単語内の1文字を別の文字へと変える操作のみであり、最初の単語と最後の単語、そして経由可能な単語のリストを与えるので最小の変換回数での変換とその過程を示せ。

解法

　リストの重複を削除し、最初と最後の単語を挿入して、最初の単語を始点とした経路復元付きダイクストラ法を行う。

反省

　19分27秒でAC。10分で考察して10分で実装という感じ。そこまで突っかかる要素もなかったわりには時間がかかっている気がする。

　それにしても昔のARCはちょっと簡単めですね。

コード

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

int main() {
    string first, last;
    ll N;
    cin >> first >> last >> N;
    if (first == last) {
        cout << 0 << endl;
        cout << first << endl;
        cout << last << endl;
        return 0;
    }

    vector<string> s(N);
    for (ll i = 0; i < N; i++) {
        cin >> s[i];
    }

    //重複とfirst, lastを除去
    sort(s.begin(), s.end());
    unique(s.begin(), s.end());
    for (auto itr = s.begin(); itr != s.end(); itr++) {
        if (*itr == first || *itr == last) {
            itr = s.erase(itr);
        }
    }

    //先頭にfirstとlastを挿入
    s.insert(s.begin(), { first, last });

    //Nが変化している可能性があるので取り直す
    N = s.size();

    //隣接リストを構築
    vector<vector<ll>> connect(N);
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            //ハミング距離が1であるか判定
            ll num = 0;
            for (ll k = 0; k < (ll)s[i].size(); k++) {
                if (s[i][k] != s[j][k]) {
                    num++;
                }
            }
            if (num == 1) {
                connect[i].push_back(j);
                connect[j].push_back(i);
            }
        }
    }

    //経路復元付きダイクストラ法
    vector<ll> cost(N, INT_MAX), pre(N, -1);
    struct Element {
        ll cost;
        ll curr;
        //priority_queueでコストの小さいものから出すために
        //普通とは逆の向きで不等号を定義する
        bool operator<(const Element& rhs) const {
            return cost > rhs.cost;
        }
    };

    priority_queue<Element> pq;
    cost[0] = 0;
    pq.push({ 0, 0 });
    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();

        ll new_cost = t.cost + 1;
        for (ll next : connect[t.curr]) {
            if (new_cost < cost[next]) {
                cost[next] = new_cost;
                pre[next] = t.curr;
                pq.push({ new_cost, next });
            }
        }
    }

    //cost[1]がlastへのコスト
    if (cost[1] == INT_MAX) {
        cout << -1 << endl;
    } else {
        //過程の単語数はその-1
        cout << cost[1] - 1 << endl;
        vector<string> ans;
        for (ll i = 1; pre[i] != -1; i = pre[i]) {
            ans.push_back(s[i]);
        }
        ans.push_back(first);
        reverse(ans.begin(), ans.end());
        for (auto str : ans) {
            cout << str << endl;
        }
    }
}