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

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

TTPC2019参加記

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

f:id:yosupo:20190904003306j:plain

前日

ここいる？*1

f:id:yosupo:20190901232411p:plain
うんち

当日

コンテスト前

無(二度寝したので)

昼食

無(二度寝したので)

チーム決め

無(それはそう)

コンテスト

東　京　工　業　大　学 と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

プロキシを建てた

背景

マンションのネットが、マンション共有で安い！みたいなやつ

なんかネットが不安定だった

最近、不安定を再現する方法が分かった(研で使っているサイボウズをノートパソコンから開く)ので、真面目に調べることにした

原因

共有部分のルーターのIPマスカレード制限(多分)

要するに一度にめっちゃたくさんのサイトとか画像とかにアクセスすると死ぬってやつで、サイボウズは細かい画像が多い & http1.1 で死んでいたっぽい

対策

内側と外側にプロキシを建てた(内側: Raspberry Pi / 外側: GCP)

f:id:yosupo:20190711002838p:plain
これが

f:id:yosupo:20190711002853p:plain
こう

建て方

めんどそうだなぁと思ったけど、GitHub - ginuerzh/gost: GO Simple Tunnel - a simple tunnel written in golang を使ったら一瞬で立った　すごい

client(raspi)

./gost -L http://:1080 -F http+mws://yosupo:$PASSWORD@$SERVER_IP:1080

server(GCP)

./gost -L http+mws://yosupo:$PASSWORD@:1080

難点

http / httpsプロキシの設定が必要

  • なんか自動設定できるらしいが、DHCPサーバーをルーターのじゃなくて自前で用意しないといけなそうで、面倒…

お金がかかる

  • GCPのサーバー自体は他の用途にも使っているものだからいいんだけど、ネットワーク(下り)に料金がかかる

Gifted Infantsのチーム戦略について

メンバー

yosupo, sigma, maroon

戦略

明確な戦略は特になかったです(完)。

いくつかのルールを守りながら(守らないこともある)、毎回適当にやってた感じです

ルール

  • 今誰がどの問題を読んだか、考えたか　の紙を作る
  • 特に得意ではないジャンルを無理にやらない 例(yosupo: DP, 109 + 7, sigma: JOI, maroon: AOJ-ICPC)
  • 解いた後でも苦手な実装だったら人に投げる
  • ちゃんと実装を詰める
  • ちゃんと声かけをする
  • 必要なら厳しい言葉をためらわない
  • 人がある程度燃えたら他の人が強制的に介入する
  • 実装が重かったら相談する(想定よりはるかに重い実装方針を考えていて、相談すると綺麗になるってことが結構ある)
  • 解法が 難しい / 未証明 / 貪欲 / 計算量が怪しい などの場合は相談する
  • 有名問題っぽい見た目になったら他の二人に知ってないか聞く

あたりかな　明文化されていたわけではないです。とにかく相談を沢山するチームだったと思います。

練習セット

5時間セットをやる→反省する を繰り返したぐらいで、特に特別なことはしてないです。ちゃんと動き方とかの反省をするといいかもしれません。

Petrozavodsk Camp(9)

  • セット数: 11日9セット(oooxoooxooo)
  • 難易度: [ICPC-Japan, INF]
  • 開催地: Petrozavodsk, オンライン(有料)
  • 注意点: 凍死

MIPT Camp(6)

  • セット数: 7日6セット(oooxooo)
  • 難易度: Petrozavodskと同じかちょっと簡単
  • 開催地: MIPT, 同時開催で世界のどっか(年による)
  • 注意点: パスポートを忘れない

Opencup(11)

  • セット数: 15 ~ 20セットぐらい
  • 難易度: [ICPC-Japan, INF], 時々ゴミ
  • 開催地: オンライン(無料)
  • 注意点: 上2つのキャンプと同じ問題セットが使われることがある, 終了が遅い

知っての通り別にOpenじゃないです

Ejudge(15)

  • セット数: たくさん
  • 難易度: 様々
  • 開催地: オンライン

キャンプとかOpencupの過去問が詰まったジャッジです。

これもOpenじゃないです

その他(13)

コドフォのGymとかRUPCとか夏合宿とか

ライブラリ

ライブラリにファイル容量制限とかがあって、それを超えて大変だったりした(html + @printerで作ってたら、印刷するOSによって容量が変わった なぜ？)

www.dropbox.com

単体法 出典: GitHub - koosaga/DeobureoMinkyuParty: 럭스를 럭스답게 든든한 연습헬팟 더불어민규당

少なくとも行列式がバグっています

環境

ある程度は本番に環境を合わせて練習したつもりです。 突然環境が変わると上手くいかなくて悲しい気持ちになりがち(経験則)

個人的には キーボード >>>> エディタ >= OS >>>> その他　ぐらいの重要度

キーボード

  • 英字配列以外の選択肢はないです。日本語配列は今すぐやめましょう。ポルトガル配列はやめろ
  • 高速にタイピング出来る人がいないとライブラリ写経が絶望的になる

OS

  • Ubuntu以外の選択肢はないです(フラグ)。バージョンは最新のLTSでよさそう
  • yokohamaはほとんどデフォルト設定だと思いました。WFではなんか見た目とかが弄られていました。

エディタ

  • visual studio / atom が使えないことに注意。本番で使えるエディタ一覧はサイトから見れます
  • 色々設定をする場合、それだけ時間を失うことに注意する必要があります
  • 理想的には3人でエディタ, 設定を合わせることですが、あまり強制しようとすると喧嘩になります。

Gifted Infantsは

でした。カオス。CLionはデフォルトで色々上手く動くのでいいです。でもノーパソだと発熱がすごい。

プリンター

印刷のタイムラグを表現するために、「ファイルをアップロードして1分後にダウンロード出来るようになる」サイトを作って使っていました。あんまり意味なかった気がする

おすすめ

CapsをCtrlに

setxkbmap -option ctrl:nocaps で出来ます

ターミナルを簡単にリセット出来るように

alias c='tput reset'

コンパイルオプション

-Wall -Wextra -Wshadow -DGLIBCXX_DEBUG -ftrapv を使う

check.sh

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

make $1
for f in tests/*$1*.in; do
    echo '#### Start ' $f
    ./$1 < $f
done

みたいな、コンパイルしてサンプルを一括で全部試せるシェルスクリプトを用意すると便利です。

Google hash code 2019 Final

Google hash code 2019に参加してきました

hash codeって？

google主催のコンテストで、GCJみたいなものです。一番の違いは形式で、2-4人チーム、パソコン無制限で短時間(予選:4時間, 本戦:5時間)というコンテストになっています。 予選は一発で、上位から、人数の総和が150人ぐらいになるまで進出らしいです。

ということからわかるように、GCJ Finalなどのtop25コンテストよりはるかに進出しやすいコンテストな気がします。

交通費

交通費、ホテル、食費のうちいくらか出すとサイトには書いてあります。 僕らがもらう予定の交通費は、全額ではないけど大半、ぐらいです。詳しく知りたい人は直接聞いてください。

環境

ファイルの共有はdropboxを使用しました。短時間なのでgitの旨味がほとんどないからです。

ディレクトリは

- common・
     - common.h
     - random.h
- yosupo/
     - main.cpp
- sigma/
     - A.cpp
- sugim/
     - A.cpp
- maroon/
     - A/
          - main.cpp

みたいな感じです。common.hには問題のファイルからの入力、出力、スコア計算などを書き並べ、全員importします。

戦略みたいなのはなくて、分担したり協力したりをぬるっとやりました。

結果

🌞

感想

5時間で4人4台チームコンテストすると、もうめちゃくちゃになります(チーム戦とは？)

事前に誰が何をやるかとか、もはや完全に分割して別のケースを解くとかするといい気がします。

あとpast gloryはしっかり優勝してて、さすがだなあって思いました。

余談1

Mac book pro(2018)を使っているんですが、最近いろんなキーがチャタリングを開始して、本戦がしんどかったです。 space, nあたりが酷い、対策されたって聞いたのに…

余談2

GWだったのでダブリン->イタリア->ドイツの大型旅行にして、今イタリアにいるんですが、パスポート失くしました。