Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

Codeforces Round #492 (Div.1)

初のDiv.1コンテスト。渡る世間はプロばかり。

コンテストリンク

本記事のHackMD版はこちら

目次

A. Tesla (※自動車会社名)

問題リンク

概要?

スライドパズルの要領で駐車場に車を入れよう!

解説

概要が雑だが気になる人は本文を読んでほしい。ここで説明する分量ではない。

本番で思いついたのが以下のようなアルゴリズムで、Editorialもこれと全く同じ解法だった。

  1. 駐車場に接している車は入れてしまう。
  2. 車を全部反時計回りに移動させる(キャタピラの要領)。
  3. 1に戻り、全ての車が入ったら終わる。

2の時点で車が移動できない、つまり K = 2Nで全ての車が駐車場に隣接していない場合だけ-1と出力すればよい。 そうでない場合、各車は多くても1周=2Nしか移動しないので、制約から最悪でも10000回程度の移動で終わる。

と、言うのは簡単だが実装がアホみたいに重い。特に実装が難しいのが

  • ループが回しにくい
  • 2で適当に1周回してしまうと車が衝突してしまう可能性があり、空きマスから移動させなければならない

の2点。最初はループを4分割して管理性最悪の継ぎ接ぎコードを書いていたが、結局バグに対処しきれずうんざり。

こういったコードを書いているときは、すぐに書くのを中断してもっと効率的な書き方を考えるのが大切。実際、そのあと「ループを配列にしちゃえばいいじゃーん」ってことに気づいて全部書き直したら、コード量は格段に減ったし一発で通った。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
template <typename T, typename U>
using P = pair<T, U>;

#define fst first
#define snd second
#define pb push_back
#define mp make_pair

#define SIZE(v) (LL((v).size()))

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

int main() {
    int N, K;
    cin >> N >> K;
    V<V<int>> place(5, V<int>(N + 1));
    // 1-indexedで記録
    NREP(i, 4) {
        NREP(j, N) {
            cin >> place[i][j];
        }
    }

    V<P<int, P<int, int>>> ans;
    // 手順を記録 (id, (c, r))
    
    V<P<int, int>> loop(N * 2 + 1);
    // ループの回る順番を記録する配列
    
    REP(i, N) {
        loop[i] = mp(2, i + 1);
        loop[i + N] = mp(3, N - i);
    }
    loop[N * 2] = loop[0];
    // [(2,1),(2,2), ... ,(2,N),
    //  (3,N),(3,N-1), ... ,(3,1),(2,1)]

    while (true) {
        bool finish = true;

        // 1. 格納できる車を格納
        NREP(j, N) {
            if (place[1][j] > 0 && place[1][j] == place[2][j]) {
                ans.pb(mp(place[2][j], mp(1, j)));
                place[2][j] = 0;
            } else if (place[2][j] > 0) {
                finish = false;
            }
        }

        NREP(j, N) {
            if (place[4][j] > 0 && place[4][j] == place[3][j]) {
                ans.pb(mp(place[3][j], mp(4, j)));
                place[3][j] = 0;
            } else if (place[3][j] > 0) {
                finish = false;
            }
        }
        // 上のコードは1,2行目と,3,4行目で2つに分けているが、
        // place[i][j] == place[i^1][j]的な方法もある

        if (finish) break;
        // 全部格納できたら終了、出力へ

        // 2. 車を反時計回りにローテーション
        // まずは空きマスを探す
        int begin = -1;
        REP(i, N * 2) {
            auto p = loop[i];
            if (place[p.fst][p.snd] == 0) {
                begin = i;
                break;
            }
        }

        // 空きマスがない->車が移動できないので不可能
        if (begin < 0) {
            cout << -1 << endl;
            return 0;
        }
        
        // 次いで手順を記録する
        // 空きマスを始点として、時計周りに1周見ていく
        FOR(i, begin, 2 * N) {
            auto p = loop[i + 1];
            if (place[p.fst][p.snd] > 0) {
                ans.pb(mp(place[p.fst][p.snd], loop[i]));
            }
        }

        REP(i, begin) {
            auto p = loop[i + 1];
            if (place[p.fst][p.snd] > 0) {
                ans.pb(mp(place[p.fst][p.snd], loop[i]));
            }
        }
        
        // それから実際に移動する
        // 移動自体は空きマスとかガン無視でいい
        // リアルタイム更新みたいな破壊的な方法は、やめようね!
        V<V<int>> to = place;
        REP(i, N * 2) {
            auto p = loop[i], sp = loop[i + 1];
            to[p.fst][p.snd] = place[sp.fst][sp.snd];
        }
        place = to;
    }

    // 最後に手順を出力
    cout << SIZE(ans) << endl;
    for (auto p : ans) {
        cout << p.fst << " " << p.snd.fst << " " << p.snd.snd << endl;
    }

    return 0;
}

メインパートがコメント抜きでも約80行、これは重い。

実際この問題は点数の割に重すぎるため、どう考えても飛ばすのが正解。この問題に50分くらい掛けてしまったために、10分で解けるB問題の点数が下がったのが悔やまれる1。問題の識別眼がまだまだ鍛えられてないなぁと実感した。実践経験不足だろうか。

B. Suit and Tie2 (集合写真)

問題リンク

概要

 1 \sim Nがそれぞれ2個ずつ入った長さ 2Nの配列がある。 隣り合う要素を何度かswapして同じ数字が隣り合うようにするとき、最小のswap回数を求めよ。

制約

  •  1 \leq N \leq 100

解説

先程「10分で解ける」と言ったが、実際AtCoderでも300点くらいの問題である。というのも、貪欲に頭の要素からペアを作るだけで事が済む。 下手に真ん中の方からペアを作ると、そのペアをまたぐように分かれているペアについて、操作数が2増えてしまうことからも分かるだろう。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;

#define pb push_back

#define SIZE(v) (LL((v).size()))

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
// Usual REP runs from 0 to n-1
// Natural REP runs from 1 to n

/* ---------- ここまでマクロ ---------- */

int main() {
    ll N;
    cin >> N;
    V<ll> A(2 * N);
    REP(i, N * 2) {
        cin >> A[i];
    }

    ll ans = 0;
    // 総swap回数
    
    while (!A.empty()) {
        NREP(i, N * 2 - 1) {
            if (A[i] == A[0]) {
                // swap回数は転倒数、ここでは移動距離と同じ
                ans += i - 1;
            }
        }

        V<ll> tmp;
        // A[0]以外の要素を順番通りに抽出
        // 下手にeraseとか使うとバグりそうなのでやめといた
        REP(i, N * 2) {
            if (A[i] != A[0]) {
                tmp.pb(A[i]);
            }
        }
        A = tmp;
        N--;
    }

    cout << ans << endl;
    return 0;
}

私が本番中に解けたのはこの2問まで。

C. Leaving the Bar (千鳥足)

問題リンク

概要

N個の二次元ベクトル \vec{v_i}が与えられる。

Allenは最初原点にいて、各ベクトルについて \vec{v_i} -\vec{v_i}だけ移動する。言い換えるなら、最終的に

 \displaystyle{
\vec{p} = \sum_i c_i \vec{v_i} \hspace{2ex} (c_i = \pm 1)
}

にいることになる。このとき、 | \vec{p} | \leq 1.5 \times 10^{6}を満たすように各 c_iを決めよ。 ちなみに、以下の制約下では条件を満たす c_iのパターンが必ず存在する。

制約

  •  1 \leq N \leq 10^{5}
  •  |\vec{v_i}| \leq 10^{6}

解法

最初「ノルムが大きい順にソートして、絶対値ができるだけ小さくなるように c_iを決める」という脳筋解法をぶん投げたら案の定通らなかった。その時点ではAがまだ解けてなかったので即諦めたが、気になってEditorialを見たら中々に面白い解法だった。

Editorial解法の肝は

3つのベクトルについて、そのノルムの最大値を rとする。 このとき、3つから適切に2つのベクトルを選ぶと、その和差でノルムが r以下になるものが必ず存在する。

という定理。正三角形を思い浮かべるとなんとなく分かるのだが、詳しくはEditorialを見ていただきたい。

これをN個のベクトルに順番に適用すると、制約から最終的にノルムが 10^{6}以下の2つのベクトルが残る。これらの和差のノルムの最小値は高々 \sqrt{2} \times 10^{6}なので、条件を満たすようにできる。

上の定理は大学入試でも出てきそうな感じはある。幾何問題難しいね。

回答例?

Coming soon...

D. Game (ゲーム)

問題リンク

概要

関数 f: (0, 1)^{N} \rightarrow \mathbb{R} (N桁のbit列に実数を対応させるような関数)がある。

AllenとBessieはランダムに決められた順番でN桁からなるbit列の各桁の値を決めていき、最終的に得られたbit列を xとして f(x)を最終的なスコアとする。

Allenはスコアを最大化するように、Bessieはスコアを最小化するようにするとき、スコアの期待値を求めよ。

ちなみにこの問題は fの一部が変わる r回のクエリ制になっている。

制約

  •  1 \leq N \leq 18
  •  0 \leq f(x) \leq 10^{9}
  •  0 \leq r \leq 2^{18}

解法

ゲーム系かと思ったら点数がバラバラだし、順番はランダムだしでなんかよく分からない問題。無論 2^{N}の全順番を試していては余裕でTLEだし、実装方法もよく分からない。

まぁ答えを言ってしまうと、期待値は

 \displaystyle{
\frac{1}{2^{N}} \times \sum_{x=0}^{2^{N}-1} f(x)
}

つまり  fの平均で出せてしまう。えぇ...。

Editorialでの説明はだいたい以下の通り:

 x番目のbitを tにしたときのスコアの期待値を v_{x, t}とおく。このとき、 \frac{v_{x,0}+v_{x,1}}{2} = \mathbb{E}(f)が成り立つ。

さて、最初がAllenの番だったとする。このときAllenは v_{x, t}が最大となるような x, tについて操作を行うことになる。

このとき、 v_{x,1 - t} = 2 \mathbb{E}(f) - v_{x,t}より v_{x, 1-t} vの最小値となる。よって最初がBessieの番である場合、Bessieは {x, 1-t}について操作を行うことになる。

したがってスコアの期待値は \frac{v_{x,t}+v_{x,1 - t}}{2} = \mathbb{E}(f)となる。

なんか分かるような分からないような...。確率論難しいね。

回答例

using namespace std;

template <typename T>
using V = vector<T>;
#define DOUBLE(n) static_cast<double>(n)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
// Usual REP runs from 0 to n-1

#define fcout cout << fixed << setprecision(10)

/* ---------- ここまでマクロ ---------- */

int main() {
    ll N, R;
    cin >> N >> R;
    ll sum = 0;
    V<ll> A(1 << N);
    REP(i, 1 << N) {
        cin >> A[i];
        sum += A[i];
    }

    fcout << DOUBLE(sum) / (1 << N) << endl;

    // ここからクエリ
    REP(i, R) {
        ll z, g;
        cin >> z >> g;
        sum -= A[z];
        A[z] = g;
        sum += g;
        fcout << DOUBLE(sum) / (1 << N) << endl;
    }

    return 0;
}

感想

なんか最近、問題の難易度を見極める力が試されている気がする。しかし私の実力で解けるのはA,Bだけ(運がよければDも)だったし、Aの実装が遅かった時点でまぁ実力もそんなもんなんだろうか。

結果はこんな感じ。ラッキーセブン。でもレートは2下がった。

初のDiv1コンテストだったが、早くもDiv2への郷愁の念に駆られている。しかし私は決してくじけない。


  1. 覆水盆に返らずとは言うが、もし最初に解いてればもう100点は稼げていた。それでもAが遅すぎて20位くらいしか変わんないけど。

  2. タイトルの「Suit and Tie」は直訳すると「スーツとネクタイ」だが、慣用句的に「格調高い」という意味があるらしい。