AGC 046 E Permutation Cover

解けずに解説読んだ

本質

答えが-1かどうか <=> (max < 2*min)に気づくかどうか
[1, 1, ..., 1, 2, 2, ..., 2]のパーツができる <=> ↑の条件は全部できる

思考反省

方向性を間違えた

出来た: 辞書順最小なので判定条件出来たが使わなかった: パーツごとに独立間違えた方針: 先頭のごちゃごちゃとかがあるから判定条件を書き下すのは無理だろう　考えたくねえ -> きっとなんらかの貪欲が最適なことが証明可能で、これを実装すればいいんだろう正しい方針: とりあえず先頭にごちゃごちゃがない場合の判定条件を考える。

2020-07-30

競プロ実装テクニック

これはなに

実装力で戦える！～競プロにおける実装テクニック14選～ - Qiita に触発された

競技プログラミングでコーディングの際気を付けていること - うさぎ小屋を強く参考にしている

効果が高い or 一般性がありそう　なことから書いたつもり

重要なこと

「競プロのきれいなコードと業務のきれいなコードは違う」と定期的に唱える。未来の自分 or 他の人が読む必要がないことを仮定できるため、様々なバッドノウハウ(業務)が正当化される。(あえて過激なことを書くと、)「using namespace stdを使わない」などは逆にバッドノウハウ(競プロ)だと思っている。

-fsanitize=undefined,address / -D_GLIBCXX_DEBUG

#include <iostream>

using namespace std;

int main() {
    int a[10];
    cout << a[100] << endl; 
    return 0;
}

このコードは当然未定義動作だが、これを g++ main.cpp -g -fsanitize=undefined,address とコンパイルして実行すると

A.cpp:7:13: runtime error: index 100 out of bounds for type 'int [10]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior A.cpp:7:13 in

などと出てくる。他にも様々な未定義動作をキャッチできる。速度に影響があるが、手元で使わない理由はないと思う。他にも-D_GLIBCXX_DEBUGをコンパイルオプションに入れると色々検知するようになるが、macで使えない…

当然ながら g++ main.cpp -g -fsanitize=undefined,address などといちいち打つのは時間の無駄なので、aliasなどの機能を適時使うと良い。

コーディングスタイル

コーディングスタイル(インデント, space/tab, ...)は揃ってないより揃ってたほうがいい。有名規約で言うと Google C++ Style Guide に従っている人が身近では多い気がする。

インデントを手で整えるのは時間の無駄なので、エディタの自動整形に任せるべき。自分は以下の.clang-formatでvscodeに全部任せている。

BasedOnStyle: 'Chromium'
IndentWidth: 4
AccessModifierOffset: -2

# for competitive programing
AllowShortFunctionsOnASingleLine: All
AllowShortIfStatementsOnASingleLine: true
AllowShortLoopsOnASingleLine: true
AlwaysBreakTemplateDeclarations: false

いわゆる「きれいな」コーディングスタイルが(競プロで)常に正しいかというと怪しい。例えば1 * 2 + 3 * 4と1*2 + 3*4なら後者のほうが読みやすいと思う(自分はもう手癖で入れてしまうが…)。

using namespace std

575とも呼ばれる。std::があらゆるところから消せるのでコードがスッキリする。名前空間が汚染されるというデメリットがあるが、引っかかるのは無視できるぐらいの確率なので圧倒的にメリットのほうが大きいと思う。

マクロ / スニペット

マクロは俗に言う

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

みたいなやつ。僕はマクロは使っていないがfori / all でこれらが出てくるスニペットを登録している。マクロを使っても競プロなら何のデメリットもない。

とりあえず手でいちいちfor (int i = 0; i < n; i++)を書いているならば見直したほうがいい。

printfデバッグ /デバッガ

個人的には多くの場合でデバッガよりprintfデバッグのほうが速いと考えているが、デバッガのほうが強いときもある。assertで落ちたときにスタックトレースを確認するなど。僕は雑にlldbを使うが、これは改善の余地がある気がする。

printfデバッグするにしろ、printfをいちいちつけたり消したりするのは時間の無駄、僕は以下のようなマクロ(を強化したもの)を使っている。

また、vector / mapなども簡単に出力できるようにするといい。operator<<をオーバーロードするなど

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

goto

競プロでもgotoを使ってメリットが有るタイミングは少ないと思うが例外もある、有名な例は多重ループの大域脱出がある。

bool ok = false;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (solve(i, j)) {
            ok = true;
            break;
        }
    }
    if (ok) break;
}

が

bool ok = false;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (solve(i, j)) {
            ok = true;
            goto loop_out;
        }
    }
}
loop_out:

のように書けるというやつ。2重だとありがたみが薄いが、競プロでは平然ともっと多重のループが出てくるので、そういう時に強い。

bool ok = [&]() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (solve(i, j)) return true;
        }
    }
    return false;
}();

このようにも書け、自分はこちらをよく使う。

再帰ラムダ

普通にdfsを書こうとすると

vector<vector<int>> g;

void dfs(int v, int parent) {  
    for (int u: g[v]) {
        if (u == parent) continue;
        dfs(u, v);
    }
}

int main() {
    dfs(0, -1);
}

となるが、これを

int main() {
    vector<vector<int>> g;

    auto dfs = [&](auto self, int v, int parent) -> void {
        for (int u: g[v]) {
            if (u == parent) continue;
            self(self, u, parent);
        }
    };
    dfs(dfs, 0, -1);
}

と書ける。独特な記法を覚える必要があるが、処理を上から下へと書けるのは大きい。なお、ラムダ式は覚えると便利な事が多いので慣れると吉。

vector<vector<>>を短く書けるようにする

個人的おすすめ。V<int> / VV<int>でそれぞれvector<int> / vector<vector<int>>になるようにしている。便利。

2020-03-03

WTF C2 Triangular Lamps Hard 別解法

今回は、Nimberを使ってWTF C Triangular Lamps Easy / Hardを解いていこうと思います。

C1

このような問題では、操作で変わらない不変量を考えたくなります

具体的には $(x, y)$ に $\binom{x + y}{x} \pmod 2$ を書き込めば、 $(x \geq 0, y \geq 0)$ では不変量です。なのでこれを適切にシフトしたものを考えて、うまくやるとOKです

C2

先述の不変量は一般の場合ではあまり役に立ちません。なぜならば、1の数が少なすぎるからです。つまり不変量を求めたところで元の点に関して得られる情報量が少なすぎます。

じゃあどうするかというと、元々の想定解法では先述の不変量を同時に大量にばら撒きます。もちろん適切に計算できるようなばらまきかたをしないといけなくて、そういうことを考えると自然と $\bmod 3$ が出てきます。

今回はもっと情報量の多い不変量を考えることにします。

実際に、ある $a$ について、 $(x, y)$ に $a^ x (a+1)^ y$ を書き込むと、これは不変量になっています。ただし、要素は全て $\mathbb{F}_ {2^N}$ とします。 $\bmod 2$ でダメなら $\mathbb{F}_{2^N}$ というのは自然ですね。

この不変量により、 $a$ を原子根にすると、 $(a + 1) = a^s$ として、 $x + sy$ が求まります。もう一つ、他のaについても調べると、ある $t$ について $x + ty$ が求まります。

結果として、 $x, y$ が求まりました。

実装としては、 $F_{2^N}$ で離散対数を求める必要があります。ところで、最近Nimberで離散対数を求める問題が出ました: Problem - F - Codeforces　ちょうどいいですね。

実装例: Submission #10507304 - World Tour Finals 2019 Open Contest

2020-01-02

Library Checkerを支える技術

あけましておめでとうございます。これは Competitive Programming (2) Advent Calendar 2019 - Adventar の 14日目の記事です。あけましておめでとうございます。

この記事では、Library Checker の宣伝をします

Library Checkerって？

競プロのライブラリを整備するために爆誕したサイトです。特徴としては、問題が全部ライブラリを整備する目的に特化していること、ケースジェネレーター、チェッカーなどが全て公開されていることが大きな特徴です

中身を全て公開することにより

誰でも問題の追加が出来る
誰でもケースの修正などが出来る
CIに組み込める*1

などの、様々な利点を得ることが出来ます。理論上はO(使用人数)でケースが強くなっていくので、最強のテストケースが出来ると言う目論見です。

概要

こんな感じです

f:id:yosupo:20200101233401p:plain — こういう図をブログに貼りたかった

見ての通り、GCP(Google Compute Platform)で動いています。

一つ一つ紹介していきます

Problems

library-checker-problems で問題の情報を管理しています。

ジェネレーターとかは全部C++で、それをpythonから叩く仕組みになっています。目的上どの環境でも同じテストケースを吐き出すようにしないといけないので、とても苦労しています。(uniform_int_distributionは環境依存なんですよ、知っていましたか？)

Cloudbuild

図にやたら出てくるやつです。yamlファイルにコマンドを書き並べるだけで、githubにpushするたびに実行とかをやってくれるので乱用しています。今5種類ぐらい使っています。

ジャッジサーバー

dockerなどの既存のコンテナは時間計測 / メモリ計測がむずかったので、いっそのことと思い、unshare / cgroups / overlayfs などの(dockerの中で使われてる技術たち)を直接叩き、コンテナを作っています

unshare: プロセスからネットワークのアクセスを禁止したり、mountを分離したりしてくれるすごいやつ
cgroups: これがないと何も出来ない。プロセスのCPU、メモリ消費量とか諸々を制限してくれるすごいやつ
overlayfs: プロセスから/tmpとか変な場所にファイルを書き込んでも、パッとやるとそれらを一瞬でなかったことにしてくれるすごいやつ

ずっとサーバー借りてると高いので、preemptible(AWSのスポットインスタンスみたいなもの)を借り続けるという雑なことをしています。24時間(or もっと短い)で勝手に停止してしまうので、停止を検出したらCloud Functions(≒ AWS Lambda)で自動再起動、うまくいくのかと思いましたが、今のところうまくいっています。

SQL

Cloud SQLと言うフルマネージドのサービスでPostgre SQLを立てています。バックアップなども取ってくれているようなので慢心しています。

このサービスのコアで、全てが入っています。問題のテストケースもbytea型でそのまま入っています　ええんかこれ？

APIサーバー

(最近正式サービスとなった)Cloud Runで動いています。理由はApp engineだとgRPCが動かなかったからです。 apiv1.yosupo.jp:443 で動いていて、API一覧は library-checker-judge/library_checker.proto at master · yosupo06/library-checker-judge · GitHub です。(RESTではないので、GitHub - ktr0731/evans: Evans: more expressive universal gRPC client のようなgRPCクライアントを使わないと何も見れないです)

フロントエンド

言ってしまえばAPIサーバーを叩いて結果を出力するだけです。

APIサーバーを作る前はgoでSQL直接叩いてやっていたのを、API化と共にtypescriptとかそう言うのに置き換えようと思ったんですが、断念して今はgoでAPIを叩いてやっていっています。

おわりに

このプロジェクトは、いつでもみなさんの協力をお待ちしております。最近めちゃくちゃコントリビューターが増えて、嬉しい。普通のOSSよりは競プロ勢の人にとってとっつきやすいと思うので、pull requestsとかに興味があるけど、難しそうだし〜と言う人は、ぜひ！

明日(概念崩壊)はsaka_ponさんの競技プログラミングでも C# で簡潔に書きたいです。ありがとうございました。

*1:ざっくり言うと、自動で「ライブラリをちょっと修正するたびに全部の問題に投げ直す」ことが出来ます

2019-12-03

yukicoder No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│

基本方針

ガン見

maspypy.com

解法

最近ipad買いました(私事)

f:id:yosupo:20191203234110j:plain — goodnote

2019-11-12

Static Range Union Find

N頂点のUnion Findが与えられます。以下のクエリがQ個与えられます。

given l, r, dist: merge(l, r), merge(l+1, r+1), merge(l+2, r+2), ..., merge(l+dist, r+dist)

これを処理した後のUnion Findを計算してください

これは D: LCP(prefix,suffix) - 「みんなのプロコン 2018」決勝 | AtCoder の本質部分です(ネタバレ)

O(N α(N) + Q)で解けます。

Submission #8391439 - 「みんなのプロコン 2018」決勝 | AtCoder

2019-09-04

TTPC2019参加記

TTPC2019にチームyosupo(yosupo, yosupo, yosupo)で参加して、優勝しました

f:id:yosupo:20190904003306j:plain

前日

ここいる？*1

当日

コンテスト前

無(二度寝したので)

昼食

無(二度寝したので)

チーム決め

無(それはそう)

コンテスト

東　京　工　業　大　学と4年ぶりの再会

A

TTPC2020 たのしみ～(問題設定無視)

B

D言語なら正規表現があるんですよね→デバッグ出力、消し忘れ…

C

解けないから飛ばした

D

実験書こうとしたが、そういえば素数って奇数だったなって

素朴で好き

E

000
111
222

からちょっといじるとなんか出来た

F

最小費用流を貼ってグラフを構築しようとして、何かがおかしいことに気づいた

M

UKUNICHIAがFAしてるから開いた

抽象化ライブラリじゃ処理できないけど俺の全方位木DP実装力を見せてやるぜ→デバッグ、42分…

L

初感が(x * 100,000 + y)で分けたら良さそうだなぁだったから対して苦労しなかった　天才かも

半分全列挙だけど見たことない気がする

G

丁寧に場合分けをやった

O

とりあえず2冪から考えてみるか→普通に出来た

f:id:yosupo:20190904004546p:plain

BDDって31 * 31なんて処理できたっけ？って思ってたけど、経路数が少ないから(別の方法で)なんとかなるんですね(FPTじゃん)

C

再考したら普通に解けた

H

俺の平衡二分木ライブラリを見せてやるぜ→1年ぐらい使ってなかったため、使用法を完全に忘却…

動的Fenwick Treeでお茶を濁す

I

とりあえずQを素べきに分解して考えてたが、実は分解しないほうが見通しが良かった？細かいところを詰めずに実装を開始したら大変なことになった

J

Iの合間に解いてたので、パパっと実装

K

とりあえず手でケースを試しまくるとハミング距離(=FFT)が関係しそうなことがわかって、N=100,000 / 2.5sはいかにもFFTっぽい制約なので確信(は？)

とりあえず2種類のハミング距離を眺めて、大小関係がサンプルと一致したので提出…(競プロをやめろ)

MuriyarokonnNaNと4年ぶりの再会

N

問題設定がぶっ飛んでて好きとりあえず適当なのを投げたら全然ダメだった

懇親会

🍣が出てきて、嬉C

自分より若い人が大半で、もう気づいたら高齢者…(ホロリ)

話したことない人と喋ったので、満点！(コミュ障)

感想

久しぶりの5時間コンテストで楽しかったです。運営のみなさんありがとうございました。

~~AtCoderのせいで~~データ構造ライブラリが化石になってるんでちゃんと整備しなおさなきゃ…

*1:https://kenkoooo.hatenablog.com/entry/2019/08/31/084809