2020-03-09

競技プログラミング初めて3年経ちました

少し遅れましたが毎年書いているので今年も書きます。

去年の抱負の振り返り

まずは去年のブログで抱負っぽいものを書いたのでそれが達成できたかどうか見ていきましょう。

レート1900を目指す

f:id:nanae1914:20200309182856p:plain — AtCoderのレーティング推移

残念ながら2019年以内には達成できませんでしたが、2020年に復帰したコンテストで過去最高パフォ(2400!)を叩きだすことができ、見事1900台に乗りました。
半年くらい期間が空いていてその間競プロはほとんどやってなかったのにこの成績は運が良かったとしかいいようが無いです、実際その後のABCで２連続水パフォで今は1800台に落ちてしまいました。
しかし一時的にとはいえ1900にはいきましたし、この抱負は半分くらい達成したといってもいいんじゃないかな、と思っています。

競プロslackに参加する

こちらはまったくと言っていいほど参加しませんでした……というか存在を半分忘れておりました。
今見てみると稼働もあまりされていないっぽく、やはり競プロerにとってはslackよりtwitterなどのほうが相性が良いのかなと思っています。

作問

こちらも結局一問も作りませんでしたね……言い訳すると問題案自体はあるのですが、問題文を作ったり解説を書いたりテストケースを作ったりテスターさんに依頼してやり取りしたり……と結構作問って大変なんですよね。
なのでなかなかモチベが高くないと取り掛かれないのですが、そもそも半年くらい競プロサボって別のことやっていたりしていたのでそこまで出来ませんでした。

……というわけで抱負の達成率は1/3未満といったところでしょうか。酷いですが、まあ抱負ってそういうものですよね。

何やってたの？

レートグラフを見ると去年の9月から今年の2月まで大きなブランクがあるわけですが、この時期コンテストにすら出ず何をやっていたかという話ですが、Slay the Spireというゲームに没頭していました。
store.steampowered.com

競プロとは関係無いのですがこのゲームが本当に面白くて、過去一番か二番目くらいにハマったゲームなんじゃないかなあと思います。
ローグライクとデッキビルディングを組み合わせたゲーム、ということでランダム性によって毎回組むデッキを臨機応変に変えざるを得ないんですがそれが高いリプレイ性を生み出しています。
だからといって運ゲーかというとそうでもなくそのランダム性に対応できるような多種多様なコンボも用意されていて……と魅力を語ろうとしたのですが本題と逸れるので止めることにしました。
これのA20心臓という最難関モードで勝率をいかにして高められるか、みたいなことをやってました（が大したレベルではないです）。競プロerでもちらほらやっている人は見受けられましたね。
ソロゲーで高難度で戦略性も高くてとにかく面白いので、運要素があるゲームが嫌いとかじゃなければ競プロerにもおすすめしたいです。

あとTwitterを見返していて思い出したのですが、ハイパーロボットボットを一時期やっていましたね。こちらはほんとに一時期、多分一カ月くらいだと思いますが……
あれもなかなか刺激的で面白かったです。パズルはあまり得意じゃないんですがとにかく参加しまくることによってＡＣ数一位になったこともありました。
こちらはもう今は稼働していないみたいですね。

競プロ記事の充実

最近はAtCoderも人気が出てきてこの前のABCで参加者数が7000人を超えるなど競プロ界隈もどんどん進歩しているなあ……と遠巻きに見ていて思います。
その影響で（？）最近はかなり競プロ記事を書いてくれる人が増えていて凄く良いですよね。
この辺はやっぱりけんちょんさん(drkenさん）がQiitaで初心者向けの記事やAtCoder蟻本版などの記事をたくさん書いてくれたのが皮切りになったのかなと推測しています。
qiita.com

最近ではE869120さんという高校生レッドコーダーの方が上達のガイドラインという記事を書いてくれて話題になっていましたね。ありがたいです。
私もこれを読んで黄色コーダーを目指したいですね……
qiita.com

あとAtCoder Problemsなんかも凄く使いやすくなっていますし（半年ぶりに使ってとても進化していてびっくりしました）競プロを学びやすく取り組みやすい環境がどんどん整えられているなあと感じました。
その分参加者に求められるレベルも上がってきていて自分もちゃんと勉強しないと取り残されていきそうな感じがします。
（セグ木とか高級なデータ構造だし青になるまで勉強しなくていいでしょという認識だったのですが、今は水色で必修科目？みたいな。流石にそこまででは無いですかね？分かりません）

今年の目標

そろそろ今年の目標を書いて締めくくりにします。今年は２つです。

黄色になる

上でも少し書いたのですが今年は黄色を目指してみたいです。去年は黄色になるビジョンが見えないので1900で、と言っていたのですが去年の６月くらいから、というか新ABCになってから結構黄パフォも出せるようになってるんですよね。何か分からないですが新ABCとは相性が良いのかもしれません（普通にダメなときもあります）。
一時的に1900に乗せることも出来たし全くビジョンが見えない状況から「もしかしていけるのでは？」くらいにはなってきたので目指してみようかなと。

AtCoderのAC数を1600にする

いつだったか、「AtCoderで〇色になるまで何問解けばいいか」みたいなツイートが流れてきました（どのツイートでこの画像を拾ったかは忘れました、すみません）。

f:id:nanae1914:20200309193821p:plain — 各色を達成できる確率

これによると1510問解けば黄色になれる確率が60%らしいです。なのでキリ良く1600問くらいを目標にしてみました。
今計算してみたところ、現在のAC数が1269で残り日数が297なので一日平均1.11問くらい解けば1600問達成できるみたいです。割と目標としてはちょうどいい感じじゃないでしょうか！

競プロを継続する

これが一番難しいですよね……継続さえ出来ていれば、少なくともAC数1600は達成できるはずです。
ただ去年みたいに他のゲームとかにドハマリしてしまうと……あとは生活環境とかも変わるのでその辺はどうなるかなぁと言ったところです。

と書いていたら目標が３つになってしまいました。
それではこの辺で、読んでくださってありがとうございました。

2019-02-25

C - Synthetic Kadomatsu

ABC119 ABC 全探索 DFS 4進数 bit全探索

atcoder.jp

この問題は個人的に過去のABC-Cでも一二を争う難しさではないかと思いました。一言で言うと「全探索するだけ」なんですが、その全探索の仕方が独特というかいくつかの気づきが必要な問題だと感じました。

まず一つが「延長・短縮・合成の操作の順番を自由に入れ替えても最終的な状態や総コストは変わらない」ということです。延長・短縮の操作が入れ替え可能なのは明らかで、延長と合成も「竹Xを延長した後、竹Yと合成する」としても「竹XとYを合成した後、その竹を延長する」としても一緒だと言うことが分かります。短縮と合成についても同様です。

「操作の順番を好きなように入れ替えられること」を「操作が可換である」と言ったりもします。競プロにおいてはしばしば何か（数列とかグラフとか）に対して操作を繰り返すような問題が出ますが、「与えられた操作が可換であるかどうか？」は常に気を配りたいポイントですね。

そして延長・短縮・合成の中で一番複雑な操作が合成です。操作が可換だと分かったので「合成を先に全てやってしまって、残った竹に延長・短縮をやってA,B,Cを作る」と考えると少し考えやすくなる気がします。（もちろん複雑な操作は最後にまとめてやってしまう、という考え方もあると思いますしその方が考えやすくなる問題もあるかもしれません……その辺はアドホックなのかな、少なくとも今回は合成を先にやってしまう方が楽になりそう、というのは勘みたいなものが働いている気がします）

なのでまず合成を考えることにします。合成の順番も関係無いので、次のような操作に置き換えて考えると分かりやすくなりそうです。

合成: １本以上の竹を選んで、それらを全て接続した竹を作る。このコストはk本の竹を選んだとすると $10(k-1)$

このように考えておくと「合成した竹を合成する」のは一回の合成で置き換えらえることも分かるので、合成した竹を合成するのは考えなくてよくなります。（１本の竹だけ選んだものも合成と呼んでる点に注意です）

次に大事なポイントが「合成した竹を使わないのは明らかに損」ということです。ここでいう「合成した竹を使わない」というのは作りたいA,B,Cのために割り当てない、ということです。これも明らかで使わないんだったら最初から合成しなかったことにしたほうが明らかにコストが小さくなるからです。

これらの考察から合成の仕方として考えるべきは、全ての竹について

Aのための合成に使う
Bのための合成に使う
Cのための合成に使う
何もしない

という4つの場合全てを考えれば十分だということが分かりました。

これで合成に対して考えるべきことは終わりました。後は、

(Aのために使われた竹の長さの総和とAの長さの絶対値) + (Bのために使われた竹の長さの総和とBの長さの絶対値) + (Cのために使われた竹の長さの総和とCの長さの絶対値)

が延長・短縮にかかるコストの最小であることは明らかです。

最後に計算量を考えます。

各竹について選択肢が4つありますから、全ての場合を試すと $4^n$ 通りです。指数時間は一般的には遅いと思われていますが、今回の場合ですと $n \le 8$ とかなり小さいので最大ケースでも $4^8 = 2^{16} = 65536$ 通りとなり十分計算可能であることが分かります。

ここまで分かれば解ける人も多いと思いますが「 $4^n$ の全探索ってどうやるの？」という人も少なくないと思います。やり方は思いつく限り3通りあって

深さ優先探索(DFS)
4進数で全探索
bit全探索(2進数の全探索)でゴリ押し

です。オススメ順に並べてみました。

深さ優先探索

一番素直だと思うのがこのDFSによる解法です。今回のような各点での枝分かれがk本みたいな状況に限らず、もう少し複雑な枝分かれをする場合にも応用が効きます。放送でchokudaiさんも言っていましたが汎用性がかなり高いのでスラっと書けるようになっておくとよいです。

部分的なコードは以下のような形です。

// idx は今見ている竹の番号、 gc はこれまで合成に使った竹の本数
int dfs(int idx, int la, int lb, int lc, int gc) {
    if (idx == n) {
        if (la == 0 || lb == 0 || lc == 0) {
            // A, B, Cの合成の竹に使われた竹が存在しないときは有効な回答ではない
            // このときは答えに影響が起きないような十分大きな値を返すことにする
            return inf3;
        }
        else {
            return abs(la - a) + abs(lb - b) + abs(lc - c) + 10 * (gc - 3);
        }
    }
    int res = inf3;
    // idx番目の竹を A のための合成に使う場合
    res = min(res, dfs(idx + 1, la + l[idx], lb, lc, gc + 1));
    // idx番目の竹を B のための合成に使う場合
    res = min(res, dfs(idx + 1, la, lb + l[idx], lc, gc + 1));
    // idx番目の竹を C のための合成に使う場合
    res = min(res, dfs(idx + 1, la, lb, lc + l[idx], gc + 1));
    // idx番目の竹は使わない場合
    res = min(res, dfs(idx + 1, la, lb, lc, gc));
    return res;
}

4進数で全探索

次に4進数による全探索です。こちらはややテクニカルな印象がありますが、dfsのような関数を書かずforループを回すだけでさくっと書けるのがポイントでしょうか。bit全探索を知っている方はこちらの解法を思いつきやすい気がします。

以下のコードでは(0 -> 使わない、 1 -> Aに使う、 2 -> Bに使う、 3 -> Cに使う)と対応付けています。その他の部分はdfsによる解法と大きな違いは無いです。

int ans = inf3;

foreach (s ; 0 .. 4^^n) {
    int la, lb, lc;
    int gc;

    foreach (i ; 0 .. n) {
        if (s % 4 == 1) {
            la += l[i];
            gc++
        }
        else if (s % 4 == 2) {
            lb += l[i];
            gc++
        }
        else if (s % 4 == 3) {
            lc += l[i];
            gc++;
        }
        s /= 4;
    }

    if (la == 0 || lb == 0 || lc == 0) continue;
    ans = min(ans, abs(la - a) + abs(lb - b) + abs(lc - c) + 10*(gc - 3));
}

bit全探索によるごり押し

上記2つと比較してスマートでもなく自然でもないのであまりオススメできない解法です。それでもなぜ書いたかというと、私がコンテスト中に書いたのがこの方法だったからです……

あまり多くは語らないので雰囲気だけ掴んでもらえたらと思います。 $2^{3n}$ くらいかかってそうでやばくね？って思いますが、よく考えるとs,t,uの各bitが立つ本数が高々1本しかないので実は $4^n$ に収まっているという奴です（多分）

(2019.02.26 追記) と思ったんですが $4^n$ に収まっているというのは嘘な気がしてきたのでやっぱり参考にしないでください

long ans = inf6;

foreach (s ; 1 .. 1 << n) {
    long tmp;

    int la;
    foreach (j ; 0 .. n) {
        if (s & (1 << j)) {
            la += l[j];
            tmp += 10;
        }
    }
    tmp -= 10;

    foreach (t ; 1 .. 1 << n) {
        auto ttmp = tmp;
        int lb;
        if (s & t) continue;
        foreach (k ; 0 .. n) {
            if (t & (1 << k)) {
                lb += l[k];
                ttmp += 10;
            }
        }
        ttmp -= 10;

        foreach (u ; 1 .. 1 << n) {
            if ((s | t) & u) continue;
            auto tttmp = ttmp;
            int lc;
            foreach (e ; 0 .. n) {
                if (u & (1 << e)) {
                    lc += l[e];
                    tttmp += 10;
                }
            }
            tttmp -= 10;
            tttmp += abs(la - a) + abs(lb - b) + abs(lc - c);
            ans = min(ans, tttmp);
        }
    }
}

おわりに

分かっているように書きましたが、実際コンテスト中は難しすぎてテンパってしまい、いろいろと最悪でした。一番下のコードになった理由も「合成する竹としない竹で分ければいいのか」→「いや、A,B,Cの3つに分ければいいのか」→「いや、使わなくていい竹もあるんじゃん」となってネストがどんどん深くなってしまったからです（しかも計算量は何となく大丈夫でしょみたいな感じで本当に適当だった）

いろいろと反省すべき点が多いコンテストでした。ABC-Cでも難しく感じたら焦らずに、考察はじっくりやらないとダメですね。

2019-02-24

No.794 チーム戦

数え上げ yukicoder

概要

N 人(偶数)の人がいて、i 番目の人は整数 A_i を持っている。これらの人々を使ってペアを N / 2 組作りたい。ただし、各ペア(i, j)について A_i + A_j <= K が成り立っていないといけない。

そのようなペアの分け方は全部で何通りあるか？

制約

$2 \le N \le 2 \cdot 10^5$ , $N$ は偶数
$1 \le K \le 2 \cdot 10^9$
$1\le A_i \le 10^9$

考察

まず人の順番は無視していいので、 $A_i$ は昇順にソートしておくことにする。すなわち $A_1 \le A_2 \le \dots \le A_N$ が成り立っているものとする。

「２人の和がK以下」という制約が無ければ簡単で、答えは

$\binom{N}{2} \cdot \binom{N-2}{2} \dots \binom{2}{2} / (N / 2)!$

となる。最後に $(N / 2)!$ で割らなければいけないことに注意する。なぜなら、例えば[1,2,3,4,5,6]とあるとき、({1,2}, {3,4}, {5,6}), ({1,2}, {5,6}, {3,4}), ({3,4}, {1,2}, {5,6})...のように同じ分け方でも順序が違うものを重複して数えてしまうからだ。

上の考察は無駄ではなくてKが十分大きいときはこの答えがそのまま使える。より厳密に言うと、 $A_{N-1} + A_{N} \le K$ であるとき上の答えに帰着される。

こういうのは相方の候補数が少ないもの、つまり $A_i$ が大きい順に考えてその候補数を掛け算していけばよさそうな感じがする。 $A_i$ の相方の集合より $A_{i-1}$ の相方の集合のほうが大きいので、 $A_i$ がどれを相方にしても、 $A_{i-1}$ の相方候補は1つ減るだけだから。（これを逆順にやってしまうとややこしくなってしまう……ということをABC114-Dで学んだ）

そうやりたいんだけど、問題は $A_i$ が $A_{i-1}$ をペアにした場合とかを考えると、次に $A_{i-1}$ を考えるのではなく $A_{i-2}$ を考えなければいけない、みたいになってかなりややこしくなってしまう。どうすればいいんだろう……？

よく考えると $A_i$ が $A_{i-1}$ とペアになれるっていうことは、 $A_i + A_{i-1} \le K$ が成り立っているということで、これは上の「制約が無いパターン」に帰着されていることが分かる。すなわち、 $A_i + A_{i-1} \le K$ が成り立っているときは、前のi人は自由にペアを組めるのだ。

なので、 $A_i + A_{i - 1} \le K$ がどこまで成り立つか？でグループ分けすると考えやすくなるのではないか、という考えが浮かぶ。すなわち $A_i + A_{i - 1} \le K$ を満たす最大の $i$ をmとして、前半組m人、後半組N - m人と分けてみよう。すると前半組のm人はどの２人を選んでもペアに出来るし、後半組のN-m人はどの２人を選んでも絶対にペアに出来ないことが分かる。ということは後半組は相方を前半組から取ってこなければいけない、ということも分かる。