hogecoder

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

JAG 夏合宿 2019 参加記

JAG 夏合宿 2019 に参加しました。昨年に続いて二回目で、今年も four-t としてチーム全員で参加しました。今回は作問もすることになったので昨年とは少し違う面持ちで参加した気がします。

Day 1

割と時間ギリギリでオリセンに向かっていると、知ってる顔のひとたちも同タイミングでたくさん向かっていたので一緒に歩く。

去年と部屋違ってビックリ、部屋おおきい。

いろいろとコンテスト前のアナウンスがあったのち、準備してコンテスト開始。

最近は自分が A を解く担当をしているので A をやる。よめない (は?) もたもたしてるとえび君が B 解けたらしいので代わると通る。FA。プロか?

チームメイトと A を確認していたらいろいろ解釈がまちがっていたことがわかる。介護をうけて AC。

C はペナ出しながらもわりと早い段階で通ってよかった。

これ以降で最初に読んだのは E だった気がする。わりと考えた。

TAB 君によると D が解けたらしいので話を聞くと中国剰余定理が必要らしい。中国剰余定理は持ってるので写経する。一応 __int128 を使いながら実装して通った。

えび君がやっていた J 問題の話を聞くと、最小化は二部グラフの最大マッチングやればできそうという話になり、これも持ってるので写経する。通った。

その後 E の解法を TAB 君がひらめいて、重み付き UnionFind が必要というという話になって、これも持っているので写経しようとしたが、持つ値がヤバそう。これ Python でやったらよくない?となって、えび君に Python に移植してもらった。再帰が多くて RE しているようだったがそれも最終的には回避して AC。この辺チーム戦ならでは感があった。

あとはだいぶ冷えていて、2 問おしかった

  • I: 誤差死
  • K: FFT の工夫がたりなかった

この辺詰められるようになりたいね

終わった後はご飯と風呂を済ませて、Day3 の準備とかボドゲとかやってた気がする。たのしかった。

Day 2

この日も自分が A を解いた。WA (は?) 冷静になる時間が必要なので代わる。

えび君が E を AC。最初の一問担当、代わったほうが良くない・・・?

冷静になったので A を AC した。

F をかなり考えるがわからない。このグラフ上で最大独立集合すればできるんだけどな〜、無理だな〜、で終わってしまった

TAB 君と自分が F を考えている間に I がいつのまにかえび君によって通されていた。FA らしい。やったじゃん。でもそのすぐ後にジャッジ解の間違いによるリジャッジのアナウンスがあった。結果的に FA は幻となった。かなしいね。

D が無限に通されてるわりにわからんとなるが、流石におかしいので問題をよく読む。解釈を間違えていて、正しい解釈をすると書くべきコードが分かったので書く。通った。

中盤何してたのかおぼえてないんですが多分ずっと F やってた。

最後の方に J を考える。全員でなんとか考えると数式が生えて、さらにこれはラグランジュ補間があればどうにかなりそうなことがわかる。これは持っているので写経する。でも最後の詰めが甘くて、偶奇によって標本を変えないといけないことを失念していて人生終了した。この辺は実力が如実に現れたという感じがしますね・・・。

懇親会があってカツサンドくんを撮ったりおしゃべりをしたり翌日の Writer として紹介されたり哀愁ただようカツサンドくんを撮ったりした。

https://twitter.com/_TTJR_/status/1173173793721765888

https://twitter.com/_TTJR_/status/1173193726329413633

この日にあった ABC で黄色になった (5 回目)。ボーダー芸人を安定させるんじゃなくて黄色を安定させてほしい。

Day 3

Writer なのでコンテスト前にいろいろアナウンスした。この日のコンテスト時間は 4 時間でした。

https://twitter.com/_TTJR_/status/1173471957037154304

A は偶奇でなにかやりたいなと思ったのと、簡単枠が枯渇していたので作りました。A 問題なので本質部分はとても軽く、注意力のほうが重要だったかもしれません。

B はそもそも原案が生えた時点で (合宿に限らず) コンテストに出すかどうかすら迷いました。相談したら、いいんじゃない?とのことだったので置きました。逆から処理するとわりと破滅すると思いますが、実は楽が出来ます。

あとテスターをちょこちょこやりました。個人的にヤバい問題だと思うのは F, G, I, J あたりで、この辺は概ね想定通りの結果となりました・・・。

HUPC が終わって問題が余っていたときに声をかけてくれた not さん、JAG のセットを作るためにたくさん作業してくれた Writer の皆さん、英語の校正や連絡面などでたくさんサポートしてくださった JAG スタッフの皆さん、本当にありがとうございました。当日は特にトラブルなく終わって本当に良かったです。

なお、Day3 の解説は Google ドライブ に上げたので、復習にお役立てください。そのうち JAG の Wiki にも載る、はずです。

以下個人的メモ

持ってないもの

  • 一般グラフ最大マッチング
  • 重み付き UnionFind (や、持ってるんだけど久しぶりすぎて中身がどうなってるか曖昧だったのが非常に良くないし改変しづらそうだったからなんとかする)
  • CHT (や、持ってるけど 復習してない問題 があることに気づいてしまった )

復習するもの

ぜんぶ

その他

疲れをとる (明後日から会津合宿マジ?????)

総括

学びしかなかったです、行って本当に良かったです。会津も行く人はまたよろしくお願いします!

TTPC 2019 参加記

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

問題概要

日本語があるので原文参照 → 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;
}

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