2019-07-07

競プロライブラリをPDFにする無限にあるうちの一つの方法

競技プログラミングのライブラリをPDFにする無限にあるうちの一つの方法

もうすぐICPCなのでライブラリを印刷したいけど印刷できる状態にするのがめんどくさい...
そもそも綺麗にする方法なかなか見つからないし見つかってもファイル一つ一つやるのか...

そんな気分になったので競プロのライブラリをPDF(にできるようなTeXファイル)化するスクリプト書きました(誇張)
そこまで見た目が良くない(終わり)
そこまで楽でもない(はい)

リポジトリはこれなのでこっから適当にダウンロードして頑張ってください
template/template.texは使うので必要です. ちなみにプログラムへの引数のデフォルトは同じディレクトリにあること想定してるのでちゃんと指定するか移動させてください.

https://github.com/maze1230/Library-TeX-Generator

最初は細字だったんですが試しにコンビニで印刷してみたら掠れたので太字にしました
太字にしてから印刷してないのでもしかしたら文字が潰れるかもしれない(家にプリンターがほしすぎる)

準備

LaTeX

TeXファイルを作るだけなのでTeXファイルをコンパイルできる環境が必要
僕は"macOS Mojave 10.14.5"なのでその状況でのインストール

基本的にこれをした
少しだけ詰まったのでそこを書く

今これと同じようにmactexをインストールするとMacTeX2019が入るので気をつける

sudo tlmgr update --self --all

をしろと書いてあるが僕はパスが通ってなかったのでできなかった. 初心者なのでcommand not foundって言われて、ちゃんとインストールできなかったのか...？と数回インストールし直す人をした(初心者なので). brewでインストールしたんだからパス通ってると思っちゃわないか？思ってしまいました

sudo /usr/local/texlive/2019/bin/x86_64-darwin/tlmgr path add

みたいな感じのことをしてパスを通した、もう記憶曖昧なのでpathとadd逆かも

ついでに僕はLaTeXは書くとしたらVSCodeから書くかなぁという気持ちになったのでVSCodeのほうもやった
ここは関係ないところが原因だったけどなんか詰まって他の人のを参考にした. ただ、-shell-escapeが必要なので下みたいにargsを少し変えた.

"latex-workshop.chktex.enabled": true,
"latex-workshop.latex.recipes": [
    {
    "name": "Report",
    "tools": ["ptex2pdf"],
 }
],
"latex-workshop.latex.tools": [
    {   
        "name": "ptex2pdf",
        "command": "ptex2pdf",
        "args": [
            "-l",
            "-ot",
            "-kanji=utf8 -synctex=1 -file-line-error -shell-escape",
            "%DOC%"
        ]
    }
],
"latex-workshop.view.pdf.viewer": "tab",

ここまでやれば多分環境は整っている気がする.
スクリプトで生成したTeXファイルをVSCodeで開いてCmd+Shift+PからのBuild LaTeX Projectで行けるはず。
めっちゃ詰まっててごちゃごちゃいろいろしたのでなにか足りていないかもしれない.

使い方

Githubの方に書いてる(わかりにくいけど頑張って)
TOMLの流儀しらないから完全自己流の意味わからない設定方法になりましたが...

おわり

僕は必要だったからなんとなく書いたけど多分どこのチームも持ってるんだろうね
ここまでかいてこれ見つけちゃって泣いちゃった、みんなはちゃんと調べてから行動しような
フォントとか普段使ってるやつにしたかったけどLaTeXわからなすぎるな、悲しい
使う人、いなくないか？いなさそう
普通PCK参加した時点でみんなこういうの書くのかもしれないですが、僕は書かずにゴリ押しして1ファイルに付き1PDFファイルみたいなことをしてコンビニで頑張って印刷する悲しい人になっていました
PCK出る人とかも使ってくれると嬉しめ、左上のヘッダ部分にチーム名入れられるし(必要ないね)

2019-05-12

diverta 2019 E - Xor Partitioning

C/C++ プログラミング競技プログラミング

diverta 2019 Programming Contest E - XOR Partitioning

自分の頭が弱くなりすぎていて悲しい，どうにかしていきたい
4完した時点で11位だったのにね，そっからなにもできなかったね
unratedになっていただき助かった

問題概要

N 要素の数列 A が与えられる．
これをいくつかの区間に分けるような $2^{N-1}$ 通りのうち，それぞれの区間のxorが等しくなるようなものはいくつあるか．

解法

数列全体のxorが0でなければその値 X がそれぞれの区間の値になることがわかる．
- この場合は求めるのが簡単．僕は詰めきれなかったけど．
prefixから偶数個の区間のxorを取ると0になる
- prefixのxorが0になるような点で区切れば2つの区間ずつ考えていける
累積xorが0になるような区間の中に x が現れる場合，そこで区切るとそれぞれの区間のxorは x になる

最初に累積xor， B を取っておいて考える.

ここで $dp \lbrack i \rbrack \lbrack x \rbrack := \lbrack 0, i \rbrackをxorがxになる区間に分ける方法$ と置く．
また， $cnt \lbrack i \rbrack \lbrack x \rbrack := B の \lbrack 0, i ) にxが今まで何回登場したか$ も持つ．
$dp \lbrack x \rbrack$ を更新するタイミングは B に0が登場したタイミングだが，ここで毎回行うと $O(NA_{max})$ になってしまうので，次に B の中で $x$ が登場したときに更新するように遅延評価することにする．

$dp \lbrack i \rbrack \lbrack x \rbrack$ の更新の式は3.を利用すると, $dp \lbrack i \rbrack \lbrack x \rbrack = \sum dp_{j} \lbrack j \rbrack \lbrack x \rbrack \times (cnt \lbrack i \rbrack \lbrack x \rbrack - cnt \lbrack j \rbrack \lbrack x \rbrack)$ となることがわかる．
当然これをそのまま行うと遅延評価しようと計算量大爆発になってしまう．
$dp \lbrack i \rbrack = cnt \lbrack i \rbrack \sum dp \lbrack j \rbrack - \sum dp \lbrack j \rbrack \times cnt \lbrack j \rbrack$ と式変形すると，右辺は $cnt \lbrack i \rbrack$ しかiに依存しないので， $dp2 := \sum dp \lbrack j \rbrack$ , $dp3 := \sum dp \lbrack j \rbrack \times cnt \lbrack j \rbrack$ とする.
$dp = cnt \times dp2 - dp3$ となり，それぞれ $dp2 = dp2 + dp$ ， $dp3 = dp3 + dp \times cnt$ と更新することができる．

また, $x$ が現れる前に0が複数回現れているときのことを考える.
0が現れただけこの更新を行うと再び計算量大爆発なので， $O(1)$ で終わらせたい気持ちになる．cntが変化しないことを考慮すると，

$\displaystyle \begin{aligned} dp2' &= dp2 + dp \\ dp3' &= dp3 + dp \times cnt \\ dp' &= cnt \times dp2' - dp3' \\ &= cnt \times (dp2 + dp) - (dp3 + dp \times cnt) \\ &= cnt \times dp2 - dp3 \end{aligned}$

となるので， $dp$ は一回やったときと同じ結果になる． $dp2, dp3$ の変化は，更新した回数(同じ値) $dp$ が足し込まれるので，それまでに処理した0の個数と今の位置までの0の個数を持っとけばその差だけかけた値を足し込めばできる．

実際に解を出力する際には，総xorが0の場合と0以外の場合で分ける．

0のとき

まず遅延評価のうち評価できてない分を評価する．
それぞれの区間のxorが0になるような分け方は，0が B に現れる回数を $K$ としたとき， $2^{K-1}$ になるので別で計算する．
xorが $x$ になるような分け方は， $dp \lbrack N \rbrack \lbrack x \rbrack$ なので，これを答えに足す．

0以外のとき

A の総xorを $x$ とすると， $\sum dp \lbrack i \rbrack \lbrack x \rbrack$ が解になるが，これは既に計算していて $dp2$ なのでこれを出力する．

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int64 N;
    cin >> N;
    vector<int64> A(N);
    REP(i, N) cin >> A[i];
    vector<Mint> dp(1 << 20, 0), dp2(1 << 20, 1), dp3(1 << 20, 0);
    vector<int64> cnt(1 << 20, 0), zok(1 << 20, 0);
    int64 xx = 0;
    int64 zero = 0;

    REP(i, N) {
        xx ^= A[i];
        if (xx == 0) {
            zero++;
        } else {
            if (zok[xx] != zero) {
                dp[xx] = dp2[xx] * cnt[xx] - dp3[xx];
                dp2[xx] += dp[xx] * Mint(zero - zok[xx]);
                dp3[xx] += (dp[xx] * cnt[xx]) * Mint(zero - zok[xx]);
                zok[xx]++;
            }
            zok[xx] = zero;
        }
        cnt[xx]++;
    }

    Mint res = 0;
    if (xx == 0) {
        FOR(i, 1, dp.size()) {
            if (zok[i] != zero) 
                dp[i] = (dp2[i] * cnt[i] - dp3[i]);
            res += dp[i];
        }
        res += Mint(2).pow(zero-1);
        cout << res << endl;
    } else {
        if (zok[xx] != zero) {
            dp[xx] = dp2[xx] * cnt[xx] - dp3[xx];
            dp2[xx] += dp[xx] * Mint(zero - zok[xx]);
            dp3[xx] += (dp[xx] * cnt[xx]) * Mint(zero - zok[xx]);
        }
        cout << dp2[xx] << endl;
    }
}

2019-03-12

AGC 030 F - Permutation and Minimum

競技プログラミングプログラミング C/C++

AGC 030 F - Permutation and Minimum

初めて1600点とかいう高得点の問題をACできたので嬉しくてブログを書く

問題概要

いくつかの要素が欠けている1〜2Nで構成された順列Aが与えられるので，欠けている部分を埋めて順列A'を作る．
${min(A'[2i], A'[2i+1])}$ をB[i]とした数列Bを構成する．
このときBとなる数列は何種類できるか．

解法

なんか解説の解法はめっちゃ簡潔でした，僕の解法は簡潔ではありません(はい)
解説「2N→1の順に見ていきます」
ぼく「1→2Nの順に見ていきます(不穏)」

どう考えてもDPっぽいので，DPとしてどういう情報を持ちたいかを考えます
A[2i]とA[2i+1]をペアにして考えるべきだとわかるので
1. どちらもまだ決まっていないペアの数 2. 片方がaだと決まっていて，今見ている数xよりも大きいようなペアの数 3. 片方がaだと決まっていて，今見ている数xよりも小さいようなペアの数 4. どちらも決まっているペアの数

の4種類の情報がほしいことがわかります
ここで，ペアの総数，既にいくつ決まっているかがわかると4種類のうち，種類1か4の片方，種類2か3の片方が決まっていれば残りもわかるので，2種類だけ持てばいいことがわかります
これはよくある次元を減らすテクなのでここまでは自明です

今回はdp[i][j][k] := 現在iを見ていて，種類1のペアがj個，種類2のペアがk個として考えます．
Nがペアの総数，Mが既に決まっている要素数，種類3の数をk3, 種類4の数をk4とすると， ${k3+2*k4 = M-k，k3+k4 = N-j-k}$ の2式が立つので ${k3 = 2*N-M-2*j-k, k4 = M-N+j}$ となる

そして小さい方から見ていくとき，その数がAの中に含まれているときと含まれていないときを分けて考えます．

Aに含まれていないとき

このとき，iは種類1，種類2，種類3のペアのうちのどれに含めるかの選択肢があります．
ただし，種類3に含めるときは結果となるBに変化が起こらないため足し込むときに係数は1で，それ以外のときはBに影響するので係数はそのペアの数になります
種類1のペアに含めると，次のi+1を見るときのことを考えると種類3が増えますが，dp配列の添字には含まれないので種類1だけ減らします
同様に種類2だと種類4が増えますが種類4は添字にないので種類2だけ減らし，種類3のとき種類3が減って種類4が増えますがどちらもないので何もしません

if (j > 0) dp[i+1][j-1][k] += dp[i][j][k] * j;
if (k > 0) dp[i+1][j][k-1] += dp[i][j][k] * k;
if (k3 > 0) dp[i+1][j][k] += dp[i][j][k];

Aに含まれているとき

iのペアがAで決まっているときは最初から種類4の個数としてカウントされているので添字部分では何も変化しません．

iのペアがAで決まっていないとき，最初は種類2としてカウントされていますが，i-1までの間に種類4になっている可能性があります
つまり，dp[i][j][k]で，k個の中に含まれている場合と既に含まれていない場合があるので，含まれている場合はdp[i+1][j][k-1]に遷移してあげないといけません．

Aで，一方がi以上でもう一方が決まっていないようなペアの数をpとしておくと，p個のうちk個が残っているということになります(新たに増えた一方のみが決まっていないようなペアは種類3でありkにカウントされないので)
iのペアが既に決まっている場合の数は，p個のペアについて均等になっているはずなので，dp[i][j][k] * k / pとなります．
まだ決まっていないときは種類2としてカウントされてた分が種類3になるので種類2が一つ減るように遷移をします
よって遷移は次のようになります

if (k > 0) dp[i+1][j][k-1] += dp[i][j][k] * (p - k) / p;
dp[i+1][j][k] += dp[i][j][k] * k / p;

pは最初に累積和をしておくと簡単に求められます

~~ここまでをやると計算量はそのままO(N³)になります~~
beetさんから指摘されましたがModの割り算をしているのでlog MODがかかり，O(N³ log MOD)です

コードは下のようになりますが，変数名とか無駄な変数とか変なところがたくさんあるので参考にはなりません

int main(void) {
    int N;
    cin >> N;
    vector<int64> A(2*N), sc1(2*N+1, 0);
    vector<bool> used(2*N+1, 0), ispair(2*N+1, 0);
    int cnt[3] = {};
    int luz = 0;
    REP(i, 2*N) {
        cin >> A[i];
        if (A[i] != -1) used[A[i]-1] = 1;
        if (A[i] != -1) luz += 1;
        if (i%2) {
            cnt[(A[i-1] != -1) + (A[i] != -1)]++;
            if ((A[i-1] != -1) + (A[i] != -1) == 1) {
                sc1[max(A[i-1], A[i])]++;
            } else if ((A[i-1] != -1) + (A[i]!=-1) == 2) {
                ispair[A[i-1]-1] = 1;
                ispair[A[i]-1] = 1;
            }
        }
    }
    REP(i, 2*N) sc1[i+1] += sc1[i];
    vector<vector<Mint>> dp(310, vector<Mint>(310, 0));
    dp[cnt[0]][cnt[1]] = Mint(1);
    REP(i, 2*N) {
        vector<vector<Mint>> dp2(310, vector<Mint>(310, 0));
        REP(j, N+1) { // [-, -] のかず
            REP(k, N+1) { // [-, *]かつ*>iの数
                int64 rest = N-j-k;
                int64 latte = luz-N+j; // [*, *]
                int64 beet = 2*N-luz-2*j-k; // [-, *]かつ*<i
                if (j < 0 || k < 0 || rest < 0 || latte < 0 || beet <0) continue;
                if (used[i]) {
                    if (ispair[i]) {
                        dp2[j][k] += dp[j][k];
                    } else {
                        Mint exist_posi = Mint(k)/Mint(sc1[2*N]-sc1[i]), inv_posi = Mint(sc1[2*N]-sc1[i]-k)/Mint(sc1[2*N]-sc1[i]);
                        if (k > 0)
                            dp2[j][k-1] += dp[j][k] * exist_posi;
                        dp2[j][k] += dp[j][k] * inv_posi;
                    }
                } else {
                    if (j > 0)
                        dp2[j-1][k] += dp[j][k] * j;
                    if (k > 0)
                        dp2[j][k-1] += dp[j][k] * k;
                    if (beet > 0)
                        dp2[j][k] += dp[j][k];
                }
            }
        }
        if (!used[i]) luz++;
        swap(dp, dp2);
    }
    cout << dp[0][0] << endl;
}

2019-02-10

戻すDPわからない

はてなでの数式の扱い良くわからなくて意味わからないことになっている

戻すDPわからない

随分前から名前を見てたものの学ぼうとしてなかった
コドフォに出たことでTLでめっちゃ見えたので流石にやろうと思ったら理解に苦しんだので自分のためだけにブログを書く
実際には深く理解してないので意味のわからないことしか書けないけど

yukicoderのこれを見て理解できる人はすごいと思う．これが理解できるような人になりたい人生だった．

概要

DPで数え上げをするときに特定の要素を特別扱いしたくなることがある
そのとき，要素の順番を変えてもDPの結果が同じになるような場合ではその要素がなかったときの結果が求められる
これは例えばdp[i][j] := i番目まで見てi-1番目がj個残ってるときみたいな定義になるとダメ，多分(自信がない)
この場合でも当然，N個目を取り除いた場合が知りたければN-1個目までしか処理しなければ求められるけど，戻すDPが適用できる場合はそれが何個目の要素のときでもできるよというのが本質

戻すDPが適用できる条件は次の2つ
1. 要素の順番が数え上げに関係しない
2. DPの漸化式を式変形することでdp[i] = dp[i+1] * ... + ...みたいな雰囲気ができる

このとき，2.ができるためには情報が消えてはいけないので遷移に場合分けがあったらダメ

3問戻すDPを使う問題を解いたのでそのときの気持ちと解法を下に書く

注文の多い高橋商店

とりあえず簡単すぎると言われている方が解けないことには話にならないので解く．
僕ぐらいになるとここで詰まってしまうから悲しい
単純に考えるとDPの遷移は ${dp_{i, j} = i種類目まで見てj個選んでいるときの通り数}$ として一行目のようになっている
このままだと計算量大爆発( ${O(NM^2)}$ ぐらい)なため，累積和を使うことで削減できるがめんどくさい
ここで ${j-1}$ で計算したものが二行目のようになっていることを考えると引いて式変形することで三行目のような遷移になり単純になる
このとき，漸化式は左辺に ${dp_{i+1, j}}$ が来るようなもらう形になってるとなんか戻しやすい気がする．そんな関係ないかも

${\displaystyle dp_{i+1, j} = \sum_{k=0}^{a_i} dp_{i,j-k} \\ dp_{i+1, j-1} = \sum_{k=0}^{a_i} dp_{i,j-k-1} \\ dp_{i+1, j} - dp_{i+1, j-1} = \sum_{k=0}^{a_i} dp_{i,j-k} - \sum_{k=0}^{a_i} dp_{i,j-k-1} \\ \Leftrightarrow dp_{i+1, j} = dp_{i, j} - dp_{i, j-a_i-1} + dp_{i+1, j-1} }$

よって普通にDPができたので，これを戻せれば勝ち
ちなみに添字が0未満になるところは0として考える．これは場合分けになるから戻せなくなるのでは？みたいな気持ちになるけど0未満になる場合はありえなくて実際0通りなので問題ない．
僕はget(dp, i, j)みたいな感じで呼んだらどっちか0未満なら0を返すみたいなのを用意した

戻した結果として ${dp2_{i, j} = i種類目を使わないでj個選ぶ通り数}$ となるdp2を求める
ここで漸化式を式変形して左辺に ${dp_{i, j}}$ が来るようにすると ${dp_{i, j} = dp_{i+1, j} - dp_{i+1, j-1} + dp_{i, j-a_i-1}}$ となる．
なので，i番目を戻したい(除いた場合を考えたい)ときに行う遷移は ${dp2_{i, j} = dp_{N, j} - dp_{N, j-1} + dp2_{i, j-a_i-1}}$ となり，右辺で ${dp2}$ を参照するときの添字を考えて ${j}$ が小さい方から回すことになる．
${dp2}$ が求まったので，クエリの ${k_i}$ 種類目をちょうど ${x_i}$ 個使う時というのは ${k_i}$ 種類目を使わないで ${M-x_i}$ 個選ぶのと同じであることから答えは ${dp2_{k_i, M-x_i}}$ となる．
コードは下のやつなんですが，この問題だけModIntを使っていない

int main(void){
    for (auto& x : dp) for (auto& y : x) y = 0;
    for (auto& x : dp2) for (auto& y : x) y = 0;
    cin >> N >> M >> Q;
    a.resize(N);
    for (auto& x : a) cin >> x;
    dp[0][0] = 1;
 
    REP(i, N){
        REP(j, M+1){
            dp[i+1][j] = (get(dp, i+1, j-1) - get(dp, i, j-a[i]-1) + get(dp, i, j))%mod;
        }
    }
    REP(i, N){
        REP(j, M+1){
            dp2[i][j] = (get(dp, N, j) - get(dp, N, j-1) + get(dp2, i, j-a[i]-1))%mod;
            dp2[i][j] = (dp2[i][j] % mod + mod) %mod;
        }
    }
    while(Q--){
        int64 k, x;
        scanf("%lld %lld", &k, &x); k--;
        printf("%lld\n", dp2[k][M-x]);
    }
}

生放送とBGM

これは戻すDPなのかなあとなるけど戻すDPのところで紹介されてたので戻すDPだと思いながら考える(最悪)
特定の曲に注目して考えることになるので考えると，ある曲が再生されるときの通り数を全ての曲に対して求め足し合わせると答えになることがわかる

特定の曲が再生されるかどうかはその曲が再生され始める時間が ${L-1}$ 以下なら良いので ${dp_{i} = 曲の合計時間がiとなるような通り数}$ にして，戻した後に ${\sum_{k=0}^{L-1} dp_{k}}$ を求めれば良さそうとなる
しかしこの問題では全部の順列に対して求める必要があるので，時間が ${k}$ になる組み合わせではなく順列が知りたい．更に特定の曲の後に流れる予定の部分についても順番が区別されるため，この両方を求めるために特定の曲までに何曲流したのかも欲しい．

なので ${dp_{i, j} = i曲流した合計時間がj}$ としてDPを行う．
これを戻すと ${dp2_{k, i, j} = k曲目を除いてi曲流したときの合計時間がj}$ という配列が手に入るため，答えは ${\sum_{k=0}^{N} \sum_{i=0}^{N-1} \sum_{j=0}^{L-1} dp2_{k, i, j} \times i! \times (N-i-1)!}$ を求めた後に期待値なので ${N!}$ で割ればいい
僕は初心者なのでmodの問題でもないのにどうやってそんな大きい階乗をとれば...と思ってたけどdoubleでやれば大丈夫だった(それはそう)

肝心のDPの遷移と戻し方だが，普通のDPは ${dp'_{i, j} = dp_{i, j} + dp_{i-1, j-S_i}}$ でできる．
このときに配るDPをやろうとして，更に時間の合計がL以上になる部分はまとめていいだろ〜みたいな気持ちになり ${dp'_{i+1, min(L, j+S_i)} = dp_{i+1, min(L, j+S_I)} + dp_{i, j}}$ とかやると， ${min}$ が実質的に場合分けになっているので戻せなくなる．この場合は戻すときに ${dp_{N, L}}$ にどこから足されたかがわからなくなってしまうため
どちらの場合でも，この問題では一回戻すため一回戻せるだけの余裕をもたせる必要がある．

一曲の時間の最大値を ${S_{max}}$ とおくと配るDPなら ${min}$ のとり方を ${min(L+S_{max}, j+S_i)}$ にすれば良くて(普通のDPをする際には ${j}$ を ${L-1}$ までしか回す必要がないので配列を十分にとっておけばminを取らなくてもいい)
もらうDPなら ${j}$ を ${L+S_{max}}$ まで回せばいい

このとき，戻すDPの遷移は ${dp2_{k, i, j} = dp_{N, j} - dp2_{k, i-1, j-S_k}}$ でできる
今回も ${j}$ が小さい方から回すことになる

コード,initでfactを初期化している．
さっきのもそうだったけどdpの添字や配列名があってないのは空間計算量削減とかあるので許してください．

int main(void){
    init();
    cin >> N >> L;
    L *= 60;
    S.resize(N);
    REP(i, N){
        int64 m, s;
        scanf("%d:%d", &m, &s);
        S[i] = m*60+s;
    }
    vector<vector<int64>> dp(N+1, vector<int64>(L+60*60+1, 0));
    dp[0][0] = 1;
    REP(i, N){
        vector<vector<int64>> dp2(N+1, vector<int64>(L+60*60+1, 0));
        REP(j, N+1){
            REP(k, L+60*60+1){
                dp2[j][k] = get(dp, j-1, k-S[i]) + get(dp, j, k);
            }
        }
        swap(dp, dp2);
    }
    double res = 0;
    REP(i, N){
        vector<vector<int64>> dp2(N+1, vector<int64>(L+60*60+1, 0));
        REP(j, N+1){
            REP(k, L+60*60+1){
                dp2[j][k] = dp[j][k] - get(dp2, j-1, k-S[i]);
                if (k < L && N-j-1 >= 0)
                    res += dp2[j][k] * fact[j] * fact[N-j-1] / fact[N];
            }
        }
    }
    cout << fixed << setprecision(10) << res << endl;
}

Destroy the Colony

問題概要

僕が読解に苦しんだのでこれだけ問題概要
偶数長の英文字(大小)からなる文字列 ${S}$ が与えられる
これの並び替えのうち，文字列を前後半に分けた時に同じ文字が同じ側にある並び替えは嬉しい(Destroy the Colonyできる)
このとき次のクエリが与えられるので処理しなさい

${S_x}$ と ${S_y}$ が同じ側になるような並び替えは何通りあるか出力せよ

${S_x}$ と ${S_y}$ が同じなら普通に全部の嬉しい並び替えを答えればいいみたいな感じ
クエリの種類が実質 ${52^2}$ 種類しかない( ${S_x}$ と ${S_y}$ が逆でも答え一緒なので実際は半分強)ので先に計算しておけば勝ち

明らかに特別扱いしたいものがあるので戻すDPだなとなるが，2つあるので当然2回戻す

答えの求め方が僕の考えたTLEするやつと解説の方法がある．
解説のほうが明らかに明快(僕には難しくて難解だった)なのでそっちを先に書いて，僕の考えたやつは最後に書く(読みたい人は読んでって感じ)

解説解

それぞれの文字種がいくつ現れるかを ${c_i}$ とする. この時， ${|S|/2}$ 個ずつになるように分ける組み合わせがわかれば，そのときの組み合わせを ${x}$ とすると，前半と後半それぞれについて重複順列を求めてかけ合わせたものに ${x}$ をかければいいので下のようになる

${\displaystyle ans = \frac{x \times (|S|/2)! \times (|S|/2)!}{\prod_{i=0}^{51} c_i!} }$

${x}$ 以外の部分はどういう分け方でも共通なのであらかじめ計算しておく
じゃあ ${x}$ を求めればいいねとなり，これは上の二問よりも簡単では？みたいな気持ちになる
ここで ${dp_{i, j} = i番目まで見て前半にj個あるときの分け方の通り数}$ とすると ${dp_{i+1, j} = dp_{i, j} + dp_{i, j-c_i}}$ となる．
これを戻す形にすると ${dp_{i, j} = dp_{i+1, j} - dp_{i, j-c_i}}$ になる
${j}$ の範囲としては，2回戻す分必要かつそれぞれの文字種の個数が決まってないので ${|S|}$ まで回す必要がある？(ないかも)

文字種 ${a}$ で一回戻したときを ${dp1}$ ，文字種 ${b}$ で更に戻したときを ${dp2}$ とすると， ${dp1_{i} = dp_{N, i} - dp1_{i-c_a}}$ で ${dp1}$ がわかり，全く同じことをして ${dp2_{i} = dp1_{i} - dp2_{i-c_b}}$ で ${dp2}$ が求まる
${a=b}$ なら ${x = dp1_{|S|/2} = dp1_{|S|/2-c_a}}$ , そうでなければ ${x = dp2_{|S|/2} = dp2_{|S|/2-c_a-c_b}}$ となる
各 ${a}$ について ${dp1}$ を求め，それを用いて各 ${b}$ について ${dp2}$ を求めればいいので，計算量は使用されている文字の種類数を ${C}$ とすると ${O(C|S| + C^2|S|)}$ となり， ${O(C^2|S|)}$ である．
戻すときの処理が全く同じなのでそこを関数化すると簡単にかけるらしい

コード，僕はそれをしていない
MintがModIntで，fというのはFactorialライブラリ，f.comb(a, b)で ${_aC_b}$ を返す．
めっちゃコードが長くて何が起こってるかわからないね
これが1970msぐらい

int main(void){
    vector<int64> c(52, 0);
    cin >> s >> q;
    n = s.size();
    REP(i, s.size()) c[ctoi(s[i])]++;

    Mint W = f[n/2]*f[n/2];
    REP(i, 52) W /= f[c[i]];

    vector<Mint> dp(n+1, 0);
    dp[0] = 1;
    REP(i, 52){
        if (c[i] == 0) continue;
        vector<Mint> dp2(n+1, 0);
        REP(j, n+1){
            dp2[j] = get(dp, j-c[i]) + get(dp, j);
        }
        swap(dp, dp2);
    }
    vector<vector<Mint>> ans(52, vector<Mint>(52, 0));
    REP(i, 52){
        if (c[i] == 0) continue;
        vector<Mint> t1(n+1, 0);
        REP(j, n+1){
            t1[j] = get(dp, j) - get(t1, j-c[i]);
        }
        REP(j, 52){
            if (c[j] == 0) continue;
            if (i == j) {
                ans[i][j] = t1[n/2];
                continue;
            }
            vector<Mint> t2(n+1, 0);
            REP(k, n+1) {
                t2[k] = get(t1, k) - get(t2, k-c[j]);
            }
            ans[i][j] = t2[n/2];
        }
    }
    while(q--){
        int32 x, y;
        scanf("%d%d", &x, &y); x--; y--;
        x = ctoi(s[x]); y = ctoi(s[y]);
        cout << ans[x][y] * W * 2 << endl;
    }
}

僕の解法

DPは万能なので，DPで組み合わせだけ求めてそれに並び替えをかけなくても最初から並び替えた後を求められるじゃ～んみたいな気持ちになっていた
つまり， ${dp_{i, j} = i種類目まで見て前半にj個あるときの前半後半含めて並べ方}$ をした．
ここで，既に ${i}$ 個あるところにこれを並び替えず同じ種類のものを ${j}$ 個追加したときの並べ方は，ある種類のもの ${i}$ 個と別の種類のもの ${j}$ 個の並べ方と同じなので ${\frac{(i+j)!}{i!j!} = _{i+j}C_{j}}$ となる．

${sum_i = \sum_{k = 0}^{i-1} c_i}$ とする
前半に ${i}$ 種類目を追加するか後半に追加するかの二通りの遷移があるので合わせて ${dp_{i+1, j} = dp_{i, j-c_i} \times _jC_{c_i} + dp_{i, j} \times _{sum_i-j+c_i}C_{c_i}}$ となる
これを戻す形にすると下のような形になる．
戻す文字種を先ほどと同じように ${a, b}$ とすると，文字種を並び替えて一番後ろから ${a, b}$ にして，分母の ${sum_i-j+c_i}$ が一回目は ${sum_a+c_a = N}$ であることから ${N-j}$ ，二回目は ${sum_b+c_b = sum_a-c_b + c_b = N-c_a}$ となる．
こっちが最初に書いたやつなので答えの部分がすこしごちゃごちゃしてます.

${\displaystyle dp_{i, j} = \frac{dp_{i+1, j} - dp_{i, j-c_i} \times _jC_{c_i}}{_{sum_i-j+c_i}C_{c_i}} }$

二回戻した後， ${dp_{|S|/2}}$ が求まったら取り除いている分を追加したときの並び替えを答えないといけないので， ${dp_{|S|/2} \times _{|S|/2-c_a}C_{c_b} \times _{|S|/2}C_{c_a}}$ が答えになります
後は組み合わせが0になってゼロ割してしまわないように気をつけて下のコードのようになります
さっきのが1970msぐらいなので，遷移が定数倍重くなってるこっちは当然TLEします．
お疲れ様でした，多分test9までは通ってるので解法としてはあっているはず

int main(void){
    cin.tie(0);
    ios::sync\_with\_stdio(false);
    vector<int64> c(52, 0), sum(53, 0);
    cin >> s >> q;
    n = s.size();
    REP(i, s.size()) c[ctoi(s[i])]++;
    REP(i, 52) sum[i+1] += sum[i] + c[i];

    vector<Mint> dp(n+1, 0);
    dp[0] = 1;
    REP(i, 52){
        if (c[i] == 0) continue;
        vector<Mint> dp2(n+1, 0);
        REP(j, n+1){
            dp2[j] = dp[j] * f.comb(sum[i]-j+c[i], c[i]) + get(dp, j-c[i]) * f.comb(j, c[i]);
        }
        swap(dp, dp2);
    }
    vector<vector<Mint>> res(52, vector<Mint>(52, 0));
    vector<Mint> t1(n+1, 0);
    vector<Mint> t2(n+1, 0);
    REP(i, 52){
        if (c[i] == 0) continue;
        REP(j, n+1) {
            if (n-j >= c[i]) {
                t1[j] = (get(dp, j) - get(t1, j-c[i]) * f.comb(j, c[i])) / f.comb(n-j, c[i]);
            }
        }
        FOR(j, i, 52){
            if (c[j] == 0) continue;
            if (i == j) {
                res[i][j] = t1[n/2] * f.comb(n/2, c[i]) * 2;
                continue;
            }
            REP(k, n+1){
                if (n-c[i]-k >= c[j]) {
                    t2[k] = (get(t1, k) - get(t2, k-c[j]) * f.comb(k, c[j])) / f.comb(n-c[i]-k, c[j]);
                }
            }
            if (c[i]+c[j] <= n/2)
                res[i][j] = res[j][i] = t2[n/2] * f.comb(n/2-c[i], c[j]) * f.comb(n/2, c[i]) * 2;
        }
    }
    while(q--) {
        int64 x, y;
        cin >> x >> y; x--; y--;
        x = ctoi(s[x]); y = ctoi(s[y]);
        if (x == y) {
            cout << res[x][y] << endl;
        } else if (c[x] + c[y] > n/2) {
            cout << 0 << endl;
        } else {
            cout << res[x][y]  << endl;
        }
    }
}

2018-09-04

JOI夏季セミナー2018参加記

日常

夏季セミナー2018参加記

去年に引き続き夏季セミナーに参加してきたので参加記を
SuperConに参加していないので夏休み唯一のなんか競プロ系のアレな気がする
受験生がそれなりに来ていて嬉しかった

一日目

IOI金メダリスト(予定確定!!!)(プレッシャーをとてつもなくかけていく)等3人と僕で新宿でラーメンを食べる
当ブログはIOI日本代表を応援しています

豚骨ラーメン～レッドコーダーを目指して～ pic.twitter.com/XXUEO7Q4S6
— 迷路 (@pazzle1230) 2018年8月15日

どっかを経由してバスに乗ってこれから4泊5日を過ごす何とかっていうところに行く

集合場所に行くと部屋に最大人数入れるようにするマラソンマッチで最適解みたいな感じに机と椅子が並んでいた
しかしレッドコーダーの温床だったので最適解を超える解が出てきて机と椅子が並び替えられた
~~最初の配置明らかにおかしくて，大人数を部屋に入れる気がなかった~~
自己紹介とかあり，IOI日本代表(非公式含む)8人のうち7人がいてすごいと思った
本はいろいろあって，暗号理論以外だったら何でもいいなという気持ちでグラフ理論にしたけどもうちょっと読んでみたら暗号理論でも普通に良かったなみたいな気持ちになった
グラフ理論にした決め手は，チューターがよく知らない人だけどすごそうなオーラが出ていたからなんですが

その後本ごとにそれぞれの部屋に別れた後

ぼく「...」
チューター「...」
ぼく「...」
チューター「...」

みたいなことをする，これから5日間お世話になる人なのでコミュニケーションは当然欠かせない
チューターによる基礎用語と基礎知識解説みたいなのを聞いてなるほどなぁとなる
その後適当に読んで自分がやりたい章を決めるみたいな感じになって，彩色を選んだら五人の内僕しかいなかった．平面グラフは三人いたので幾何できない僕はプロだなぁという気分でした
まあ数学ができるので一人だけの章の人がもう一人いることがわかるのでわかる

夕飯の量が多いんですよね

正直この時点であのとても有名な五色定理をやろうと決めていたため余裕やろみたいな気分になってた
まあ当然これは嘘でコンピュータを使って証明が何ページにも渡ったと言われているので5日では不可能なんですが僕は天才なのでできます．
4という数字は不吉なので僕は知らないことにしています．

セミナーが終わったところで風呂に入りボードゲーム大会が始まる
カルカソンヌとかして，せっかくSwitchがあるので某先輩所持のマリカーやぷよテトをした
多分寝たの三時か四時，何してたか忘れましたが

二日目

朝ごはんを食べる
去年と変わってなくて飽きたことに気づく

セミナー，読むだけ

講義，当然機械学習に興味があるので寝るわけなく真剣に聞く
~~前半寝ていて~~後半理解できなかった，悲しい

セミナー読むだけここらへんで多分普通の五色定理の証明を読み終わる
もういいのでは？みたいな気分になりながら読み続ける

夕飯食べる，当然昼飯はもう食べている

読む

終わり
何したか忘れたけどどうせボードゲームをしている

スタバ行ったしTwitterに上げてるかなと思ったら上げてなかった

確か寝たの四時

三日目

朝ごはんは飽きているので食べなかった
今ドキの女子なのでスタバだけでお腹いっぱいになるため

読む
ここらへんでもう一つの五色定理の証明方法がでてきてそっちを発表にしようという気持ちになる

多分ここらへんで少し競プロをした
チューターの人，まあ大悪魔専門家の人なんですがサイクル基底とかの話をしてたので聞いた

ミュージカル鑑賞が趣味の人に質問することでなんとか彩色の章を読み切った
やったぜ

夕飯たべるよね，昼飯は食べてる

交流なので交流する
カルカソンヌとかお邪魔者とかをやった気がする
コードネームで戦犯かましたのこの日だった気がする

イマドキの女子なので当然スタバに行く

明日の徹夜に備えて健康的な生活✌️ pic.twitter.com/FzLk3BYI1J
— 迷路 (@pazzle1230) 2018年8月17日

海辺で飲んだいつもの味を感じた

この日も寝たの四時ぐらいなのかなぁ...そんな事ある？流石に違う気がする
ツイートから寝た時間考えようとしても10:34とか表示されてておかしい，セミナー中に流石にスタバは行かない

四日目

朝ごはんはね，お気持ちをするとNo subで終わる

発表準備
iPadProを使ってイキりながら作っていくけど遠くからだと線とか見にくかったらしいですね
そうなる雰囲気は感じてたけど突っ切ってしまった

昼飯を食べる，夕飯はまだ

講義
当然量子コンピュータに興味があるので聞いていた
すごいよね，量子コンピュータ，見た目がかっこいい，マリオメーカー ~~おやすみなさい~~
講義してくれた人に見られたら○されるのではないかという不安がわりとすごい

発表準備の時間で当然みんなスライドを作り終わる

Writer:双子なABCがあるので当然出て全完する
当然発表準備終わってないので風呂に入った後作り続ける

チューターの方々がボードゲームする相手がいなくて帰ってしまい悲しい気持ちになった
Kmc○deくんとか○ni○nくんがコドフォ出るって言ってたので一緒に出ようとAを提出してWAする．人生終了
Kmc○deくん達の調子を適当に聞いたらコドフォ出てなかった．なにかがおかしい
このままレートを下げて人生終了です．お疲れ様でした

日課のスタバ，夏季セミに行く人は絶対毎日スタバ行きましょう

最後の晩餐 pic.twitter.com/ksnAdq5piZ
— 迷路 (@pazzle1230) 2018年8月18日

財布が写真に写っているのは，写真に財布を写すことでなくした財布を見つけた人がいたからですね

みんな死んだ目でスライドを作り続けていて，作り終わった人からボドゲみたいな感じになってた気がする
僕が持ってきたけど出し忘れていたコヨーテもやった
そういえば一〜四日目のどっかで人狼をしました，いつだったかは忘れました

最終的にチューター三人？と参加者四人？ぐらい？だった気がする
流石に書くのが遅すぎて記憶曖昧すぎた
ワードバスケットとコヨーテだけやりました
2つしかやってないからね
この日は何時ぐらいに寝たんでしたかね

五日目

寝てないんですけど
寝てないので当然そのまま朝ごはんも最終日だし食べに行った
2つのボードゲームでN時間消えた事実が怖すぎて怖い

発表ね
他の人達の発表は当然楽しみだったのでワクワクしながら ~~寝ていた~~ 見ていたんですけど面白すぎて気づいたら半分終わって昼飯になっていた本当に一瞬で終わったのでびっくりした
感覚的にはまばたきしている間に終わっていた感じでした

なんか午後の発表が始まってすこししたら三人組が発表を聞きにやってきた
ここでIOI代表が8人揃っているわけなんですがすごい，なんのイベントなんですかね
情報オリンピック委員会のイベントなんですが

自分の発表，去年もそうだったんですが本に書いてることそのまま詰め込んで詰め込むだけみたいななんの理解の助けにもならないものになってる感じがあって悲しい
発表に使ったスライド
10分って短い気がする

流石に午後は全部起きれたけど普通に難しくてなかなか理解できないね
まあわからないのでただ座り聞き続けるだけの人と化していた

終わった後，某チューター等数人でカラオケにいった
IOI代表三人の歌声を聞けるというすごい体験でした
僕はなぜか夏季セミ途中から喉が死んでいてやばかった

夕飯としてラーメン食べました
夏季セミ期間で何回ラーメン食べたんですかね，すごい

大学生になったらこういう機会がなくなりそうなので悲しい，来年も参加者として参加したい

2018-03-25

JOI'18春合宿参加記

競技プログラミング日常

JOI春合宿2018

JOI本選通ったため春合宿に行ってきました
これを書いているとき僕はまだ春合宿中です
何日目かあててみてください
文章の変化とかから頑張ればわかりそう

一日目

部活のえんやこらをした後に東大に入ってパスタを食べて偏差値を上げる
データセンターについた後、プラクティスを頑張る
1. なんかコミュニケーションなんですがコミュ障なのでなかなか通らない 2. エスパーなんですが、超能力者なので3回ぐらいで通る（超能力者なので）
3. Output OnlyなんですがOutputする、LinuxかCに慣れてないと厳しそう
4. 電　子　レ　ン　ジ 4問目なので当然一番難しい

この後オリセンに行き講義を受ける
簡潔データ構造面白そうとなるけど途中までだったので悲しい気持ちになる
頭がないので計算量とてつもなく気持ち悪いと思いました

ねる

二日目

起床できる
朝ごはんに向かうとめっちゃ混んでいる、やばい
社会性の塊なのでバスの出発時間には当然間に合う

競技1日目が始まる

一問目

木で頑張ろうみたいな
何もわからず何もわからなかったため何もわからなかった
部分点だけセグ木で取る

二問目

幾何で頑張ろうみたいな
とりあえず部分点だけ取ろうとしたらめっちゃバグるためめっちゃバグる
終わる

三問目

整数二個はやばいためやばい
横に置くのと縦に置くのとそのまま置くのの数を全探索$O(N³)$を書く部分点ですね
そのまま置くのを高速化すれば嬉しそうみたいなことが分かる
sum(nCk * 4^k * mPk)みたいな感じで二項定理とかで頑張ろうとするけど無理
ところで、そのまま計算することが小さければできるのでテーブルっぽく表示させて眺めます
なんか遷移が見えます（超能力者なので）
そこをDPにすることでなんとか満点がとれます

16+0+100でした

講義を受ける
双対難しいんですが慣れない5時間コンテストの疲れから序盤で寝てしまい途中から覚醒するも何も理解できないやつをする

解説

ねる

三日目

朝ごはんに行くとめっちゃ混んでいる（前日比INF倍、階段で下の階まで及んでいて何が起きているんだとなる）
社会性に満ちているのでバスの出発時刻+5分ぐらいに着く

競技二日目

一問目

整数二個じゃ～ん
眺める
わからないねと思い二問目三問目をやってきてから解く
わからなすぎるため小課題1の全列挙を書く
わからないね
全列挙ということは小さければ計算できるね
テーブル表示させよっか
にらみます
dp[i][j] = dp[i-1][j]*j+dp[i-1][j-1]*(i-j+1)という遷移が見えます（超能力者なので）流石にレッド超能力者にはブルー超能力者なので及ばず部分点で止まりました

二問目

Output Only
完全に見た目がマラソンだったので最初に焼きなましか山登りを書いて時間内回そうみたいな気持ちになる
実装がバグって2時間半ぐらいかかる（vectorはeraseすると添字ズレするのに気づくことできないね）
回すけどすぐ更新止まるし頂点がかたまっていて乱数バグってんじゃーんとなる（解説情報ですが本質です、青なので気づけない）
まあそのまま何回か実行して出しまくるとある程度取れる
裏で回すと重くなるためやるべきではなかった

三問目

難しくないですか？難しいと思います
前に人の1後ろに行くことにしばらく気づかずなんか詰まる
それに気づいたらなんか座標+iが嬉しそうなことに気づいてO(1)で出せるように頑張りにぶたんする
なんか定数倍か何かがきつすぎたのか、scanfやprintfに直しても通らずlong longをintにしたら通った

49+54+100=203でした

講義を聞く
純粋関数型データ構造
怖いね

解説を聞く
一問目がわからない

寝る

四日目

朝起きる
前日の教訓を活かして早めに向かう
あまり並ばずにすむ（並ぶ）

社会性が高いのでバスの集合時刻に間に合う

競技三日目

一問目

コミュニケーション
与えられた頂点に番号がついているグラフを、頂点に番号がついていないグラフで表現しろみたいな問題
無向グラフだと考えることで頑張ってとく
有向グラフなので簡単に解けるらしくキレる

二問目

びたろうくんだれやねん
DAGなのでダイクストラで部分点を取ろうとしてTLEになってハマるを無限時間続ける
DAGなのでDPで出来る
部分点が取れる
満点思いつきたかったね

三問目

パット見簡単枠現実不可能枠
お気持ちになることで小課題1解法で小課題2まで通す
終了
やばDP書くけど重複して数えていることに気づき死ぬ

講義を聞くチューターが少ないことが印象的でした

解説を聞く
三問目理解できない

寝ます

五日目

起きる
もう全然混んでいない
余裕のバス搭乗AC

一問目

2乗DPを書きます。部分点を得られます
セグ木DPを疑いながらわからないため諦めます

二問目

リアクティブですね
補集合で二分探索を疑うとわかりかけるけど考察して実装始めると記憶が消えるため何もわからない
終了

三問目

グラフ、全点始点でうまくダイクストラを前計算して良さそうなのいくつか持てば良さそうとなる
部分点1しか通らなくて終了する

8+19+12=39
春合宿に感謝を告げて終了
サンキュー春合宿

二問目、春合宿中に1か2を争う簡単さっぽくて人生終了
通してたらJAPAN2だったんだよなぁって永遠に言い続けて死んでいきます

六日目

チューター企画のSKIコンビネータがある
純粋に難しいため難しく、異世界の科学を異世界の言語で学んでいる気分になっていた
面白いので頑張りたかったけど圧倒的に頭が足りなかった
地頭の塊になりたかった

まあここまでで実質終了なため終了
五、六日目の夜にワードバスケットやコードネームをやって楽しみました、楽しかった

2018-02-11

JOI'18本選参加記

C/C++ 競技プログラミング日常

JOI本選参加記

JOI予選通過したため本選に行ってきたので参加記をたくさん書きます*1
結果としては100-100-13-31-5で249点でした、ボーダー上という雰囲気を感じてどっちに転ぶかわからず怖いです
とりあえず落ちたという暗示をかけて落ちても楽な気持ちで、通ったらとてつもなく幸せになれるようにしておきます

前日

宿泊をするため荷造りがある
夏季セミとは違い1泊のため難易度は下がっているが少なくとも7はあるため辛いがPCKなどで鍛えたので日が変わってからAC
これもう前日じゃないね

1日目

お昼ごはんを食べることにして食べるが、他の人は土曜日なのに学校があるらしくそれまで世界史を勉強する
全然進まない
難易度7を通す気持ちになりStrapを読む
一瞬わからない
しばらくわからない
家をでるぐらいになってようやくわかるけど難易度7でわからないのはまずい
お昼を食べる
うどんにわさびを全部とかしたら結構きつかったため全部溶かすのがおすすめです

TXに乗る
オタクなのでTXでパソコン広げるオタクになりStrapを実装する

バグる

結局通せないままつくばにつく*2
荷物をおいてプラクティスに行く
プラクティスの問題が開始前に見ていいらしいので見ると問題名から去年と同じとわかる
余裕をぶっこいて問題文見ずに開始を待つ
始まる

1問目、2問目、3問目までやるだけなのでやる
ここらへんで通ってるか確認しに行くと1問目が通っていない、オーバーフローです、人生終了
4問目をあー去年もやし先輩めっちゃバグらせてたやつだ！と言いながら書く

バグらせる
なんとか時間めっちゃかけて通す
5問目は半分全列挙なのでやるだけと言いながら書く

バグる

なんかupper_boundで添字-1したんですが謎の値が出るためM越えるかを場合分けして逃げる

終わったため他の人のところへ行くと、◯◯◯oooさんにEmacsというゲームソフトを教えてもらう
色々あってほんとすごい、Vimと敵対しているエディタだと思ってたけどゲーム機だったんですね

講義始まる
去年より良さげなところでやり、椅子で隠れるためどう考えても精進が出来る(JOI委員会の人へ、許してください)
Strapをなんとかして通し、EnJOIable logo designを通す
Telegraphを解説見ちゃったけど実装したい気持ちになるのでやると全然出来ないため死ぬ
講義終わる

多分夕ご飯
色々食べる
WAと書かれた名刺をもらうため終わりを確信する
食べ終わる

去年の教訓を活かし、即風呂をするとみんプロにより余り混んでいないことがわかりAC
風呂を上がったらもやし先輩の部屋に集まり何か考察しようみたいな感じになるけど雑談で終わる
一方僕はTelegraphが実装できない

0時を回ったため寝る
なかなか寝付けず、天井の緑の光に苛立ち始める
気づいたら寝ていた

二日目

目覚ましを6時半にセットしたはずが5時に起きる、眠気がやばい
とりあえずお腹痛めていたためトイレに行く
その後適当に時間つぶして食堂に行くとめっちゃ混んでてなんで競プロerがこんなに時間守ってるんだとなる
去年より鮭の塩加減は良くなっててよかった

本選会場に行く
なんか緊張ヤバイけど頑張るみたいな気持ちになる

始まる

1問目

うーん...やるだけ

2問目

うーん...頭良く出来そうだけど頭ないのでRMQで殴る
ここらへんで易化しすぎでしょ、やばやばってなる

3問目

おいおい苦手なやつ来たぞコレとなる(cf. yukicoderの双子のどっちか回のトランペットか何か)
グリッド状でうまくやるやつ苦手なのでとりあえず貪欲を書いてしまう
なんか部分点1が通る

ここで天才なので縦に使うときと横に使うときでしかブッキングせず、ブッキングした同士を辺で結ぶと二部グラフになることに気づく
この瞬間、フローシラバス外では...みたいな気持ちが何処かに消えるそしてhttps://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_cとhttps://mathtrain.jp/bipartitematchingが頭の中に入ってくる
フロー書けないため増加道探すの頑張ってかくぞ〜！ｗとなる
1時間がとける、なんか書けたつもりになってもWAなので無理っぽいとなり諦める
トイレに行く
あっ、DPでは？となり頭の中が昔の予選6のbitDP達で一杯になるも、右に遷移していくと流石に情報持ちきれないやろとなる(必要な情報がななめなので)
諦め

本選後の解説で斜めに遷移すればいいと言われ衝撃が走った
それはそうみたいな感じだけど常識覆される感があった

4問目

見る
4問目のグラフなんて難しいに決まってるやんけ...となる
けどどう見てもダイクストラは使いそうな雰囲気あるし行けそうみたいになる

部分点オタク精神を発揮して部分点1を見る
SとU一緒なら一番後ろの分岐点までの最短路を引けば行けるねとなる
ここでなんかスパゲティを書くことで同時に部分点2も同時に通る(なんで通ったかわかりません)

部分点3を見ると、ワーシャルフロイドやってくれ感バリバリに出ているため書きたくなるため書く
もしかしてこの部分点は全経路列挙してそれぞれに試せということなのでは？みたいな気分になりDFSを書く(おそらく間に合いません)
トイレに行く
書くとワーシャルフロイド意味ないなという気持ちになるためS,U,Vを始点にダイクストラをする
そして、経路復元しながら見ていったとき、ある頂点以降でUから、Vからの最短がわかるためメモ化DPできるのではとなる
PLLである頂点以降でのUから、Vからの最短の和が最小になるような組を持つ
行けるやろこれみたいになるもめっちゃバグる
なんかシグナル11とか行って全部REっぽくなったりもする
残り30分ぐらいでなんとなく致命的なバグはなくなるけど答えあわない

なんか明らかにおかしいところがあったので直す
部分点オタクのため関数に分けてたのもなんとなくmainに全部やる
残り10分ぐらいで、Uからの最短が最小、Vからの最短が最小、Uからの最短とVからの最短の和が最小の3つを持たないといけないことに気づき実装する
手が震え、日本語配列キーボードのためミスタイプが増える
13:00ちょい前ぐらいに最低限かけた気がしたので最終提出†ファイナルサブミット†をする
手元でコンパイルするとCEが出る、人生終了
帰りの電車の中で直してオープンに出すと通る、後5,10分ほしかったね

5問目

どこかの間で5点だけ取って退散した
包除原理と高速ゼータ変換こわいね

後二日ぐらいで結果出ると思うのでぼーっと待ちます
テスト勉強をする気は起きません
どっちかというと競プロやりたい

*1:"さんかき"をたく"さんかき"ます

*2:ば