TTPC2019参加記

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

前日

ここいる？*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冪から考えてみるか→普通に出来た

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)

これが

こう

建て方

めんどそうだなぁと思ったけど、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, 10⁹ + 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は

• maroon: gedit
• sigma: CLion
• yosupo: CLion
• CLionのキーバインド: emacs + (ctrl+c, ctrl+v, ctrl+z)=(copy, paste, undo)

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

DDCC 2019

コード部門

• A: なんかバグった、素直にD言語のgroup関数を使うべきだったかも、遅かった
• B: 平衡二分木使うか悩んだけどしばらく考えたら貪欲で普通に解けた、遅かった
• D: もう典型、segtree.hとmatrix.hを貼って終わり、速かった
• C: みんな解法は簡単というけどそんなことない気がする、実装の方は2ヶ月後にICPC WF行く人幾何担当がこれを解けないとチームをクビになる、でも遅かった(は？)
• E: コンテスト開始からチマチマ考えていた、1080までは見えていて、残り時間との兼ね合いでそこで諦めることにした、見積もりを間違えてて1110が取れた、速かった

DISCOの人が順位表の凍結にこだわっていそうだったので、せっかくだからすっとぼけることにした。

昼食の時はCが大変なことになって終わった(終わったとは当然文字通り問題が終わった=ACという意味です)とか、Eも提出だけはした(提出した結果0点だったとは言っていない)とか言ってた

装置実装部門

予選: なぜか壮大なものを実装しようとしていたが、そもそも正の点数を取ることすら相当難しいと気づいて方針転換。これが幸いしてギリギリ滑り込めた

10位に入れていそうだったので、予選が終わった後の休憩時間ではすぐに本戦のためにプログラムを改善開始

本戦はesper力、観察力、実装力、盤外戦術力みたいなのが全部問われる不思議なコンテストだった

pre本戦:

• 向こうの口ぶり的に最速で移動するとどうせ大変なことになる設定なんだろう
• 最高速を減らすことのメリットが少なすぎる、いじるべきは加速減速時間のみでいいだろう
• 普通に実装すると45度移動になるが、水をこぼさないように運ぶなら明らかに直線的に動くべきだろう
• AとかBに移動するとき、真下まで行かずにちょっと前で止まると少しだけお得
• pre本戦は自分の挙動を確認する以上に、他人の挙動を確認するのが大事だろう
• submissionの点数を見ることで、n週ギリギリの調整が出来る

あたりには気づいていて、これらを踏まえて適当に良さそうなのを実装して、pre本戦は紙とペンを持って気づいたことをなんでもメモを取ることにした

また、pre本戦ではわざとダメなの送って気づいたことを秘匿しようかとも思ったけど、ぶっつけ本戦で挙動が終わるリスクを考えたら素直に送った方がいいと判断した

以下はpre本戦中の考察や、人を見て気づいたこと

• E -> Aは水がないんだから最速で移動すればいい(また、A -> Bは水が少ないから少し早くてもいい)
• AとかBに移動するとき、真下じゃなくてちょっと前で止まると少しだけお得だが、ここでギリギリを攻めると水がうまく給水できずに零れる
• 4週しかない、5週は時間的にまず不可能だろうし、3週だと水が少なすぎる気がする
• pre本戦でもっと情報を収集するべきだった(sugimは各週ごとに速度を変えて水のこぼれ具合を調べていた)

また、自分のコードはほとんど自分の予想通りに動いていることが確認できて嬉しかった、特に直線的に動けているかは不安だったので

これを踏まえて、その後の実装タイムでは

• まずは、E -> Aの速度をmaxにし、A -> Bの加速度はB -> Eの2倍にすることにした(水量が半分だから)
• 5週でまともな量は運べないだろうこと、3週だとどれだけ上手くやっても4週に勝てないだろうことを確認
• 理論値480では勝てないだろうと予想して、理論値と加速度のバランスを雰囲気で調整していくことに
• ↑pre本戦一位(自分)が水をかなりこぼしていたのに435であったことを加味すると、450 ~ 460程度は平気で出るだろうと予想した
• また、ここらへんでA -> Bの加速度が2倍ではお話にならないことに気づく(ビーカーの形的に水量が半分でも水位は結構高くなる)、謎の仮定(めちゃくちゃでした)を置いた計算の結果1.43(1 / 0.7)倍にすることにした
• 理論値528で挑むことにした、理由は特になくて、注ぐ時間を100ms刻みで選ぶと480, 504, 528, 552になるんだけど、504だと流石にしんどいだろう & 552は欲張りすぎだろうみたいな判断から)

結果は予想より全然水がこぼれず500.5になった、preよりこぼした量が減ったというのは驚きで、多分もっと理想の理論値は上だったっぽい(下手したら552まで行くかも)

AGC 029

A

隣り合う要素をswapして数列をsortする最小回数は転倒数と呼ばれています

B

• 2で割れる回数でグループ分けして←いらない
• 大きい順にマッチしていく

という解法で解いた、1個目いらない

証明

xとマッチできる値たちのうち、x以下のものは1種類しかない、というのが本質

最大の値xとマッチできるyが存在しなかったらx消していい

存在したらx - yでマッチ作っていい(x - yを使わないマッチングがあったとしても、x - yを使うマッチングに変換できる、なぜならx - yを使わないならxはぼっちで、yはx以外の何かとマッチしている、よってy - 何かをばらしてx - yを足せばいい)

C

そもそもどういう文字列をつくっていけばいいか考える

二分探索をする

シミュレーション

D

E

実装を詰めなかったため、破滅

F

twitter

CODE FESTIVAL 2018

本選

対策

特になし

結果

ふつう

原因

Hの得意度は参加者の中でトップクラスだった自信があるため，Iを速やかに解ければ勝っていたと思うが，Iに90分掛けたためどうしようもないね

対策

転生？

りんごの挑戦状

対策

• ペイントで様々な色を作って眺める
• トップページを暗記する，日時を重点的に

結果

どうしてこんなことに

原因

R:G:Bの比だけを注意していて，明るさという概念を忘れていた。|R-r| + |G - g| + |B - b|ならR:G:Bの比は本質じゃないんだよな

対策

そもそも地理系に弱いので詰んでいませんか？詰んでいますね(チーム戦にしませんか？)

リレー

対策

例年はふわっとやってふわっと終わるみたいな戦略だったけど，今年は真面目に

最初の5問に2人 * 5で取り掛かって後の5問は臨機応変にみたいな(いややっぱりふわっとしていない？)

結果

2位

原因

戦略が上手く行った，とかではなく他のチームの話を聞くとそもそもチームメンバーが優秀だったっぽい(完)

対策

文句なし