hogecoder

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

TTPC 2019 参加記

AtCoder その他コンテスト 大会参加記

2019/8/31 に開催された 東京工業大学プログラミングコンテスト に参加しました。

前日まで

某社に行ったり五等分の花嫁展に行ったり中本を食べたりした。

TTPC たのしみ〜

当日

コンテスト前

ホテルを出てしばらく虚無をしてた。

そのあとこれに行ってました。

リステアニメ、地味にチェックしていて、自分は本城香澄派です (聞いてない)

コンテスト中

ferin, oshibori, tsutaj の 3 人でチームを組んだ。olphe はオンライン参加だしチーム名 olphe_konaiphe にしようぜ (なぜ？？) という謎の流れでチーム名決定。

コンテスト開始、最初に読む問題を分担して取り組んでいった。B を ferin さんが書いて AC、その後に A も oshibori さんが AC、C は軽く方針の確認をして大丈夫そうだったので、その方針で書こうとなった。

A, B を書いてもらっている間に D を読んでいた。なんか遷移がかなり限定されているなぁ、ということに気づいて、ferin さんにお気持ちを伝えて C を実装して AC。

D はそのまま ferin さんにバトンタッチして書いてもらって AC。

E は構築らしい。チームメイトみんなで考えてみる。しばらくすると「偶数むりじゃない？」「奇数だったら swap すればいけない？」ということがわかってきた。ということで書いてみる。可能なときに Yes を出してなくて 1WA、競技プログラミングがへた

F は最初わからなくて、わりと考えた。DP の大筋を ferin さんが組み立ててくれて、合流は高々 1 回しか起こらないこととかを適当に指摘してた。コーナーに何度かやられたけど結局 AC できた。

H は平衡二分探索木があればいけるらしい、と oshibori さんに教えてもらった。平衡二分探索木はありますか？ありますね。書きたいですか？いいえ・・・。一旦放置することに

G はなんか解けそう。oshibori さんと考察をはじめる。

停滞してきたので H を ferin さんに実装してもらうことに。しばらくしたら AC していた (すごい)

G は任意 mod NTT あれば解けそうな気がしてきた。絶対想定解じゃないな・・・。とりあえず書いてみることに。考察がいくつかミスっていて少しずつ直していった。

G をずっとやっていると ferin さんが M 解けそうとのこと。交代しながら実装する。しばらくすると AC していた (すごすぎ)

終盤で G が半分 AC する (偶数だけ解けた)、奇数はなんかバグっていてつらい。そのままコンテストが終わってしまった・・・。

あとで気づいたんですが K = 0 のときに死んでいました。大戦犯

懇親会

ピザと寿司を同じ皿に並べるという夢みたいなことをしてた。

解説をひととおりきいた。復習しなきゃ・・・

懇親会ではじめましての人なんにんかと話せたので良かった。また会うことありましたらよろしくです。

翌日

リアル脱出ゲームをした。初めてやったけどめっちゃ楽しかった。その後に遊ぶ流れあったけど札幌に帰らなければならなかったのが残念・・・

その日の夜に行われた ABC でレートが 1 下がりました。

総括

TTPC たのしかった〜

AtCoder Grand Contest 030 F: Permutation and Minimum

AtCoder 動的計画法 数え上げ

問題概要

日本語があるので原文参照 → F - Permutation and Minimum

解説

A_{2i} と A_{2i + 1} の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態としてありえるものは以下の 3 通りである。

  • 2 つとも値が確定している (入力の段階で B の値がどうなるか分かる)
  • 1 つだけ値が確定している
  • なにも値が確定していない

今回はブロック内の値の最小値が数列 B の値となるので、値の大きいものから確定させていく (値が 2 個未満入っているブロックに対して値を追加) ことを考える。動的計画法で処理しよう。

ここで、はじめに与えられる数列 A で登場しなかった要素 v それぞれについて、最後に生成される B に登場するかどうかで場合分けして考える。

  • B で登場しない場合
    • v は、 A で登場しなかった B で登場した v 未満の要素とペアを組むか、 A で登場してなおかつ 1 つだけ値が確定しているブロックに属している v 未満の要素とペアを組む可能性がある
  • B で登場する場合
    • v は、 A で登場しなかった B で登場しない v を超える要素とペアを組むか、 A で登場してなおかつ 1 つだけ値が確定しているブロックに属している v を超える要素とペアを組む可能性がある

A で登場しなかった要素が B で登場するかしないかを分けて考えることで、

\mathrm{dp}[i][j][k] := i 番目の要素まで見て、 A で登場せずに B でも登場しない要素でペアになっていないものが j 個、 A で登場せずに B で登場する要素でペアになっていないものが k 個あるときの場合の数

という DP を考えることができる。

下で書いたソースコードでは、 B で登場しない要素同士のペアの順序を考慮していないため、最後に階乗で掛けている。

ソースコード

using mint = ModInt<MOD>;
mint dp[2][310][310];
signed main() {
    int N, M; cin >> N; M = N; N *= 2;
    int both_neg = 0;
    
    vector<int> tp(N + 1);
    for(int i=0; i<N/2; i++) {
        int a, b; cin >> a >> b;
        if(a > b) swap(a, b);

        if(b == -1) both_neg++;
        else if(a == -1 and b != -1) tp[b] = 1;
        else tp[a] = tp[b] = 2;
    }

    dp[0][0][0] = mint(1);
    for(int i=N; i>=1; i--) {
        int cur = i % 2, nxt = 1 - cur;
        for(int j=0; j<=M; j++) {
            for(int k=0; k<=M; k++) {
                if(dp[cur][j][k] == mint(0)) continue;
                if(tp[i] == 2) {
                    dp[nxt][j][k] += dp[cur][j][k];
                }
                // k 増えるのここだけ → 3 次元目は (-1, 値入っているもの) のペア
                if(tp[i] == 1) {
                    dp[nxt][j][k+1] += dp[cur][j][k];
                    if(j) dp[nxt][j-1][k] += dp[cur][j][k];
                }
                // j 増えるのここだけ → 2 次元目は (-1, -1) のペア 
                if(tp[i] == 0) {
                    dp[nxt][j+1][k] += dp[cur][j][k];
                    if(j) dp[nxt][j-1][k] += dp[cur][j][k];
                    if(k) dp[nxt][j][k-1] += dp[cur][j][k] * mint(k);
                }
                dp[cur][j][k] = mint(0);
            }
        }
    }

    mint ans = dp[0][0][0];
    while(both_neg) ans *= mint(both_neg--);
    cout << ans << endl;
    return 0;
}

説明がかなり難しいですね・・・。これ自力で解きたかったなぁ

Codeforces Round #581 Div. 2 D: Kirk and a Binary String

Codeforces 文字列 要考察

問題概要

原文 → Problem - D2 - Codeforces

0 と 1 のみからなる長さ N の文字列 S が与えられる。 S の文字を、以下の条件が満たされた上で変更することを考える。

  • 全ての 1 \leq l \leq r \leq N に対して、 S の l 文字目から r 文字目までのみからできる最長単調非減少列の大きさが元の文字列と変わらない

変更後の文字列であって、0 を最も多く含むものを求めよ。

解説

まず、"10" という文字列について変更不可能であることがわかる。ここから考察を進めていこう。

"10" という文字列は 1 と 0 を 1 文字ずつ含んでいるが、"10" を通過する直前の部分列が最後にどの文字を使ったかによって場合分けする。

  • 部分列が最後に "0" を使用していた場合、つまり "....0xxx10" (x は選択していない文字) のような状況であった場合、それに "10" の 0 を続けるか 1 を続けるか 2 通りの選択ができる
  • 部分列が最後に "1" を使用していた場合、つまり "...1xxx10" のような状況であった場合、それに "10" の 1 を続けることができる

最後に使用した文字に続きうる文字のうち、どれか 1 つを "10" から使用することができることがわかるであろう。言い換えれば、「"10" を通過するときは必ずどれか 1 文字をその中から使っていて、適切に選択すれば最長単調非減少列の大きさに影響しない」ということにもなるため、このようなパターンは元々なかったものとして (削除して) 構わない。

文字列から "10" というパターンを左から順に消していくと、最終的にできる文字列は "0000...0111.....1" のように左が 0 で右が 1 となる文字列である。この文字列に関しては全て "0" に変更してしまっても最長単調非減少列の大きさは変わらない。

ゆえに、stack などを用いて高速に解くことができる。

ソースコード

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

    vector<bool> checked(s.size());
    stack< pair<char, int> > st;
    for(size_t i=0; i<s.size(); i++) {
        if(st.empty() or st.top().first == s[i] or st.top().first == '0') {
            st.emplace(s[i], i);
        }
        else {
            checked[i] = checked[st.top().second] = true;
            st.pop();
        }
    }

    for(size_t i=0; i<s.size(); i++) {
        if(!checked[i]) s[i] = '0';
    }
    cout << s << endl;
    return 0;
}

"10" が変わらないのは思いついたけど、その後が全然ダメだった。難しい・・・