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

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

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

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

AtCoder Regular Contest 010 C - 積み上げパズル

問題

 m色のうちどれか1色で塗られているブロックがn個順番に落ちてくる。1個落ちてくるたびにそのブロックを山に積むか捨てるか選ぶことができ、最終的に山に積まれたブロックによって次のように点数を付ける。

  • 色ボーナス:色ごとに決められた点数が個数分与えられる
  • コンボボーナス:同じ色のブロックがx個続いて積まれる場合、定数Yに比例したY(x - 1)点与えられる
  • 全色ボーナス:m色全て存在する場合Z点与えられる

 点数を最大化せよ。

解法

 メモ化再帰で解く。状態を一意に定めるために必要な情報は

  • 今見ているブロックのインデックス(0からn-1まで)
  • 直前に積まれたブロックの色(m種類)
  • 今までに積まれたことのある色

 であり、最後のものはm色にそれぞれ1ビット与えて管理することにより2^{m}の種類となる。全体で計算量はO(nm2^{m})であり、間に合う。

 遷移は

  • 積む場合:色ボーナス + 直前が同じならコンボボーナス + 今回で全色達成したなら全色ボーナス
  • 積まない場合:そのまま

 というようにしていけばよい。

反省

 1時間14分でAC。最初はまずDPで必要な状態がきちんと考察できず時間が30分ほど溶かした。というのも、直前にある色が「何個」続いているかも状態に含まないといけないと勘違いしており、これだと状態の数が多くなりすぎて計算量的に間に合わないと思っていたのだった。

 わからないままにコードを書き出してみると直前に何個続いているかは保持しなくてよいことがわかり、そのまま書き出す。ここでスッと実装できていたら40分ほどでできていたのだろうが……。

 最初はメモ化再帰で書き始めたにも関わらず、書きやすいと勘違いしてforループによるDPに書き直したところサンプルさえ合わない状態に。全色ボーナスを毎回足していたり、全色達成しえないときにも足していたりと、forループでは面倒くさいと思い直してメモ化再帰を書き直してようやくAC。実装の方針がダメダメだった。

 全色ボーナスは最後に足すのでも問題なかったか。そこによって遷移中の方針が変わることはないか……どうか。

コード

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

ll n, m, Y, Z;
vector<ll> a;
vector<ll> p;
ll max_pow;

vector<vector<vector<ll>>> memo;

ll solve(ll i, ll pre, ll stacked) {
    if (i == n) {
        return 0;
    }

    if (pre!= -1 && memo[i][pre][stacked] != -1) {
        return memo[i][pre][stacked];
    }

    //積む
    ll score1 = p[a[i]];
    if (a[i] == pre) {
        //preと同じ色ならボーナス
        score1 += Y;
    }
    ll nstacked = stacked | (1LL << a[i]);
    if (stacked != max_pow - 1 && nstacked == max_pow - 1) {
        //今回で全色達成したならボーナス
        score1 += Z;
    }
    //次以降
    score1 += solve(i + 1, a[i], nstacked);

    //積まない
    ll score2 = solve(i + 1, pre, stacked);

    if (pre != -1) {
        memo[i][pre][stacked] = max(score1, score2);
    }

    return max(score1, score2);
}

int main() {
    cin >> n >> m >> Y >> Z;

    p.resize(m);
    a.resize(n);
    max_pow = 1LL << m;
    memo = vector<vector<vector<ll>>>(n, vector<vector<ll>>(m, vector<ll>(max_pow, -1)));

    vector<char> c(m);
    map<char, ll> color2num;
    for (ll i = 0; i < m; i++) {
        cin >> c[i] >> p[i];
        color2num[c[i]] = i;
    }

    string b;
    cin >> b;
    
    for (ll i = 0; i < n; i++) {
        a[i] = color2num[b[i]];
    }

    cout << solve(0, -1, 0) << endl;
}

SRM506 Div1 Easy - SlimeXSlimesCity

問題

 N個の街がありそれぞれには人口が定められている。

  • 2つの街を選んで人口の小さい方を大きい方へ統合する

 操作を街が1つになるまで繰り返したとき、最終的に残り得る街の数を求めよ。

解法

 人口が大きい順にソートして、人口が自分以下の街の人口の和が次に大きい人口を超えているかどうかを見えていけば良い。超えられなかったときそこまでで打ち切り。

反省

 AtCoder Grand Contest 011 B - Colorful Creaturesと全く同じなので悩む余地がなかった。その時より簡単な方針で書けたので経験が活きている。

コード

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

class SlimeXSlimesCity {
public:
    int merge(vector <int> population) {
        sort(population.begin(), population.end(), greater<int>());
        ll sum = accumulate(population.begin(), population.end(), (ll)0);

        int ans = 1;
        sum -= population[0];
        for (int i = 1; i < population.size(); i++) {
            if (sum < population[i - 1]) {
                break;
            }
            ans++;
            sum -= population[i];
        }

        return ans;
    }
};

AtCoder Regular Contest 009 C - 高橋君、24歳

問題

 N人のうちK人へ手紙を配り間違えたとき、あり得る配り方の組み合わせの数を求めよ。

解法

 まずN人の中から配り間違えたK人を選ぶ方法が{}_NC_{K}

 そしてK人に対して全て間違った配り方となる組み合わせの数は攪乱順列、あるいはモンモール問題などと言われるものであり、これは第n項目をa_{n}として$$a_n = (n - 1)(a_{n - 1} + a_{n - 2})$$という漸化式が成り立つ。

 これらを掛け合わせたものが答えとなる。

反省

 23分48秒でAC。K人について自分以外というのは有名問題のやつだなということに気が付き、式を考えるのが面倒だったので「プレゼント 自分以外 配り方」などとググってこれこれといったページを見てそのまま書いた。

 N自体が大きいのでMODを取る必要があったり、攪乱順列の組み合わせ数を求める際の配列を小さくとりすぎていたりで2WA。

コード

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

const ll MOD = 1777777777;

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

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

    return result;
}

ll combination(ll n, ll m) {
    ll result = 1;
    for (ll i = 1; i <= m; i++) {
        result *= (n - i + 1) % MOD;
        result %= MOD;
        result *= POW(i, MOD - 2);
        result %= MOD;
    }
    return result;
}

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> f(max(K + 1, (ll)4));
    f[2] = 1;
    f[3] = 2;
    for (ll i = 4; i <= K; i++) {
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % MOD;
    }
    cout << (combination(N, K) * f[K] % MOD) << endl;
}

AtCoder Regular Contest 008 C - THE☆たこ焼き祭り2012

問題

 あなたと参加者を足してN人の人がおり、あなたは持っているN個のたこ焼きを参加者に投げて配る必要がある。参加者もたこ焼きを投げることができ、参加者を経由して他の参加者にたこ焼きを配ることが可能である。各人は2次元座標上に散らばっており、たこ焼きを投げる速度の上限と受け取る速度の上限が決まっている。たこ焼きを全員に配りきるために必要な時間の最小値を求めよ。

解法

 i番目の人がj番目の人にたこ焼きを直接投げつける場合の最小コストは$$\frac{iからjへの距離}{\min\{iが投げる速度の上限,jが受け取る速度の上限\}}$$である。このような重み付きのエッジを持つグラフとして考えて、0番目の人からダイクストラ法を使えば各人への最短経路が求まる。1秒に1個しか投げられないという制約から、この最短経路をソートして小さいほうから N - 1, N - 2, \dots, 1を足したものの最小値が答えとなる。

反省

 22分36秒でAC。最初は1秒に1個しか投げられないという制約や、参加者を経由できるという点に戸惑ってすごく複雑な答えになるのではないかといろいろ考えていたが、13分ほどで結局ダイクストラ法やるだけというところに気づけた。気づいてからは特に詰まることもなく……とは言ってもやはり実装がちょっと遅いか。しかしダイクストラ法の書き方は固まってきたのでこれ以上速くできる気はしない。

 解法としては最短経路で投げる限り同じ人が同時に2個たこ焼きを持つことにはならないという点が重要なんだろうけど、感覚的にしか言えなくてはっきり証明しろと言われたら困ってしまう気がする。おそらくそのような場合がありうると最短性に矛盾ということになるんだな。

コード

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

int main() {
    ll N;
    cin >> N;

    vector<double> x(N), y(N), t(N), r(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> t[i] >> r[i];
    }

    //iからjに投げるときにかかる時間
    vector<vector<double>> connect(N, vector<double>(N));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            double distance = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
            double speed = min(t[i], r[j]);
            connect[i][j] = distance / speed;
        }
    }

    //ダイクストラ法
    vector<double> cost(N, INT_MAX);
    struct Element {
        double cost;
        ll curr;
        bool operator<(const Element& rhs) const {
            return cost > rhs.cost;
        }
    };

    priority_queue<Element> pq;

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

        for (ll i = 0; i < N; i++) {
            if (i == t.curr) {
                continue;
            }

            double new_cost = t.cost + connect[t.curr][i];
            if (new_cost < cost[i]) {
                cost[i] = new_cost;
                pq.push({ new_cost, i });
            }
        }
    }
    
    sort(cost.begin(), cost.end());
    for (ll i = 1; i < N - 1; i++) {
        cost[i] += N - 1 - i;
    }

    printf("%.10f\n", *max_element(cost.begin(), cost.end()));
}

AtCoder Regular Contest 007 C - 節約生活

問題

 テレビを点けた瞬間から数えて視聴可能なタイミングを'o'、不可能なタイミングを'x'で表す文字列が与えられる。同じテレビを複数用意し点けるタイミングをずらすことで、最後のテレビを点けて以降はどの瞬間もいずれかのテレビで視聴可能であるようにしたい。最低必要な台数を求めよ。

解法

 最大でもN個使えば視聴可能になる。点ける時刻は\mathrm{mod}\;Nで考えればいいので各N通り。二つ以上のテレビを同じ時刻で点ける意味はないことから、全探索しても計算量はO(N!)で済む。

反省

 33分でAC。解法自体はすぐにわかったが、その実装をどうすればいいのかに悩んでしまった。大きく分けると

  • 点ける時刻の組み合わせを列挙する方法
  • ある点ける時刻の組が条件を満たしているか判定する方法

 という2つの山があるように思う。前者は点ける時刻の配列を後ろから見ていき、N - 1未満だったらそこを+1して、そこから以降を前のもの+1したものにしていくという実装にした。順番を無視できるタイプの組み合わせを列挙する問題で何度か書いた経験があるがいまだに慣れず、書き出すのに抵抗を感じてしまう。

 後者はビット演算で実装した。点ける時刻分だけシフトしたパターンのorを取っていき、最終的に時刻N + 1から2Nまで全部ビットが立っているかを判定することでなんとかできた。

 パッと思いついた実装が面倒くさそうだったのでもうちょっと良さそうな実装を探りながら……という感じだったが結局あまり簡単にはできなかった。他の人の解法を考えると、ある時刻分ずらしたものを採用するかどうかを考えていけばO(2^{N})で解けたようだ。こういう考え方がなかなかできてこない。

コード

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

ll N;

bool next(vector<ll>& v) {
    for (ll i = v.size() - 1; i >= 0; i--) {
        if (v[i] >= (N - 1) - (v.size() - i)) {
            //これ以上増やせない
            continue;
        }

        //iを増やし、i以降を前のもの+1にする
        iota(v.begin() + i, v.end(), v[i] + 1);
        return true;
    }
    return false;
}

int main() {
    string c;
    cin >> c;

    N = c.size();

    ll bit = 0;
    for (ll i = 0; i < N; i++) {
        if (c[i] == 'o') {
            //2ループ分ビットを立てる
            bit ^= (1LL << i);
            bit ^= (1LL << i + N);
        }
    }

    //テレビを点けるのは[0, N)の間なので
    //[N, 2N)で全部ビットが立っていれば良い
    ll target = (((1 << N) - 1) << N);

    for (ll i = 1; i <= N; i++) {
        //i台で可能かを判定
        vector<ll> tv(i, 0);
        iota(tv.begin(), tv.end(), (ll)0);

        while (true) {
            ll all = 0;
            for (ll j = 0; j < i; j++) {
                all |= (bit << tv[j]);
            }

            if ((target & all) == target) {
                cout << i << endl;
                return 0;
            }

            if (!next(tv)) {
                break;
            }
        }
    }
}

SRM505 Div2 Medium - PerfectSequences

問題

 与えられた整数列の要素を1つ非負の整数へ変化させたとき、要素全ての和と積が一致するかを判定せよ。

解法

 要素数が1つの時はどう変えても一致するので2つ以上の場合について考える。

 i番目の要素をj = 0, 1, \dotsへと変化させることを考える。i番目以外の要素の和をs、積をpとしたとき$$j + s = jp$$となればよい。したがって

  • p = 0のとき、j + s = 0となることからs = 0かつ元のi番目の要素が0でなければ"Yes"
  • p = 1のとき、j + s = jとなることからs = 0であれば"Yes"
  • 上記以外のときjを小さい順に試していきj + s \lt jpとなったらi番目の要素を変化させることでは一致しない

 という判定をi = 1, 2, \dotsについてやれば求まる。制約が緩いので計算量も問題ない。

反省

 コーナーケースに突っ込みまくっていくらかWAを出した。ここに書いたくらい見通し良い解法に練り上げてからコードを書き始めないと大変なバグが生まれまくる。

 オーバーフローの判定も入れないと一度はPassedと表示されるが数秒後にFailedとも出てくる。よくわからないがおそらくFailedなんだろう。そういうのも含めて結構時間かかってしまったし本番でちゃんと解ける気は一切しない。

コード

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

class PerfectSequences {
public:
    string fixIt(vector <int> seq) {
        ll N = (ll)seq.size();
        if (N == 1) {
            return "Yes";
        }
        vector<ll> sum_others(N, 0), pro_others(N, 1);
        vector<bool> pro_big(N, false);
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                if (j == i) {
                    continue;
                }
                sum_others[j] += seq[i];
                pro_others[j] *= seq[i];
                if (pro_others[j] > 1e9 * 50) {
                    pro_big[j] = true;
                }
            }
        }
        for (ll i = 0; i < N; i++) {
            if (pro_others[i] == 0) {
                if (sum_others[i] == 0 && seq[i] != 0) {
                    return "Yes";
                }
                continue;
            } else if (pro_others[i] == 1) {
                if (sum_others[i] == 0) {
                    return "Yes";
                }
                continue;
            } else if (pro_big[i]) {
                continue;
            }
            for (ll j = 0; ; j++) {
                if (j == seq[i]) {
                    continue;
                }
                ll sum = sum_others[i] + j;
                ll pro = pro_others[i] * j;
                if (sum == pro) {
                    return "Yes";
                } else if (sum < pro) {
                    break;
                }
            }
        }
        return "No";
    }
};