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

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

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