hogecoder

tsutaj 競技プログラミングの記録

Codeforces Round #527 Div.3 D1 / D2: Great Vova Wall

Codeforces 要考察

問題概要

原文 (D1) → Problem - D1 - Codeforces
原文 (D2) → Problem - D2 - Codeforces

長さ N の数列が与えられる。以下の操作を繰り返し行うことによって、全要素の値を等しくしたい。

  • D1 で認められる操作
    • 値が同じである隣り合う要素を選び、その両方に対し 1 加算
    • ある要素を選び、それに対し 2 加算
  • D2 で認められる操作
    • 値が同じである隣り合う要素を選び、その両方に対し 1 加算

解説

D1

単一要素に対して 2 加算できることから、値の偶奇が等しいものは値も等しいとみなしてよいです。つまり、与えられた数列を 0 と 1 のみからなる数列に直すことができます。

このように直した数列に対し、全要素の値を等しくできるかを考えましょう。これは stack を利用することで効率的に処理できます。括弧の対応を取るときと同じように、stack の top にある値と追加したい値が等しい場合は pop し、そうでなければ push することを繰り返し、最終的に得られた stack の size が 1 以下であれば条件を満たせます。

この正当性を簡単に述べます。まず 0 と 1 のみからなる数列に対して「単一要素に 2 加算」の操作は必要ありません。つまり「値が等しい隣り合う要素両方に 1 加算」のみを考えれば良いです。この操作を考える際、同じ parity を持つ区間の長さの偶奇*1が重要になります。この区間長が偶数である場合、うまく操作することで区間全体の parity を変えることもできますし、変えないこともできます。つまり、他の区間の状況に応じて parity を自由に変えることができるので、この区間は元からなかったかのように無視しても構いません。区間長が奇数である場合も、1 つを残して他は全て 0 または 1 に変更可能です。つまり、区間長 \bmod 2 を考えれば良いことになります。全体の偶奇を揃えることが目的なので、最終的に何も区間が残らないか、区間がただ 1 つ残る場合に元々の条件を満たせます。この操作は、上で書いたように stack に対する操作で簡潔に表現できます。

D2

D1 とは異なり、単一要素に対して 2 加算することが許されていません。つまり、D1 のように偶奇の戦略を使うことができなくなります。

しかし、この場合でも stack を使うことで効率的に処理できます。stack の top にある値と追加したい値が等しい場合は pop し、そうでない場合について top にある値未満である場合に push、そうでなければその時点で条件を満たしません。

top と値が等しい場合についての操作の正当性は先ほどと同様です。では top と値が異なる場合はなぜこれでうまく動くのでしょうか？

  • top にある値未満である場合
    • stack に残っている要素は、括弧の対応で言うところの開き括弧の状態に対応します。stack に残っている要素を閉じる前に、それよりも小さい要素が来てしまったという状況です。この場合新たに追加した値を閉じることができれば、それに対して一様に加算することで元々 stack にあった要素も閉じられる可能性があります。よって stack に値を追加して操作を続ければ良いです。
  • top にある値を超える場合
    • stack に残っている要素を閉じる前に、それよりも大きい要素が来てしまったという状況です。全要素の値を揃えるためには stack に残る要素に対して操作を行う必要があるのですが、閉じられていないため操作を行うことができません。よって、この時点で条件を満たせなくなります。

最終的に判定する際も若干の注意が必要です。数列に対して繰り返し操作をし終えた際に、各要素の値がいくつになっているか考えます。これは明らかに元の数列の最大値 M になります。このことを考慮すると、最後に得られる stack の状態として許容されるものは、中身が空であるか、 M だけが残っている状態のみです。

ソースコード

D1

signed main() {
    int N; scanf("%lld", &N);

    stack<int> st;
    for(int i=0; i<N; i++) {
        int val; scanf("%lld", &val);
        val %= 2;

        if(st.size()) {
            int t = st.top();
            if(t == val) st.pop();
            else st.push(val);
        }
        else st.push(val);
    }

    cout << (st.size() > 1 ? "NO" : "YES") << endl;
    return 0;
}

D2

signed main() {
    int N; scanf("%lld", &N);

    stack<int> st;
    int ma = -INF;
    for(int i=0; i<N; i++) {
        int val; scanf("%lld", &val);
        ma = max(ma, val);

        if(st.size() and st.top() == val) st.pop();
        else if(st.empty() or st.top() > val) st.push(val);
        else {
            puts("NO");
            return 0;
        }
    }

    bool ok = st.empty() or st.top() == ma;
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

*1:数列が [0, 0, 1, 1, 1, 0] であった場合、[偶数長の '0', 奇数長の '1', 奇数長の '0'] というように、parity が等しいものが連続する数の偶奇を考える、ということです

Codeforces Round #527 Div.3 C: Prefixes and Suffixes

Codeforces 文字列

問題概要

原文 → Problem - C - Codeforces

n 文字の文字列 s があり、あなたは s が全体としてどのような文字列であるかは知らない。しかし、長さが 1 から n-1 までの全ての prefix と suffix についての情報は持っている (ただし、どれが prefix でどれが suffix かはわからない)

与えられるそれぞれの文字列について、その文字列が prefix であるか suffix であるかに分類せよ。そのような割当が複数あるならばどれか 1 つを答えればよい。

解説

長さ n-1 の文字列の情報がふたつあり、これを X, Y とします。これらの情報から s 全体が何であるかはある程度推測できます。具体的には、 (X, Y) = (prefix, suffix) の場合と、 (Y, X) = (prefix, suffix) の 2 パターンです。

全体の文字列が推測できたので、あとは条件に合うような割当ができれば良いです。これは check(s, k, assim) のようなメソッドを作ることで実現できます。文字列全体が s と推測されているときに、次に処理すべきものが長さ k の prefix 及び suffix であり、その時の割当が assim である、という意味です。 一見 TLE しそうなのですが、条件を満たさないときに探索をしないなど枝刈りをすると高速に動くようです。落ちるケースあったら教えてください。

また、multiset などでどの文字列がいくつあるかを数えながら割当を行う方法もあるようです。Writer による解説はその方針でやっています。

ソースコード

int N;
string par[210], NIL = "Z";

string check(string s, int k, string assim) {
    if(k == 0) return assim;
    
    int idxX = -1, idxY = -1;
    for(int i=0; i<2*N-2; i++) {
        if(par[i].length() != k) continue;
        if(idxX < 0) idxX = i;
        else         idxY = i;
    }

    if(s.substr(0, k) == par[idxX] and s.substr(N-k) == par[idxY]) {
        assim[idxX] = 'P'; assim[idxY] = 'S';
        string res = check(s, k-1, assim);
        if(res != NIL) return res;
        assim[idxX] = assim[idxY] = 'X';
    }
    if(s.substr(0, k) == par[idxY] and s.substr(N-k) == par[idxX]) {
        assim[idxY] = 'P'; assim[idxX] = 'S';
        string res = check(s, k-1, assim);
        if(res != NIL) return res;
        assim[idxX] = assim[idxY] = 'X';
    }
    return NIL;
}

signed main() {
    cin >> N;

    string X = "", Y = "";
    int idxX = -1, idxY = -1;
    for(int i=0; i<2*N-2; i++) {
        cin >> par[i];
        if(par[i].length() == N-1) {
            if(X == "") X = par[i], idxX = i;
            else        Y = par[i], idxY = i;
        }
    }
    
    if(Y.substr(1, N-2) == X.substr(0, N-2)) {
        string cand = Y[0] + X;
        string assim(2*N-2, 'X');
        assim[idxY] = 'P', assim[idxX] = 'S';

        string res = check(cand, N-2, assim);
        if(res != NIL) {
            cout << res << endl;
            return 0;
        }
    }
    if(X.substr(1, N-2) == Y.substr(0, N-2)) {
        string cand = X[0] + Y;
        string assim(2*N-2, 'X');
        assim[idxX] = 'P', assim[idxY] = 'S';

        string res = check(cand, N-2, assim);
        if(res != NIL) {
            cout << res << endl;
            return 0;
        }
    }
    return 0;
}

ACM-ICPC 2018 Asia Yokohama Regional Contest 参加記

ICPC 大会参加記

コンテストからだいぶ日が開いてしまいましたが、参加記を書きます。

ACM-ICPC 2018 Asia Yokohama Regional Contest に参加しました。昨年と同様に four-t として参加しました。また、同じ大学からチーム Megido も参加しました。

0 日目 (前日の移動)

本当はこの日のうちに東京に到着して明日からの日程に備える、はずでした・・・

あれ？？？

雪がひどくて、乗るはずだった飛行機が飛ばない。一緒に空港に来ていたえび君の飛行機も飛ぶかどうかあやしい。これ大丈夫なのか・・・？

結局自分は、この日は函館まで移動して、翌朝新幹線で移動することにしました。ちなみにえび 君と TAB 君は深夜に着いたそうです。お疲れ様です・・・

函館に行ったら ｼﾝﾔｶﾄｰ さんとエンカしました。適当にネカフェを見つけて就寝。

1 日目 (Registration とか Practice とか)

起床成功。前日に予約した新幹線に乗り込みます。席が全然空いていなくてグランクラスしか取れなかったので、乗ってみました。財布さん・・・

想像していたよりもはるかに豪華でした。ハイクラスの旅をする方や、移動手段に困っている方はぜひご検討ください。

そんなこんなで、なんとか Registration に間に合いました。

Practice は去年とだいたい同じように進みました。えび君がサンプルケースを全部チェックしてくれるようなスクリプトを用意してくれていたので、とても助かりました。

その後チーム紹介をしました。翌日はここに書いてある 4 つの T を大事にして頑張りたいという気持ちになりました。

宿に戻りしばらくすると、前日欠航になったため翌日の便に振り替えていたコーチの tsukasa_diary さんが到着！これで four-t 全員集合！！！

記念 (？) に中華を食べました。えび君がえびを共食いしていた

ABC があったんですが解いた後眠すぎてすぐ寝ました。

2 日目 (コンテスト本番)

朝の集合が早いけど起床成功。コンテスト前の時間はマスコットであそんで過ごした。

そしてコンテスト開始。えび君が A を、自分が B を、TAB 君が C を見ることに。A は実装するも WA が出るようでつらそう。B は map でやれば O(N^{2} \log N) だし行けるなと思って書いたけど TLE (は？) C はすぐ通ったらしい。はいプロ

少々詰まりながらも A も AC。B はとりあえず違う人が実装したらいいかもねということで交代して、結局 3 人とも実装するが TLE しか出ない。どうなってるんや・・・。

なんか G が解かれているので読んでみる。しばらくすると左に寄せる場合と右に寄せる場合の min を取れば良いことに気づき。実装してみる。こちらは一発で通った、うれしいね。

その後他の問題もいくつか見ながら B を実装するも TLE しか出ない。どうなってるんや・・・。

K がそこそこ解かれていたので考えてみる。いろいろ考えてみた結果、その時点で取っても破綻しない最大のものを選び続ければ良さそうだが、TLE しそう。二分探索できそうではあるけど B のせいで O(N^{2} \log N) が全く信用できない (想定解はこの計算量らしい、どうなってるんや・・・)。

しばらくいじってると B が通る。結局計算量的には変わらないがメモ化してサボるところはサボるのと、map を回避すればよかったらしい。うーん・・・

K を最後に通そうとするも時間切れ。このへんは実力不足を感じますね。明らかに動きとして悪かったものの、去年よりは良いかなあという結果になりました。

順位は 60 チーム中 31 位で、中央値だったため 株式会社オプト さんから企業賞をいただきました。ありがとうございました！

懇親会で懇親していたらいつの間にか肉がなくなっていました。悲しい。

その後は北大勢で打ち上げ。青島ビールおいしかった。

3 日目 (企業見学)

株式会社 bitFlyer さんと Indeed Tokyo さんと LINE 株式会社 さんの企業見学がありました。見学の内容を喋ってよいかどうかがわからないのでマスコットの癒し画像をもって記事を締めたいと思います。

↑これは bitFlyer で昼食を食べた時の写真で、

↑これは企業見学後に競プロ er でサイゼリヤに行った時の写真です。マスコットはいいぞ。

余談

ICPC の翌日に海外出張があったのですが、帰りの飛行機で遅延が発生し乗り継ぎができずに足止めされました。飛行機運がない・・・

総括

去年よりはまともに戦えたので、少し安心しました。とはいえ理想的な戦い方には程遠いので、もっとチーム練習を重ねて上を目指したいなあと思いました。

弊学で今年 ICPC に出たメンバーの大半は引退せず来年も参加できるため、来年も 2 チーム通過を目指してサークル全体で頑張って行きたいですね。