2019-09-17

JAG夏合宿2019参加記

参加記 ICPC2019

JAG夏合宿2019に参加しました

行きの電車内で宿泊所が咲の聖地だということを知り、少しテンションが上がる特に何もしなかったんですが

https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20

清澄高校 pic.twitter.com/4xMWCT9yC9
— こるとん (@ILoveTw1tter) 2019年9月14日

https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20

最初の参加者自己紹介のときに「risujirohはまだ来てません」と言う羽目になったこういうの言うの恥ずかしくないですか？遅刻しないで

Day.1 okimochi(kort0n, risujiroh, idsigma)

PCとキーボードを並べると思ったよりスペースが狭いので、運営の方に許可を取った上で机を繋げる社会性の欠片も無い感じになる

とりあえず

A:idsigma

B:kort0n

C:risujiroh

で読んで、分かった人から実装しようとなる

読むと分かったので実装して通すそこそこ速かったのでFAかな？とわくわくしていたが、four-tに1分差で負けていたゆるせねえ...

A,Cは暫く掛かりそうだったので、後ろの問題を一通り読むことにする

後ろを読むとH,J,Kの解法が生える今日冴えてるな〜天才だな〜

risujirohにCの相談をされる話を聞いていると自己解決していた良かった(?)

その後idsigmaさんがAを通す Kの実装を投げると、問題文の誤読を指摘されて解法が爆発したは？

JはUnionFindとフローの写経が必要なので後回しにしたかったが、流石にHより楽なのは明らかなのでこれをやることにする伝達も面倒なので自分でやることにする

risujiroh「写経しようか」

kort0n「いや、自分で写経するわ」

と言ってドヤ顔でコーディング席に座ったところで、(普段使い慣れていない)US配列キーボードであることを思い出す

kort0n「ごめん、写経頼むわ...」

写経パート以外は軽いので、写経してもらうと流石に通る

Dをrisujirohと詰めていると、連立合同方程式を解けば良いということが分かる書けますと言われたので任せると通る

満を持してHの実装に入る大まかな解法は以下の通り

列は、B列ずつM/Bブロックに分ける
各ブロックについて、対応するbの値をvectorに突っ込んで、ソートしておく
N*(M/B)個のブロックについて、書かれる数字の数を計算するこれは、さっき作ったvectorを使って二分探索すると、1ブロックあたりO(Blog(max a_i) * logB)で出来る
クエリをdの値昇順で処理するブロックは適当に飛ばして、各ブロック内では真面目にやる

(これ改めて見ると計算量ダメですね...これでやってはいけない...)

H実装中に他の2人がEを詰めたらしく、解法を共有されたので、「ただしそう」と言う「log取るか素数mod取るか」とかでちょっと相談したら、誤差ヤバいしlogはダメだねとなる実際logでやろうとしてハマったチームもいたらしい logで解決したくなる気持ちはかなり分かる...

Hは実装終わるまでどうせ暫く掛かるし、一旦PCを譲る最初modを1つのみでやってWAを吐くも、modを2つにしてrisujirohが通すなんか有名素数は対策されていたらしく、有名じゃない素数mod1つで通したチームもいたらしい？

再びHに戻る実装をして投げるとTLE 桁数を求める関数を極僅かに高速化したり、バケットサイズを適当に調整したりして何度か投げるもTLE

risujirohがKは二次元畳み込みで解けますと言う Hは泥沼感が出てきたので代わるとKが通る

再びHに戻るバケットサイズの調整の為に、前半パートに掛かる時間等が知りたくなるこういうときはsubmitデバッグが便利なんですね

submitデバッグをすると、なんかバケットサイズとかの問題じゃなくて計算量落とさなきゃ無理なのでは？という気がしてくるここでHを諦める何とTLEとsubmitデバッグを含めて14submit... PC長時間占拠したしこれは完全に戦犯ムーブでしたね...

順位表を眺めると、Gを通すべきだという話になる考えても何も分からない

risujirohがdpテーブルは想定解通りにちゃんと定義出来たようだが、実装ミスか遷移式ミスか何かで一生サンプルが合わず、コンテストが終了する

結果は7完最速の8位(オンサイト4位)で冷えっ冷えだった誤読嘘解法人に投げるし写経要求で人の時間奪うしHで一生PC占拠するし、完全に戦犯をした...

コンテスト後てんぷらさんに「おきもち冷えすぎだろ」と煽られるキレそう

解説を聞く Hで浮動小数点数的な考え方をすると計算量がlog(max a_i)落ちるのか〜天才だな〜

感動しながら再実装して投げる

f:id:kort0n:20190916225514p:plain — やーめた

コドフォに出たかったが、回線難民で出られなかったので、談話室のボドゲ会に参加する楽しかった

最the高 pic.twitter.com/DDEOU1HYfD
— こるとん (@kyort0n) 2019年9月14日

海底探検の最終ラウンドで欲張って無事帰らぬ人となりました

Day.2 Seica_no_okimochi(kort0n, risujiroh, seica)

「後ろどんどん人増えますね〜」とか談笑してたら突然前に人が増えて非常に厳しい気持ちになった
— こるとん (@kyort0n) 2019年9月14日

idsigmaさんは私用で不在につき、seicaちゃんをチームに招き入れる

問題が難易度に依らず全問シャッフルらしいので、とりあえず各人がmod 3で問題に目を通すことにする

自分はA, D, G, Jを読むことになる Aが簡単なので取り組むことにする

連結成分を調べたいのでUnionFindを写経する見事5箇所ほど写経ミスする US配列を許すな

写経が終わると流石に通る seicaちゃんが「Eがギャグ」と良い、サッと通す

Dが解けたので実装する肺が0個と判定されたときの出力を誤って1WAするが通る

Fを考察していたseicaちゃんが、「†一般マッチング†に帰着された」と言い始める嘘だろ？と思いつつ話を聞くと、†一般マッチング†に帰着されたことが分かるまあこの問題固有の上手いやり方があるかもしれないし、手を付けるかはオンサイトAC状況を見つつ決めようという話になる(オンラインACはライブラリコピペで終わるので参考にならない)

CGHJあたりを適当に読んで考察する Cは何となく最小費用流っぽい話になりそうだなーと感じる GHJは何も分からない...(Jの勝利条件が分からないのは流石に酷すぎる)

risujirohがIを解いて実装する WAを連続で出していて辛そう暫くすると解法を共有される

聞いた感じ合ってそうだけどなー「あまり通ってないし、とりあえず後回しにしよう」と言ってトイレに行く戻ってくるとジャッジミスがあったらしいと言われるかなしいね

暫くすると、seicaちゃんがjの最適戦略を導き出すこれを使って勝利条件をまとめる最初自分のミスで20分くらい無駄にしたは？

勝利条件を元にして、seicaちゃんが答えを表す式を立てる変形するとN-1乗和の公式に定数倍掛けたものを足したり引いたりした形に変形出来ることが分かるので、多項式補間で出来ると分かるこれをrisujirohが実装する

暫くサンプルが合わなかったが、標本点を選ぶ際に偶奇性に注意しないといけないことに気付いてサンプルが合う AC これは熱かった

Bについて話し合うが、全員口を揃えて「これ最大流問題を部分問題として含むし、フローは明らかに無理だし、何かおかしくないか？」と言うということでclarを投げる

f:id:kort0n:20190916235350p:plain — 仰る通りでございます。

「全てのedgeのcapが等しいならdinicは速い」ということを知らなかったせいで、このようなクソclarを投げてしまいました。clar対応の皆様、本当に申し訳ございませんでした...

Cを改めてちゃんと詰める最小費用循環流っぽいことをやればokだということが分かる Primal-Dualの写経をrisujirohに頼んで、Cを実装する添字ミスで1WA吐くも無事AC この時点でオンサイト1位になって思わず叫ぶ

Gを詰めていたseicaちゃんが実装に入る risujirohにO(N^2)でいいからHのdp解を書いてみてくれと言われるちなみに一旦計算量の悪い解を僕が書いて、その数式をrisujirohが変形して高速化するというのは弊チームの常套手段で、RUPC2019 day3の赤黒そーるじぇむでもこういうことをしていました

O(N^2)解のdp遷移式を立ててrisujirohに渡すこの時点で残り時間は30分ほど計算量が落ちたときにすぐに実装出来るように階乗逆元等の準備も兼ねて、埋め込みも視野に入れつつ、Gで辛そうだったseicaちゃんにPCを譲ってもらって、HのO(N^2)解を書き始める

この辺りで(これまで完答数が並んでいた)右前のHeno_Worldに風船が届けられる様子が視界の端に映って絶望する

O(N^2)解を書いている途中で、risujirohが期待値の式をO(N)で求められる形への変形に成功するしかし二乗和の期待値は間に合わず、6完で終了となった

f:id:kort0n:20190916233007p:plain — 6完最速全体4位オンサイト2位

7完のHeno_Worldとの差はFだったどうやらFが一般マッチングになるという考察は間違っていなかったようなのだが、Heno_Worldは一般マッチングライブラリが無いにも関わらず、その場でフルスクラッチで書いたらしい heno_codeとかいう男気持ち悪すぎる本当に無理だ

僕がどう見ても一般マッチングだからやめろって言ってる横でやむなくくんが提案したアルゴリズムをへのくんが実装して通していたので本当に意味がわからない
— てんぷら (@tempura_cpp) 2019年9月15日

コンテスト後は懇親会があったやはり(日経コンやDDCC等の規模のものと比べて)参加者が少ない懇親会は、色々な人と話そうという気分になれて良いですね

choKOdaiの方々とお話し、「高速ゼータ変換は名前が格好良い」という話で盛り上がる高速ゼータ変換って格好良くないですか？

突然じゅっぴーにじゃんけんを挑まれたので戦って勝つと、大量の名札を押し付けられた上に、カツアゲ呼ばわりされるなんで？

JAG懇親会、友達みんなこるとん(@kyort0n )さんにカツアゲされた(இдஇ; ) pic.twitter.com/ktTFB1ofp2
— じゅっぴー (@juppyjappy) 2019年9月15日

懇親会後はwriterを務めたABCがあった談話室で大勢の人が参加していたので、同じくwriterだったbeetさんと眺めていた

????_code「良い問題でしたね E問題だけに」

らてさんと初めてお会いするらてさんは完全に酔っ払っており、名乗ると突然

「うんこるとんじゃん！！！！！！！！」

と言われた(参考:TTPC2019参加記 - kort0nの日記)

その後5回くらい「やむなくさんですか？」と聞かれた「えーだって黒髪で眼鏡掛けてるし」と言われたやむなくは眼鏡を掛けていなくないか？

potetiさん曰く、らてさんはやむなくに会ったことが無いらしい何から何まで意味が分からない

Day.3 kaisan(kort0n, risujiroh, heno_code)

idsigmaさんとてんぷらさんが同時に作問チームに入っている日があることは分かっており、okimochiとHeno_WorldのContestantがちょうど3人であった為、組むことにした

こるとんさんにどんな問題投げればいいか分からねえ
— heno (@heno_code) 2019年9月15日

わかるなあ(得意ジャンルという得意ジャンルが無い人なので)

当日コンテスト会場に集まると、henoがビズリーチTシャツを着ているこれは...?

f:id:kort0n:20190917000828p:plain

f:id:kort0n:20190917000842p:plain

そう、これはHeno_WorldがICPC2019国内予選ラスト40秒でEを通し、我々から奪い取った(?)企業賞のTシャツであるゆるせねぇ...

「ふざけやがってチーム解散だ」と言うと、「じゃあチーム名解散にしましょう」と言われるこうして謎チーム名"kaisan"が誕生する何？

とりあえず

A:heno

B:kort0n

C:risujiroh

で読むということになるまた、D以降はhenoがメインのコーダーを務めるということになる弊チームは基本的にコーダー担当のような人はいない為、少し新鮮で楽しみ

henoはAがすぐに分かったようで、書き始める

自分も数分掛かったがBが分かる

risujirohにCの相談をされる無証明だが流石に正しそうな貪欲解法...

「実装量は多分同じくらいで、Cは解法が少し怪しいけどBは流石に合ってるからBからやろう」と言う

Aが通った後Bを実装するドヤ顔でsubmitする

f:id:kort0n:20190917001624p:plain — Cは解法が少し怪しいけどBは流石に合ってるからBからやろう

本当に死にたくなった

更に悪いことに、自分のコードのバグが見つからない最悪だが後ろを読んでいるhenoに相談して、デバッグをしてもらう

無事バグを発見してもらう Cをrisujirohが通した後、Bを通す 3完は2位以下に結構な差を付けたハイスピードで1位だったらしい

しかし、自分がhenoに相談して止めてしまったこともあり、ここで実装キューが空になるつらい

F(risujirohが得意そうなタイプの数え上げ)、G(期待値ゲー)、I(数学ゲー)は自分よりrisujirohに任せるべきなので放置自分はDEあたりを読むことにする「Dが燃やす埋めるで解けました」と言うと、henoに「この形は二部グラフじゃないと無理」と言われ、risujirohに「制約的に間に合わない」と言われるごめん...

risujirohがJのN=2べきでの構築に成功する 2べき以外で失敗することは証明出来てはいないが、まあそれっぽい結果だしとりあえず投げてみるしかしWA

相談も挟みつつ色々考えていると、自分とrisujirohでHの解法が生えるしかし実装が重そうだなぁ...

henoに解法を伝える

kort0n「でもこれどうやればいいんだろうね UnionFindでマージテクするけど、そのときそれぞれのUFに辺の情報を持たせて...」

heno「あ、実装方針は任せてください」

た、頼もしい...

そうは言いつつ結構時間が掛かるだろうし、とりあえず他の問題を読もう Dはよく考えると2-SATの形になるねでも辺がかなり多くなりそうで...

heno「サンプル合いました」

...は？

heno「通りました」

この男本当に無理だ気持ち悪すぎる

Jを考えると、それっぽい解法が生える N=4, 6, 8で手元で試すと正しく構築出来る

これをhenoに頼んで実装してもらうすると、N=10で破滅することが分かる死んでくれ

その後risujirohがGを解く henoが実装すると見事AC

再び実装キューが空になる henoも考察を始めると、henoがEを解き、実装を始める

自分は再びDに戻ると、辺を貼るパートが3^N全列挙で出来て、実は辺がそんなに多くならないことが分かる

risujirohがIを考察すると、綺麗な畳み込みの式になって解決する(僕としてはこれが解けるのもかなり気持ち悪いんですが...)

何とここに来て3問ほぼ同時に実装キューに突っ込まれるこれは興奮した

henoがEをバグらせた為、印刷して一緒にデバッグをするその間にrisujirohがIの実装を始める

一緒にデバッグをすると(結局はhenoがほぼ自己解決したのだが)バグが見つかり、Eを通すその直後にrisujirohがIを通すこれで単独7完で1位に

その後はhenoがDの実装を始める残り時間的にあとは実装が重い問題を解いても意味が無い為、解ければ実装が軽そうなJをrisujirohと考えるしかし解けない Dの実装も間に合わず、時間切れになる

f:id:kort0n:20190917005225p:plain — 7完で優勝！

AC数はeiyatonariと同じでしたが、ペナ差が効いて優勝しましたやったー

その後はJAGの方+potetiさん+risujirohと万豚記に行きました「茄子豚ピリ辛炒め」を注文したら、連続部分文字列であるところの「酢豚」が出てきました

#JAGSummerCamp2019 pic.twitter.com/SgXgbXzKV0
— こるとん (@kyort0n) 2019年9月16日

楽しい3日間でした JAGの方々、作問チームの方々、本当に有難うございました。

2019-09-01

TTPC2019参加記

参加記

前日

りあんさんとおぎんぎんさんとシナモロールと4人で麻雀を打ちました

神 pic.twitter.com/c4llKVULpD
— こるとん (@kyort0n) 2019年8月30日

もう一回張ったけどダメだった pic.twitter.com/yuB1FZoAmK
— こるとん (@kyort0n) 2019年8月30日

犯罪をしました

当日

会場に着き、運営からのチーム説明や会場使用上の注意等を聞いていると、チームメイトのシナモロールからDMが飛んできました

ご丁寧にチームアカウントが作成されていました。

シナモロールがやりました #ttpc2019 pic.twitter.com/N5gnuQmKZX
— こるとん (@kyort0n) 2019年8月31日

「アイコンに丁度良い画像無い？」と言われました。ねえよ。

f:id:kort0n:20190901003757p:plain — アイコンだけはオンサイト感溢れる微笑ましいものになりました

うんち屋さんってなんだよ (当然の疑問)
— えでゅふぉを埋める (@homuhomucomp) 2019年8月31日

コンテスト開始

実は前日の麻雀の際に軽く相談をして、「シナモロールが前半の問題を通し、その間にkort0nが後ろで簡単なものを探しておく」作戦を取るという話になっていました

しかし小学生2人組はこのチーム名を解説スライドに載せたくなってしまった為、

こ「FA取りたくね？」

シ「分かる BかCあたりでFA狙おう FA狙いで最初の1問だけ実装して」

こ「ok」

となりました。

開幕Bを開きます

これは開始地点を2重に回して、それぞれの部分文字列がokyo,echであるか調べればok!FAは貰った！

サンプル実行！

Segmentation fault (core dumped)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　終
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　制作・著作
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　━━━━━
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ⓃⒽⓀ

結局元の作戦に戻って、G以降を読むことにしました

G:これは出来そうただ細かいところ詰めないといけないからすぐにやるべきではない

H:絶対データ構造ゲーだ...

I:ノーチャンではないかもしれないが、他の問題やってからでいい

J:うーん出来そう(しかしこのとき何となく考えていた解法は完全に嘘)

K:はいヤバ枠(←は?)

L:もう開かん

M:苦手分野多分ヤバ問題ではないと思うのでシナモロールに投げたい

N:要はユーリ君が整数を選べるということが大事っぽい出来るのでは?(←は?)

ここまで読んだところで、Dまで通したシナモロールにEの構築を投げられる 30分くらい？掛けて通す

後ろの方の問題が全体的に難しめだし、前半6問は簡単枠とは言えEFあたりは骨のある問題だろうし、とりあえず2人でFを通そうという話になる

Fを読むこれじゃんとなる

実はコドフォで3日前にグループバチャをした問題に、かなり似ている問題がありましたこれは無向グラフで、V, E<=3000の問題

この問題の想定解は「合流地点と離れる地点を探索O(V^2)」だったのに、今日のFはほぼ同じ問題設定でV<=1e5になっているこれはどういうことだ...

2人で分からん分からんと言い合う有向グラフであることを使う？でも有向グラフであることが良い性質を持っているとは思えないぞ？

Fで詰まって数十分後、おもむろに制約を再確認したシナモロールが気付く

f:id:kort0n:20190901010011p:plain — ん？？？？？

DAGやんけ！！！！！！！！！！！！！！！！！！！！！！！

頭を抱える DAGなら流石に出来そう
考える

出来ません

数十分掛けてようやくまともなdp解法が生える

実装して投げる WA

泥沼感が出てきたので、6完で終わることは無いだろうし後ろに手を付けようという話になる

順位表を見るとOが沢山通っているのでOをやろうと言われる Oって何だっけ？そういえばOだけ読んでないな

Oを読むこれじゃんとなる

幅がギリギリだったので無理やり分岐路を詰め込んで、マジックナンバーをコードに埋め込みつつ無理やり通す

そういえばOの実装はこうやりました
形が汚いので何となく分かると思いますが、実装が酷いですね...#ttpc2019 pic.twitter.com/o0yCfb31WN
— こるとん (@kyort0n) 2019年9月1日

次は、自分がGを考え、シナモロールがFを考えるという話になる

GがO(N^2)から落ちねーと唸っていると、シナモロールに「違う文字に変更するペアの数で全探索をすると、各答えが綺麗に累積和の形になる」と言われて、確かにと答える実装すると通る

流石にそろそろFから目を背ける訳には行かなくなってくる

考えていると、自分がさっき投げたdpが、"基本的に"最適であることが完全に証明出来てしまうあれ？

流石にコードの内容的にもバグらせているとは思えないし、おかしいなーと言っている

こ「これ何で落ちてるって話になったんだっけ？」

シ「こういうの(w<x<y<z)」

コードを読み返す 2つのルートが1度も合流しない場合を考えていませんでした................................................................................

直すと流石にACする

ここからが困る

「H、セグ木でマージテクすれば間に合いそう」

「それMLEしない？」

「動的セグ木でやればMLEしないし動く」

「確かに出来るじゃん」

「動的セグ木使える？」

「使えない」

「そっかぁ」

でHが終わる

相変わらずK不可能にしか見えない病を患っているのでKはやろうとしない

Lは開かない

Nは詰めれば出来ると思っていたが、順位表を見て流石にやめる

ということで、残りがIJMになる

相談した結果、残り時間的にもあと1問通せば御の字だろうし、お互いに通せそうな問題を頑張って考えようという話になる。

自分はJを頑張ることにするシナモロールはMを頑張る

頑張るが解けません解けません

終了20分ほど前になると、解法が分かっても実装が重いであろうMは諦め、Jが分かれば実装は軽い問題であることに期待して、2人でJを考える

考えるが解けません解けません

終わり際になってシナモロールに「こういう遷移計算でいいんじゃないか」と言われる

こ「うーん、多分正しくないし、仮に正しかったとしてもN<=10^9だから間に合わないんだよね」

シ「え、N<=10^6でしょ」

こ「え？」

f:id:kort0n:20190901012210p:plain — え？？？？？

本当に神バランスの良セットだったと思います。東京工業大学の皆様、FUTURE様、有難うございました。

2019-07-13

ICPC2019国内予選参加記

参加記 ICPC2019

ICPC2019国内予選に参加しました結果は5完最速で4位でした模擬国内予選がチームブン回って5位で、実際には模擬国内予選に参加していない同格クラスのチームも多くかなり心配していたので、本当に安心しました・・・

f:id:kort0n:20190713005108p:plain — 最終結果

前日まで

模擬国内予選で構文解析が弊チームの圧倒的弱点であることが判明した為、ここから当日までこんなバチャも立てつつひたすら構文解析やってました

前夜

去年の国内予選の構文解析問題「数式探し」の誤読(各数字1桁とは限らないと思っていた)に気付くこれなら出来そうだなあと言いながらやる 2時間程かかって絶望する「明日の構文解析、Cあたりに自明で出るか、Hあたりに不可能で出てくれ〜〜」とか言いながら布団に入る

ところで僕はイベント前夜は全然寝られない人なんですよね。2時間ほど寝付けず布団を温めていました。

当日

1限があるせいで4時間くらいしか寝られなかった休講にしろ

東大の国内予選では、プリンターは会場にあるものを他チームと共有するか、或いはチームの私物を持ち込んで使用するということになっていました 20チーム近くいるこの会場ではプリンターの使用待ち時間も痛く、ちょうどボーダー上にいるであろう我々は少しの時間も惜しむ為、プリンターを僕が持ち込むことになりました

プリンターを持って駒場着マジで重かった腕が破壊された

プリンターを起動して無線LANに繋ごうとする

あれ？eduroam繋げられないんだけど

どうやらこのプリンターはeduroamやUTokyo-Wifiを拾うことが出来ないらしい(なんか通信規格とかの問題？らしい) この辺から顔が引きつり始める

idsigmaさんが生協にUSBケーブルを買いにいくその間に適当にリハ通す

戻ってくる繋ぐプリンターが認識されない...

この辺からいよいよヤバいという空気が流れ始める

色々やるとPCがプリンターを認識してくれる問題ページの印刷ジョブを投げるとプリンターが印刷を始める

「あー良かった！」

「何とかなったね！」

「じゃあ他の準備しよう」

などと笑いあっていると、明らかに問題文ではない謎の文字列が印刷されて出てくるは？

いよいよチームから完全に感情が消えておきもちになるコーチにチェックを貰う為の準備も必要なので、この辺で私物プリンターの使用を諦める何で持ってきたんですか...?

意地が汚いので、部屋内唯一のプリンターまで徒歩2秒の席を確保するその後も他ユーザーアカウントのファイルが見られるようになっている等のトラブルを皆で必死こいて調べながら何とか対処してギリギリチェックが間に合う確かこの時点で16:20くらいだった

本番

開始直後は各チーム問題を印刷するので当然プリンターが混む一番最初に問題文の印刷権を手に入れる為、問題データをpdfファイルに変換してUSBファイルに突っ込むムーブを無限回イメトレしてた後ろ見てなかったけど多分うちが一番速かったと思います

Aは流石に無なのでそのまま実装してAC なんとFAだったようで2つの企業賞を頂けましたやったね

直後にBをidsigmaさんが実装に入り、Cをrisujirohが考察するとりあえず後ろを読むことに

Dはすぐには分からないけど暫く考えれば分かりそう

このEやりたくないですね誰がやるんですか？絶対僕がやることになるやつですね？

F難しそう何だこれ

Gよく分かんないこれもゴリゴリシミュレーション系？でもそんなのGに来るか？(まだ構文解析ということに気付いていない流し読みが過ぎる)

幾何がHだと分かる (risujirohが)幾何が強く、FGあたりに(うちがギリギリ通せるくらいの)難問で来ると爆アドだったので少し悲しくなる

しかしその直後にGが構文解析だと気付く明らかに見た目ヤバそうだしこれそんなに解かれないだろやったね

idsigmaさんがBをAC 全体5番目だったらしい速い

Cが少し実装を詰める必要がある問題だったらしいので、Dが出来た気になった自分が実装に入る

この時点では「押す必要のある回数が最も少ない場所の必要回数を+m回するこれをnループやればok」とかいう今思い返すと完全に狂ってる解法を生やしていたよくこれで実装しようと思ったな

実装残り2行くらいになったところで、「いやこれ候補2箇所あったらやり方によってはおかしくならない？てかそもそもこの解法おかしくない？」と気付く明らかに反例は作れそうなのだが、反例を頑張って考えるより20分のペナを差し引いてもジャッジくんに今すぐ教えてもらった方がプラスになると考えて投げる当然WA

ここ生きててごめんなさいペナ pic.twitter.com/ea41Uhzs1Y
— こるとん (@kyort0n) 2019年7月12日

恥です。

明らかにやべー解法だったので、ソースコードと入力と出力を印刷してPCをrisujirohに譲ることにする

ところでDの入力はこれです

f:id:kort0n:20190713012725p:plain — これが数十ケースくらい

これを印刷するとこうなります

f:id:kort0n:20190713013142j:plain

バカか？

これで印刷代500円くらい取られました金返してくれ...

そしてこんな入力見せられても当然何も分かりませんでした何で印刷したんですか...?

考えるとO(N^3)のdp解法が降ってくる risujirohがCを通したので実装に入る実行にそこそこ時間掛かったけど無事AC

僕がDをやっていた間に他の2人がEの考察を詰めていてくれたらしくて、やるべきことを伝えられる「じゃあよろしくね」と言われる

f:id:kort0n:20190713014104j:plain

3箇所くらい途中でバグらせつつも、40分くらいで実装+デバッグ完了実行に10分くらい掛かるも無事AC ここ完全に神懸かっていた...

f:id:kort0n:20190713014539p:plain — ペナ差でBBQにも勝っていたらしい

その後は全員でFを考えて始める誰も良い解法が思い浮かばない

PCが空いているのも勿体無いので、小さいケースでの実験コードを書き始める

これを無限にバグらせる本当にE実装したんですか...?

実験コード書き終わった頃には終了10分前流石にもう不可能なので、国内予選突破ほぼ確定を喜び合いながら雑談していた

合同バチャや模擬国内予選等々で全敗のheno_worldより上にいたのでへへーんとか言ってたら残り40秒でE通されて逆転された犯罪だろ

アジア地区予選へ向けて

そういう訳で、無事アジア地区予選に進めることになりました

WFに進むためには学内1位になる必要がある訳ですが、圧倒的格上のチームが2つ存在するのは厳しいですね

1チームだけなら何らかのアクシデントで運良く勝てることも無くは無いと思うんですが、2チームあると...参ったなぁ...

今年はセミファイナルというステージが存在するという噂もあるらしい？これは情報を待つしか無いですね

来年以降出る人へ

プリンターはちゃんと家で動作確認しろ

2018-12-20

競技プログラミングのすヽめ

これはGUTアドベントカレンダー2018の12/20分の記事です。他の記事はこちらから

----おことわり----

この記事ではあえて専門的な用語は使わずに、高校卒業レベルの数学・情報・プログラミングの知識さえあれば読める記事に仕上げることを目標としています。既に競技プログラミングやコンピュータサイエンスに精通している方が読むともどかしく感じる箇所も多いかと思いますが、ご容赦願います。

こんにちは。今年参加したGUTの活動は #GUTウニ紅白戦2018 のみなので、僕のことをご存じない方も大勢いらっしゃるかと思います。こるとんと申します。

今年のアドベントカレンダーでも、最近ハマっている趣味について書こうと思います。

皆さんは「競技プログラミング(通称:競プロ)」をご存知でしょうか？

AtCoderの説明に困ったらこれ使ってください pic.twitter.com/50s3czCxFy
— chokudai(高橋直大) (@chokudai) July 9, 2018

競プロの大まかな内容は、上ツイートに記載されている通りです(上記ツイートは、競技プログラミングのコンテストを開催する会社「AtCoder」の取締役社長のchokudaiさんによるもの)

...とは言え、これだけだと詳細が分からないと思うので、順に解説していきます。

競技プログラミングでは、定期的に「コンテスト」が開かれます。コンテストでは数問の数学的な問題が出題され、参加者達はそれを制限時間内にプログラムを使って解き、出来るだけ多くの得点を獲得することを目指します(得点の計算方法はコンテストによって異なるのでここでは割愛)。その結果に応じて参加者の中で順位が付けられます。

ここで注意するべきなのが、大抵の場合コンテストの参加者が考えるべきことは、「答えの求め方」ではなく、現実的な時間内に答えを上手く求めることが可能となるような、解の効率的な探索方法を考えることであるということです。

どういうことでしょうか。例えば、以下のような問題を考えてみましょう。

問題1

プログラムの実行時間制限:2秒

長さ $N$ の整数列 $a_1, a_2, \cdots, a_N$ が与えられます。次に, $Q$ 個の整数の組 $l_i, r_i\left(i = 1, 2, \cdots, Q\right)$ が与えられます。各 $l_i, r_i$ について, $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めてください。

制約

$1\leq N \leq 10^3$

$1\leq Q \leq 10^3$

$1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)$

$1 \leq l_i \leq r_i \leq N \left(i = 1, 2, \cdots, Q\right)$

例

$N=5$

$a_1=1, a_2=3, a_3=6, a_4=2, a_5=5$

$Q=3$

$l_1=1, r_1=3$

$l_2=5, r_2=5$

$l_3=1, r_3=5$

に対する答えは

貴方に求められているのは、制約を満たすような如何なる入力 $N, a_1, \cdots, a_N, Q, l_1, r_1, \cdots, l_Q, r_Q$ が与えられても、正しい答えを実行時間制限以内に出力するプログラムを書くことです。

「プログラムの実行時間制限」なるものは一先ず無視していただくとして。如何でしょうか。

恐らくプログラミングの経験がある方にとっては造作も無いでしょう。与えられた $l_i, r_i$ について $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を愚直に計算するプログラムを書けば、この問題は解決出来ます。

では、以下の問題は如何でしょうか。

問題2

プログラムの実行時間制限:2秒

制約

$1\leq N \leq 10^5$

$1\leq Q \leq 10^5$

$1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)$

$1 \leq l_i \leq r_i \leq N \left(i = 1, 2, \cdots, Q\right)$

一見何も変わっていないように見える？いえいえ、制約のところが僅かに変化しています。

とはいえ、問題の内容は全く変わっていません。ということで、こちらの問題も、与えられた $l_i, r_i$ について $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を愚直に計算するプログラムを書けばok...

とはなりません。何故か。

皆さんご存知の通り、コンピュータは単純な処理を高速に実行するのが得意です。数千個の数の総和計算もあっという間にこなしてくれます。

では、どれ程多くの処理を要求しても、コンピュータはそれらを必ず一瞬で解決してくれるのでしょうか。答えは当然"No"です。コンピュータの処理速度にも限界があります。

それはどの程度なのか、一言で言い表すのは大変難しいです。ここでは、「『基本的な処理』を $10^8$ 回以下しか行わないならば、大体2秒以内に処理が終わる」ということにしましょう。

「『基本的な処理』って何だよ」と仰る方、ごもっともです。ここでは、以下のようなものを指すことにしましょう。

・2つの数の加減乗除の計算

・2つの数の比較

この辺について語り始めるとキリが無いので、今回はこういうことで...

このことを踏まえた上で、先程の問題1と問題2を振り返ってみましょう。

問題1と問題2において、前述の方法により問題の解決を試みる場合、それぞれ最高でどの程度の回数基本的な処理が必要になるのでしょうか？

各問題で、 $N, Q$ について、最小値と最大値が決まっています。恐らく $N, Q$ いずれも大きい方が大変でしょう。ここでは, $N, Q$ がそれぞれ最大値を取る場合を考えます。

$l_i, r_i$ はどうでしょうか。 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めるのが最も大変なのは、 $\left(l_i, r_i\right) = \left(1, N\right)$ のときです。このとき, $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ は $N$ 個の数の総和ですから, これを計算するには基本的な処理を $N-1$ 回実行する必要があります。このようにして、整数の組 $l_i, r_i$ が $Q$ 組与えられます。最も大変になるのは, $Q$ 回の処理各々で $N-1$ 回の基本的な処理を要求される場合で、このとき答えを出力するまでに基本的な処理を $Q\left(N-1\right)$ 回ほど要求されます。

では、ここで問題1と問題2の制約を振り返ってみましょう。

問題1では、 $1\leq N \leq 10^3$ , $1\leq Q \leq 10^3$ という制約条件が与えられていました。これより、プログラムを実行する上で基本的な処理を $Q\left(N-1\right)$ 回実行することを求められたとしても、必要な基本的な処理の回数は $10^6$ 回程度しか要しません。つまり、2秒もあれば十分余裕を持ってプログラムを実行することが可能です。

一方、問題2では、 $1\leq N \leq 10^5$ , $1\leq Q \leq 10^5$ という制約条件が与えられていました。ここで、プログラムを実行する上で基本的な処理を $Q\left(N-1\right)$ 回実行することを求められた場合、必要な基本的な処理の回数は $10^{10}$ 回程度となります。これでは、プログラムは2秒以内に全ての処理を終えることが出来ません。

お分かりいただけたでしょうか。問題2において、答えを出力するプログラムを作成すること自体は、ある程度のプログラミング経験がある人ならば難しくはないはずです。しかし、短時間の間に答えを求めてくれるプログラムを書く為には、答えを効率的に求める方法を考えねばなりません。これは難しい問題です。

これは他のパズルやクイズにおいては類を見ない問題です。そして、これこそが多くの人を魅了する競技プログラミングの醍醐味なのです。

では、問題2を解決するには、どうすれば良いのか。例えば、以下のような方法があります。

$a_1, a_2, \cdots, a_N$ が与えられたときに、新たな数列 $S_n$ を,

$S_0=0$

$S_n=S_{n-1}+a_n$

と定義します。要は, $a_1からa_n$ までの総和ですね。 $S_1$ から $S_N$ を計算するときにそれぞれ2つの数の足し算を実行しますから, $S_1, S_2, \cdots, S_N$ の計算には計 $N$ 回の基本的な処理を要します。

では、その後 $l_i, r_i$ に対し、 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ をどのように計算すればよいのか。実は $S_n$ さえ求めていれば簡単で、 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}=S_{r_i} - S_{l_i-1}$ が成立しています。則ち、2つの数の引き算を行うだけで、 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めることが出来るのです。これより、 $Q$ 組の整数の組 $l_i, r_i$ に対して $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めるには、計 $Q$ 回の基本的な処理を実行すればよいのです。

以上より、この手法を取れば、答えを出力する為に必要な基本的な処理の実行回数は $N+Q$ 回です。これより、 $1\leq N \leq 10^5$ , $1\leq Q \leq 10^5$ という制約条件のもとでも2秒で十分答えを出力することが可能であることが分かります。

如何でしたでしょうか。「答えそのもの」ではなく、「答えを効率的に探す/求める方法」を考えるという、少し変わった面白さが伝わっていれば幸いです。

競技プログラミングは以下のような方々におすすめできます

パズルが好きな人

これまでに見てきたように、競技プログラミングとは、一言で言い表せば「人より速くパズルを解くゲーム」です。パズルが好きな人はハマりやすいと思います。「一般的なパズルに飽きたので一風変わったパズルを解きたい」という方には尚のことおすすめできます。

人と競うのが好きな人

「競技」プログラミングですからね。コンテストは他の参加者との勝負です。

レート(実力の指標)を上げるのが好きな人

言及していませんでしたが、冒頭に紹介したchokudaiさんのツイートの画像にも載っていたように、競プロでは各ユーザーの実力の指標として「レート」という数字が示されており、コンテストの結果に応じてこれが変動します。そのレートに応じて、ユーザー名表記の色が変わる、というのが競プロの通例です。まるでGUTで流行った某音楽ゲームのようですね。レート中毒者にもおすすめ出来る趣味です。

この記事を読んで競プロに興味を持つ方が1人でもいらっしゃれば幸いです。それでは、この記事を終える前にもう1問。

問題3

プログラムの実行時間制限:2秒

長さ $N$ の整数列 $a_1, a_2, \cdots, a_N$ が与えられます。次に, $Q$ 個の整数の三つ組 $t_i, p_i, q_i\left(i = 1, 2, \cdots, Q\right)$ が与えられます。各 $t_i, p_i, q_i$ に対し、以下のいずれかが成立します。