Mister雑記

競プロやります。

Codeforces Round #488 (Div2)

ABC100が終わって3時間後に行われたCodeforces。 いい子はとっくに寝てる時間ですが、大学生の特権と言わんばかりの夜更かしで参戦しました。

教訓としては、「眠気がある状態でコンテストは参加するもんじゃない1。 個人的に初めて大きくレートを落としたコンテストになってしまいましたが、Dまでの解説はします。

(例によって幾分見やすいHackMD版のリンクも貼って置きます。今回は数式も少ないので大差ないかも。)

目次

A. Fingerprints (指紋)

問題リンク

概要

あなたの目の前にはテンキー式のロックが掛かったドアがあり、手元にはその暗証番号を部分列(連続でなくてよい)として含む数列が書かれた紙がある。

さらにテンキーの一部には指紋がついている。指紋がついた数字は必ず暗証番号に使われており、暗証番号はそのようなものの中で最長のものであることが分かっている。

このとき、暗証番号を正しい順番に出力せよ。

解説

紙の数列を順番に見ていって、暗証番号とマッチしたら出力するだけ。 制約が非常に小さいので毎回全探索で十分間に合う。

回答例

int main() {
    int N, M;
    cin >> N >> M;
    
    V<int> pap(N), fin(M);
    // paperとfinger

    REP(i, N) {
        cin >> pap[i];
    }
    REP(j, M) {
        cin >> fin[j];
    }

    REP(i, N) {
        REP(j, M) {
            if (pap[i] == fin[j]) {
                cout << pap[i] << " ";
                break;
            }
        }
    }
    cout << endl;
    return 0;
}

B. Knights of a Polygonal Table (多角形卓の騎士)

問題リンク

概要

騎士たちの強さがpi、所持金がciで与えられる。

騎士たちは他の騎士を殺すことで相手の所持金を手にすることができるが、自分より真に弱い(pが真に小さい)騎士しか殺せない。

さらに良心の呵責から、各騎士は高々k人しか他の騎士を殺すことはできない。

このとき、各騎士について他の騎士を殺した後に所持しうる最大金額を出力せよ。

解説

ずいぶんと物騒な問題文だが、お察しの通り「円卓の騎士」がモチーフになっている。私は円卓の騎士の元ネタを知らないのでなんとも言えないが。

それはさておき、やるべきことを簡潔にまとめると以下の通り。

  1. 騎士のデータを強さについて昇順になるようソートする。
  2. 弱い騎士から順に以下の操作を行う。
    1. 自分の1つ前の騎士の所持金を配列(coinとする)に挿れて降順ソート。
    2. coinの長さがkになるまでpop_back()する。
    3. coinの総和を答えとして記録。

今回はkの制約が小さい(k ≦ 10)ので、毎回ソートしても十分間に合う。

ただし上はあくまでも「強さが互いに固有(distinct)である」場合の方法であり、実際は「同じ強さの騎士が来たら一旦配列(stockとする)に記録して、真に強い騎士がきたらstockを全部coinに突っ込む」みたいな処理が必要になる。

回答例

int main() {
    int N, K;
    cin >> N >> K;
    
    V<P<P<int, int>, int>> data(N);
    // ((p, c), id)
    // idは入力時の順番を記録する

    REP(i, N) {
        data[i].snd = i;
        cin >> data[i].fst.fst;
    }
    REP(i, N) {
        cin >> data[i].fst.snd;
    }

    SORT(data);
    // pについて昇順ソート

    V<ll> coin, stock;
    V<ll> ans(N, 0);

    ans[data[0].snd] = data[0].fst.snd;
    // 一番弱い騎士は誰も殺せないので所持金=答え

    NREP(i, N - 1) {
        stock.push_back(data[i - 1].fst.snd);
        // 1つ前の騎士のcを一旦stockに入れる
        
        // 強さが同じ場合はstockに残ったまま
        if (data[i].fst.fst > data[i - 1].fst.fst) {
        
            // stockの中身を全部coinに移す
            while (!stock.empty()) {
                coin.push_back(stock.back());
                stock.pop_back();
            }
        }

        // coinを降順ソートし、長さがK以下になるまで末尾を消す
        GSORT(coin);
        while (SIZE(coin) > K) {
            coin.pop_back();
        }

        ll v = data[i].fst.snd;
        for (ll c : coin) {
            v += c;
        }

        ans[data[i].snd] = v;
    }

    REP(i, N) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

下手な実装をすると絶対バグる、Codeforces恒例の実装系問題。

私は苦手なタイプの問題だが、今回は幸いにもバグらなかった。 大分慣れてきた感じがある。

C. Two Squares (2つの正方形)

問題リンク

概要

座標軸に平行な辺を持つ正方形Aと、座標軸と45度に交わる辺を持つ正方形Bが与えられる。

正方形の辺上も内部として扱うとき、AとBが共有部分を持つか判定せよ。

解説(未完)

問題自体は至って簡潔なのだが、考えてみると結構難しい。

まず、1つでも頂点が一方の正方形内部にある場合は明らかにYES。

Bの頂点がAの内部にあるかはgridの探索でもよくやる境界判定で簡単に出来るのだが、問題はもう一方。 これは幾何問題ではたまに出てくるテクニック「座標回転」(造語)を行えば上手くいく。

座標回転というのは「(X, Y) = (x - y, x + y)という座標変換を行うことで、(X, Y)は元のグラフを45度時計回りに回転させて原点中心に拡大したものになる」というテクニック。回転行列を使えば簡単に証明できる。

これを適用することで、Bが座標軸に直交するようになって先の境界判定をそのまま使えるようになる。

解説(完全)

しかし、未完とあったように先の方針では漏れがある。それが以下のようなケース2

f:id:misteer:20180617142717p:plain

これを網羅する方針で間違えたために、私はサーバージャッジで落とされた。悲しい。

ではどうすればこのようなケースを網羅できるかというと、答えは意外と簡単で「一方の中心が他方に含まれているか」を調べるだけ。 解説見て「たったそんだけでいいのか......」と嘆くなどした。

回答例

int main() {
    V<int> x1(4), y1(4), x2(4), y2(4);

    ll xmin = 1000, xmax = -1000, ymin = 1000, ymax = -1000;
    // 境界判定用のやつ(工夫すれば多分要らない)

    REP(i, 4) {
        cin >> x1[i] >> y1[i];
        xmin = min(xmin, x1[i]);
        xmax = max(xmax, x1[i]);
        ymin = min(ymin, y1[i]);
        ymax = max(ymax, y1[i]);
    }

    REP(j, 4) {
        cin >> x2[j] >> y2[j];

        // 頂点がAに入っているか判定
        if (xmin <= x2[j] && x2[j] <= xmax && ymin <= y2[j] && y2[j] <= ymax) {
            cout << "YES" << endl;
            return 0;
        }
    }
    
    // Bの中心がAに入っているか判定
    if (xmin * 2 <= x2[0] + x2[2] && x2[0] + x2[2] <= xmax * 2 && ymin * 2 <= y2[0] + y2[2] && y2[0] + y2[2] <= ymax * 2) {
            cout << "YES" << endl;
            return 0;    
    }
    
    xmin = 1000, xmax = -1000, ymin = 1000, ymax = -1000;
    // 境界判定の変数を再び初期化
    
    REP(j, 4) {
        // ここで座標回転をする
        ll x = x2[j], y = y2[j];
        x2[j] = x - y;
        y2[j] = x + y;
        xmin = min(xmin, x2[j]);
        xmax = max(xmax, x2[j]);
        ymin = min(ymin, y2[j]);
        ymax = max(ymax, y2[j]);
    }

    REP(i, 4) {
        ll x = x1[i], y = y1[i];
        x1[i] = x - y;
        y1[i] = x + y;

        // 頂点がBに入っているか判定
        if (xmin <= x1[i] && x1[i] <= xmax && ymin <= y1[i] && y1[i] <= ymax) {
            cout << "YES" << endl;
            return 0;
        }
    }
    
    // Aの中心がBに入っているか判定
    if (xmin * 2 <= x1[0] + x1[2] && x1[0] + x1[2] <= xmax * 2 && ymin * 2 <= y1[0] + y1[2] && y1[0] + y1[2] <= ymax * 2) {
            cout << "YES" << endl;
            return 0;    
    }

    cout << "NO" << endl;
    return 0;
}

残念ながら不正解だったが、経験は得られた。 今度AtCoderにでも類題出ないかな。

あと上のコードが汚いのはなんとかならないのか。

D. Open Communication (公開通信)

問題リンク

概要

2人が1~9の数からなるペアを1つずつ持っており、2つのペアには1つだけ共通の数が含まれている。

2人は自分のペアは知っているが相手のペアは知らない。この状況下で以下のような通信を交互に1回ずつ行い、共通の数を当てることが目標となる。

  • 一方がもう一方へ1~9の数からなるペアをいくつか伝える。
  • ペアは異なる数字から成り、かつ同じものを含んではならない。
  • 伝えるペアの中には自分が持つペアが必ず含まれていなければならない。

三者であるあなたもこの通信だけを見て、2人と同様に共通の数を当てることが目標となる。

やり取りされた情報が与えられるので、

  • 共通の数が分かればその数
  • 共通の数は分からないが、どんなケースでも2人とも共通の数が分かっているなら0
  • 共通の数は分からず、1人でも共通の数が分かっていないケースがあれば-1

を出力せよ。

My方針

一目すると「何言ってんだこいつ」って感じの問題。 要は論理パズルみたいなもので、眠気で支配された頭には堪えた。

ざっくりと私の方針を説明すると、

  1. どちらか一方の視点に立ち、「もし自分がこのペアを持っているなら」と仮定する。
  2. 相手についても「もし相手がこのペアを持っているなら」と全パターン仮定し、以下のように可能性を模索する。

    • もしもペアの要素が2つとも違うor同じなら、相手がそのペアを持つ可能性はないのでスルー
    • もしペアの要素が1つだけ一致するなら、その一致する数が「共通の数」となる可能性があるのでset(posとする)に突っ込む
  3. 相手について全パターン模索し終わった時点で、posの要素数

    • 0なら、自分がこのペアを持つことはないのでスルー。
    • 1なら、その要素が共通の数としてあり得るのでset(ansとする)に突っ込む。
    • 2なら、自分がそのペアを持っているケースについて自分は共通の数が分からないので、-1を出力して終わり
  4. 以上を自分の伝えた全ペアに対して行った後、ansの要素数

    • 0になることは条件から絶対にない。
    • 1ならそれが唯一「共通の数」になりうる数なので、それを出力。
    • 2以上なら、どのケースでも本人は「共通の数」を1つに絞れているはずなのに自分は分からないということで0を出力。

これをそのまま実装してなんとかpretestまでは通ったのだが、案の定サーバーテストで落とされる始末。

ちなみに一方からの視点だけから見ていたのがまずかった模様。 ちゃんと両者の視点に立って考えてれば合ってたと思うと悲しいね。

提出コード

int main() {
    int N, M;
    cin >> N >> M;

    V<P<int, int>> A(N), B(M);
    REP(i, N) {
        ll a, b;
        cin >> a >> b;
        A[i] = make_pair(a, b);
    }
    REP(i, M) {
        ll a, b;
        cin >> a >> b;
        B[i] = make_pair(a, b);
    }

    set<int> ans;
    // Aの視点に立ったとき、「共通の数」として考えうる数全てを記録
    
    REP(i, N) {
        set<int> pos;
        // AがA[i]を持っていると仮定した場合、「共通の数」として考えうる数を記録
        REP(j, M) {
            REP(_, 2) {
                swap(B[j].fst, B[j].snd);
                
                if ((A[i].fst == B[j].fst) == (A[i].snd == B[j].snd)) {
                    // ペアの共通要素数が0か2なので、
                    // 相手がB[j]をもつことはない
                    continue;
                }

                if (A[i].fst == B[j].fst) {
                    pos.insert(A[i].fst);
                } else {
                    pos.insert(A[i].snd);
                }
            }
        }

        // 1つも「共通の数」として考えうる数がない
        // = AがA[i]を持つ可能性はない
        if (pos.empty()) continue;
        
        if (SIZE(pos) == 1) {
            auto itr = pos.begin();
            ans.insert(*itr);
            
        } else {
            // 2つとも「共通の数」として考えうる
            // = AがA[i]を持つ場合、Aは「共通の数」を判別できない
            cout << -1 << endl;
            return 0;
        }
    }

    if (SIZE(ans) == 1) {
        // Aがどのペアを持っていようと、
        // 全ケースについて「共通の数」は同じ
        auto itr = ans.begin();
        cout << *itr << endl;

    } else {
        // Aはどのケースでも「共通の数」を1つに絞れるが、
        // 私からはどのケースが正しいのか分からない
        cout << 0 << endl;
    }
    return 0;
}

コメントを書いてて「私がやっているのはプログラミングではなく論理学なのでは?」と思い始めた。説明がとても難しい......。

感想

A,Bは順調だったんだが、C,Dの全ケースに対応しきれず死亡。やはりコーナーケースを考える練習が足りてないなぁと実感した。

特にこどふぉは最後までコーナーケースがあるかどうかも分からないコンテスト形式なので、その能力は今後の大きな課題になりそう。

f:id:misteer:20180617142606p:plain

結果は上の通り。紫から一歩遠ざかってしまった。

f:id:misteer:20180617142635p:plain

今月は上の通りなんかいっぱいコンテストがあるっぽいので、巻き返すチャンスはある。 しかし時間帯...。次回からは十分に仮眠をとることを心がけよう。


  1. 眠気がなかったら解けていたかというと、そうでもない気はする。

  2. この図はCSAのAppで簡単に作れます。geometry_widget