ICPC2019 アジア地区大会 参加記

 

TLDR

ICPC2019アジア地区大会に、チームPICOPICOPONとして参加して6完11位でした。結構エモい気持ちになったので、来年の自分がエモい感じを思い出せるように、参加記を書こうと思います。チームメンバーは、yamad, lgeuです。

 

大会前

チーム結成時(5月)

PICOPICOPONって、二郎系のラーメン屋さんの名前らしいですね。チーム名が決まって数ヶ月後に知りました（え）

 

5ヶ月前(6月)

チームメンバーのlgeuが黄色になりました。よって僕は、チーム内唯一の寒色コーダーになってしまいました。僕はレート1950くらいの頃でした。

 

2ヶ月前(9月)

2週間ほど競プロに沢山集中できる期間が出来たので、分野を絞って全力投球しました。選んだ分野のきっかけはこちらです。

具体的にはこんな感じで、クエリ関係の知見をまとめてました。

  1. 学習に使えそうなサイトまとめ
  2. 学習において実際に解いた問題, 知見のまとめ
  3. (途中で思い付いた、後でやろうと思った分野のまとめ)

自分用だったので公開しようか迷ってたら今になりました。正直beetさんの記事が強すぎるので。

f:id:toa25:20191119041458p:plain

 

2週間前(AGC040)

 なんとかギリギリ黄色になりました！これにてチームPICOPICOPONは全員黄色コーダーでアジア地区大会に臨めます！

 

 1週間前(全統一コン)

Q「What's this ?」

A「This is SOKUOTI NIKOMA」

 

大会1日目

朝

早解きの感覚を思い出すため、少し前に告知のあったPASTの問題を解いてました。既に解いていた問題ばかりだったので、2時間で88点取っておきました。最後2問やってたらICPC遅刻しそうなので解いてません。

 

昼

集中モードに入り始めました。うぉおおおおお！

環境構築で色々確認していたら、リハーサルは2完でした（完）

 

夜（ABC145）

本番直前大逆転勝利です。ちなみにチームメンバ―全員が全完して寝ました。lgeuはCodeforcesにも出るって言ってて凄いなぁって思いました（小並感）。

 

 大会2日目

朝

「あーたーらしいーあーさがきたー　きーぼーうのーあーさーだ」

珍しく目覚めが良くてびっくりしました。目覚まし無しで午前7時起きです。

1時間くらい時間があるので、なろう系の漫画を読んでました(ふざけてるように見えるので、チームメンバーからは隠れて読んでました)。俺つえー系の精神、僕の場合は競プロでプラスに作用する傾向にあったので、漫画を読むことで緊張を吹き飛ばしてました。実際精神が潰れそうな緊張じゃなく、心地よい緊張になりました。

その後はコンテスト開始まで無難に行動したので割愛。

 

0:00 (コンテスト開始)

初動は、yamadが環境構築、tomaがA問題、lgeuがB問題で臨みました。

以下、toma目線でのコンテストの模様です。

 

0:21(B問題AC)

A問題を速攻で書くと、高確率でミスってWAが出そうだったので、先にlgeuにBを書いてもらいました。本当に一瞬で凄いなぁと思いました（小並感）

 

0:26(A問題AC)

Bを終わらせたlgeuを巻き込んで、0WAでAのACを取ろうとしました。実は入力に1を足すことで、while文1個と、簡単な式5～6個が本質になる問題だったので、5分で書いてデバッグ入出力を見てAC出来ました。

 

1:38(H問題AC)

yamad, lgeuが頑張って解いてました。問題概要をコンテスト後に聞くレベルに何も知りません。3人で解くようなものではないとのことで、僕はCDGI問題をもくもく読んでました。

 

2:31(E問題AC)

このタイミングではEが一番容易なので僕も解いてました。物凄くDPなので、最長増加部分列などを調べながら、どういう遷移なのか考えてました。するとlgeuが「二部グラフ？」って呟いて、僕も特に反例は見つけられなかったので、yamadが実装しました。

 

3:28(G問題AC)

文字列問題だったので、初動で読んだ後、多分yamadの得意分野だろうと投げてました。実はダイクストラだったので、EH問題をyamadが解いている間にもっと考察を進めれば良かったと反省してます。

 

4:33(I問題AC)

初動

完全にグラフ問題です。実は大会前に、HL分解が出たら僕が頑張るみたいな話をしてたので考えました。木構造だと、根付き木にしたあとに経路上の必須順辺に1, 必須逆辺に-1のラベル付けをすれば良いので、HL分解をコピペすればやるだけに帰着できます。実は木構造じゃなかったのでHL分解は使えず泣きながらE問題などを読んでました。

 

転機

途中でyamadに概要を伝えると、queryをDAGにする提案を貰いました。それをlgeuに横流しすると、ループを作れば良いじゃんという話を貰いました。

その後、クエリによるDAG上のループを元グラフにパース出来ないかを考えていると、「9月に集中して解いてた帰省ラッシュが類題では？」という意味不明な閃きをしました。

f:id:toa25:20191119052619p:plain

 この問題はどういう問題かというと、二重辺連結成分分解をした後に、二重辺連結成分をノードとする木をHL分解して頑張ってくださいという問題でした。二重辺連結成分分解の後が木になることなどは、同じく9月にAtCoderの解説で学んでました。

f:id:toa25:20191119052933p:plain

そこでyamadに「二重辺連結成分において、任意の頂点から任意の頂点に到達可能なグラフの向き付けは可能か？」と聴いたらYesと返ってきました。そうなれば話は簡単ですね。初動で考えてた方針は木構造なら達成可能です。そしてグラフを二重辺連結成分分解によって木構造に落とし込むことができました。範囲に1や-1を加算するのは、HL分解の得意技です。これにて終了！以上をyamadに実装してもらいましょう！

 

実装

と思ってたのですが、流石にHL分解は不要だったらしいです。実際にはLCAまでのルートに+1, もしくは-1をするだけだとyamadに伝えると、いもす法で余裕という話だったのでその方針で実装してもらいました。

最終的にコードが完成したタイミングで終了30分前で、バグらせていたら5完終了の恐れがありました。怖かったのでWAが来たとき用に一応テストケースを8通りくらい作ってましたが、1発ACが来たので杞憂でした。

 

5:00(C問題まにあわない…)

I問題が上手く行きそうで喜んでいた所、C問題をlgeuが完全に解いてました。I問題ACは終了27分前ではあるものの、ギリギリ行けるのではという見込みでyamadが実装していました。結局間に合わなかったものの、後20分くらいあればACしそうという状況だったらしいです。

 

結果発表

 最終的に6完11位でした。昨年世界大会に行った同校のWAsedACが10位だったのでギリギリ勝てませんでしたが、十分健闘出来たと思っています。 

僕個人としては、A, I問題には貢献出来たので嬉しかったです。まさか9月に木上クエリ系を全力で頑張ったことで、人類に解ける問題のうち3番目に難しいI問題の考察が出来るとは思ってませんでした（リアル伏線回収）。

（ただ途中のEGHに全然貢献できず、最終的にC問題に時間を残せなかったのでそれが悔しいです。最後の最後でI問題のACを疑って反例検知やテストケース増産に執着しすぎて、C問題の助っ人に入れなかったのも悔しい）

f:id:toa25:20191119054948p:plain

 

景品

11位になれたので、いい生活さんとレトリバさんから色んなものを頂けました！特に、いい生活さんのホワイトボードが凄いんですよね。ホワイトボード4枚が上端だけ磁石でくっついているんですよ。そしてペンも4つ。

ICPCの実戦練習の際に、1人1枚ホワイトボードを使って考察や情報共有が出来て、残り1枚を全体進捗確認に使えるという丁度良い枚数なのです。これが全員に渡されているので凄い。

その後は直帰して寝ました（3日目の企業見学は朝10時集合なので）

 

大会3日目

楽しかった！イルカさん　ヾ(*´∀｀*)ﾉｷｬｯｷｬ

（写真撮影出来た分だけツイートしてます。）

 

あとがき

ICPC楽しかったです！

来年はもっと楽しくなるよね、ハム太郎？

 

ということで、来年がもっと楽しくなるように精進します！

FHC#R1感想

 

前置き

Facebook Hacker Cup Round1お疲れさまでした。

私はABC3完でしたので、それぞれの感想とかを書いていきます。

 

A問題

（記法：考察→実装の流れ）

証明は面倒なのでしませんが、正しい配管配置は凄く限られます。

1.左端の列と右端の列は、必ず問題文の図の左端,右端にあるような配管しか出来ません。

2.0-indexedとして、2*i+1列目と2*i+2列目(0<=i<N/2)は、必ず問題文の図の1,2列目のように上に凸、もしくは下に凸の配管しかできません。

3.2より、Nが奇数のとき、絶対に配管が不可能なことが分かります。

 

考察は、以上のような流れで行けます。

実装は、まず3番より if (N%2==1)return 0;

1番より、if (左端の列と右端の列のうち必要な場所が埋まってる) return 0;

2番より、求める場合の数を初期値1にしたうえで、

上に凸が出来れば1倍,下に凸が出来れば1倍,両方できるなら2倍になります。

 

雑に言うとこういう流れの実装をすると通ります。

 

B問題

（記法：実装ベースの考察）

AIZUの階段本ありますか？

そこに、木を先行順巡回,後攻順巡回する関数の実装例があります。

これで先に、巡回順番を配列データに起こしましょう。

 

次に、2つの配列データをデバッガなどで見ながら考えてみましょう。

それぞれをA[i],B[i] (0<=i<N)とします。

この時、A[i] == B[i] となるようなラベル割り当てが、問題文での要求です。

そこで、UnionFindを導入しましょう。

A[i]==B[i]なのであれば、併合して同じグループにしてしまうのです。

それを繰り返せば、同じ数字にならなくてはならない頂点同士は、同じグループに居ます。

 

後は、グループがK個以上であれば、それぞれに1~Kのいずれかを割り当てればOKです。(1~Kはそれぞれ1回以上使うことは忘れずに)

 

C問題

（よく分からん）

 

全体の実装順は、前計算O(N*M)→二分探索O(log(Z))→範囲縮小O(N)です。

では順番に見ていきましょう。

 

前計算

・とりあえずHの値は漸化式として与えられています。それを展開しましょう。

・パルクールをする方に関しては、担当区間と高さの差の上限下限だけ与えられてます。

そこで、配列limUp(size:N),limDown(size:N)を定義しましょう。

limUp[i] := 地点iから見て、i+1がどれだけ上にあってもパルクール出来るか。

limDown[i] := 地点iから見て、i+1がどれだけ下にあってもパルクール出来るか。

A<B or A>Bで少しだけ混乱しますが気を付けましょう。

 

範囲縮小

前置き

先にこっちの方を考えてみましょう。

先程の前計算結果をどのようにしたら活用できるのかを考えます。

先程の前計算で分かったことは、

・H[i]の値

・H[i+1]の取りうる値の範囲(H[i]基準で)

です。

 

小さな具体例

さて一度、答えを0secと仮定して全体を見渡してみましょう。

H[0]に着目すると、limUp[0],limDown[0]を元に、H[1]の取りうるべき値の範囲が分かりますね。その範囲の中にあれば、全てのパルクール演者はH[0],H[1]間のパルクールが成功します。

これを一般化して、H[i]に着目すれば、limUp[i],limDown[i]を元にH[i+1]への（からの）パルクールが成功するかどうかが判定できます。全てのiで成功すれば、答えが0secでもパルクールが成功します。

 
一般化

さて問題は、0secじゃない場合にはどうなるのか？

これは恐らく、図を書いてみると解きやすいと思います。

まず初めに、答えが t secであると仮定します。

 

区間 0-1における、0の方が取るべき高さの区間

次にH[0]から見たH[0]が最終的に取りうるべき高さを考えます。

(これは換言すると、t secという条件下に置いて、更にH[0]がその時間内に動ける範囲をH[0]自身を用いて定義しているフェーズです。)

これは(H[0] - t) ～ (H[0] + t)－①　の区間です。その範囲であれば、t sec以内に高さが調節できます。

 

区間0-1における、1の方が取るべき高さの区間

そしてH[0]から見たH[1]が最終的に取りうるべき高さを考えます。

（これは換言すると、t secという条件下に置いて、更にH[0],H[1] 間の高さの差分の条件を満たすH[1]の高さの範囲を、H[0]を用いて定義しているフェーズです。）

H[0]は先程の結果より、 (H[0] - t) ～ (H[0] + t)　の区間で自由に高さを決定できます（ただし下限は0です）。その上でlimUp[0],limDown[0]の情報も付け加えると、結果としてH[1]が最終的に取るべき高さは、(H[0] - t - limDown[0]) ～(H[0] + t + limUp[0])ー②　の区間になります。それ以外の高さをH[1]が最終的に取ると、どう頑張ってもパルクール演者の誰かは失敗します。

 

 

さて後は、これを区間1-2以降も繰り返していくだけです。

（ただし次の場合は、①と②の重複部分が、H[1]の取るべき高さの区間になります）（ここ上手く文字にしにくい）

これを、H[i] , H[i+1]それぞれに対して順番にやっていきます。

最終的に可能な区間が残っていれば、、t sec以内にパルクールの準備が可能です。

 

二分探索

さて、所要時間を固定すれば、パルクール成功判定は出来ます。そこで所要時間で二分探索します。

こういう感じでやっていけば、何とか解けます。

感想

C問題の考え方を文字に起こすのめっちゃ難しいし、野生のプロの文章読みながら書き方習います。

ともかく、Round2に進出出来て良かったです。

Round2が午前2~5時にあること、その12時間後くらいに予定があることはヤバいですが、多分大丈夫だと信じて、Tシャツを狙っていきます。

（確かTシャツは上位500人でしたよね？）

 

Round3は、運が良ければ行きたいなぁ・・・

 

以上、Round2進出を確認してから1時間で書き上げてみました。