裏紙

ほぼ競プロ、たまに日記

ACM-ICPC 2018 Asia Hanoi Regional Contest に参加しました

2018年11月29,30日に、ベトナム ハノイでACM-ICPC 2018 Asia Hanoi Regional Contestが開催されたのでWAsedACというチームで参加しました。

メンバーはimulan(私)、ryoissy、yamad、コーチのtossyの4人で行きました。結果は125チーム中2位でした。

ベトナムの出来事、思い出を簡単に書き記そうと思います。

出発前

この3人でのICPCは最初で最後というのと、3人中2人がラストICPCというのもあり、1回ぐらい海外のAsia Regional参加したいねとなる。

選択肢は横浜と被っているヤンゴンを除いて、大会規模などを考慮してハノイ、ジャカルタ、ソウルが候補になりましたが、韓国は魔境の匂いがしたので実質二択になりました。

ベトナムの問題セットを過去2年くらい見て、ハノイに行くことにしました。正直ジャカルタのセットはほとんど見なかったんですが、今年のジャカルタセットをチラ見した感じだとジャカルタでも良かったのかなあと思います。ただ、コンテスト全体の雰囲気は年による感じがあるみたいなので何とも言えません。

運営側がホテルを指定してくれて、「このホテルに泊まればホテルから会場まで送迎してあげるよ」って書いてあったのでそこに泊まることにした。ホテル代とか、参加費のために海外送金が必要になるのですが、色々と面倒が待ってるので早めにやるといいです(自分がやったわけではないが...大感謝)。ホテルには、ちゃんと送金したつもりが、足りなかったみたいで2回送金するはめになったりした。

出発前日にはホスト校のPTITの学生から"I’ll be volunteering for your team in the upcoming ICPC contest"ってメールが来た(大会中はほぼこの学生の方が案内してくれた)。もしものために電話番号とFacebook messengerを交換しておき、出発に備える。

11/28

移動日。朝7時に羽田に行く。空港でnarianZ(東工大チーム)に遭遇した。

ベトナムに(現地)15時くらいに着いて、ホテルまで行くためにタクシーで行くことにするが、タクシーのキャッチがめっちゃ強気で来たのでビビった。ICPCベトナムのサイトにタクシーの相場が書いてあったので、ちゃんといくらで行けるか聞いてからタクシーを選ぶことが出来た。

持ってきたガイドブックに乗ってたレストランで夕飯を食べるためにホテルから10分くらいあるいて夕飯を食べにいく。ハノイは信号が少なく、断続的に車とバイクが走ってくるので、間をぬうように道路を渡る必要があり、ヒヤヒヤしながら渡るけど、向こうも分かってるのでスピードを調節してくれる。ただクラクションは鳴らされる。

11/29

プラクティスの日。午前中にホテルに運営の方々が来て、Registrationとか、写真撮影とかを済ませる。Registrationとかをする前には、上で書いた私達のチームについてくれた方がコーヒー屋さんに連れてってくれた。めっちゃ甘くて美味しかった(絶対自分たちだけではこのお店に入る勇気はなかったと思う)。コーヒーを飲みながら、何を勉強してるのかとか、(1年生ということもあって)ICPCにあまり詳しくなさそうだったのでそういう話をした。あとはスマホの壁紙が"君の名は"だったので日本のアニメについても話した。ラピュタをおすすめしたら「見たこと無い」と言われたので「日本ではテレビで何回も放送されてる大人気作品です」と言っておいた。

午後からホスト校のPTITに移動し、開会式をした後にプラクティスがあった。

開会式の終わり際に、ジャッジからコンテストに関する説明があり、インタラクティブ問題に関する注意事項(flushしようね、みたいな)が説明され、それと同時に"""明日の本番では1問インタラクティブが出題される"""ことが明らかにされる。プラクティスに2問もインタラクティブがあったのでそれを考えたり実装したりした。システム自体はKattisを使っていたので、オンラインでKattisを使うのと変わりなかったので良かった。

プラクティスでは、Vietnam National Contest (日本でいうところの国内予選?)の問題のAからFが使われていた。

この日の夜は、海外チームは運営側が用意してくれたレストランで夕飯を食べた、日本勢(東工大、神戸大、筑波大)の方々と談笑しながら、美味しいご飯を食べた。

ホテルに帰ってから、L問題を考えて実装したりしてた。面白かった。

11/30

本番当日。コンテストは8時〜13時で、6時半にはホテルを出るというスケジュールだったが、意外と起きられた。

ここからコンテスト中の感想になるので、問題に言及する部分があるので、問題のネタバレを見たくない人は飛ばしてください。

順位表

チームの基本的な動きは、全員がパソコンに触る、2問以上を並行で進めていく(3人のリソースを1問に注ぎ込むというのは基本的に終盤までしない)、ぐらいです。

開始直後

開始直後からネットワークが重くて不穏。

始まったらA-D、E-H、I-Lに分けて問題を読み始める。自分はI-Lを読む。

yamadがAがいけるというのでとりあえず書き始めてもらう。

1通り書き切る頃には、もう自分はIJKLと読み終わり、CとHに正解が出てるので、Cを読む。Hはryoissyに考察を詰めてもらう。

Aが実はだめ方針だったらしく、Cはサンプルの説明をした画像が間違ってたから焦ったけどBFSをするだけなので自分がCを書く。

C AC(0:36)

そのままPCはryoissyに譲り、Hを書いてもらう。AはBFSベースで書いていたらしいが「よく考えたらパスが点素にならなかった」らしく、頂点に流量制約のあるフロー+その復元っぽいので考えてほしいと言われ、概要を聞いて、確かにできそうだと思うので自分が引き継ぐことにした。

H AC(0:56)

そのかわり、この辺りでI、J、Lに正解が出てるのでI、Jを2人に説明してから、自分がAのためにDinicを写経し始める。

自分がフローの復元で実装に手間取っている間に、Iの方針が固まったので書き始めてもらい、Jは「ループと完全グラフしかないんじゃないか」という結論になったので、それを出してみることにする。

J WA(1:47), I AC(1:51)

Jはきっと何か見落としてるんだ、と思い一旦おいておくことにする。この辺でLのclarがあり、問題文が修正された、というアナウンスがあったがネットが重くてclarが見れない。開始から2時間後くらいに、やっとネットが安定し始めてclarが確認できたので、Lをryoissyに説明し自分はAに戻る。

A WA(2:24)

結構自信があったので焦る。もう一度自分で問題をよく見直す。"shortest"って書いてあって、Dinicじゃできないじゃんってなる(見落としてたらしい)。でも、ちょっと考えると、グラフの形は変えずに、頂点に流量をつけた部分だけコスト1にした最小費用流の形にすれば、通過頂点数を最小にできることに気づき、最小費用流を写経する。

A AC(2:47)

この辺でJは頂点数が偶数だったら左右の頂点数が等しい完全二部グラフも条件を満たすということに気づいて、これで通らなかったらJは捨てるか、ぐらいの気持ちでJを出す。

J AC(3:04)

通ったのでテンションが上がる。そのままLをryoissyが書き始める。単語リストをソートし忘れたり、配列外参照をしたりしたが、程なくして通る。

L WA(3:16, 3:21), AC(3:22)

この時点で3位で、よりテンションが上がってくる。この時点で、残りの問題で正解者が出てるのがB、D、G(Gは1チームだけ)しかないのでそれらに絞ることにする。挑戦してるチームが多かったのはKで、幾何なので担当するなら自分になるが、順位表から方針を立てて実装したとしてもその後に絶対辛いデバッグが待ってると考え、Kは捨てる決意をする。

Dはインタラクティブなのでデバッグの辛さが思いやられたが、正解が多かったので、残ってる問題的にこれはやらないといけないと思い10分くらい3人でDを相談する。

けど、3人で1つに絞るのよくない、と思い、ryoissyだけはBのゲームを実験してもらうことにし、Dを自分がPCを使いながらyamadと一緒に考察することにする。

ずっと始点を固定して区間を伸ばしたり縮めたりすることを考えていたけど、どう頑張ってもクエリ回数が足りないので頭を抱える。

30分くらい紙で実験してくれてたBがわかったらしいので、実装してもらう。

B AC(4:09)

この辺から(テンションで)自分たちがうるさくなってきた(と思う)。

Dは、長さを固定して始点を動かすようなクエリを投げると、毎回答えの位置の候補を半分に絞れそうな気持ちになり、それを実装する。この時書いた二分探索が、閉区間による実装になっていたため、クエリが足りなくなったり細かいバグを踏んだ。

D WA(4:23, 4:28), AC(4:38)

残りの時間はGを考え、辺が多い方はできそうだけどねー、みたいな話をしながら祈っていた。

↑これだけだとネットワーク悪くてちょっとイライラしただけ、みたいに見えますが、実際は前半2時間の時点で3完だったのでそのせいもあって内心はイライラと焦りがやばかったです。

焦りはしましたが、結果的には、自分がCAD、ryoissyがHLB、yamadがIJみたいな感じで実装を担当し、PCが空いてしまう時間がほぼなかったので良かったです。

順位表から、8完の可能性があるのは4チームで、うち1チームにはペナルティで勝てる見込みがあったので3位以上になりそうなことがわかり、もう気が気ではなかった。

閉会式は夕方で、その前にエクスカーションがあり、ハノイ郊外にある陶器の工房みたいなところとマーケットを見学して回った。バス移動で片道1時間かかったが、チームメイトとか、PTITの学生(2,3人)としゃべってたら移動はあっという間だった。自分たちと話してたPTITの人は日本に興味があるって人が多くて、日本語も少し喋れる人もいた(すごすぎる)

大学に戻ってきて、閉会式、YesNoが始まる。

YesNoの動画は自分でも撮ってたけど震えてて使い物にならなかったのでTumoiYorozuさんのツイートを引用させていただきました(ありがとうございます)(再生回数の15回分くらいは自分です)。

壇上で表彰状、金メダル、トロフィーを頂きました。

そのまま大学内の屋外会場でディナータイム。NCTUのコーチっぽい人に、「NCTUは台湾で2位だったから僕たちがWF行ける確率上げるために君たちが横浜でも2位以上獲ってくれ〜〜」みたいなことを言われて、がんばります...ってなった。

ホテルに帰ってきてPTITの学生の人たちにも挨拶をする。次何したらいいかよくわかんない時もすぐに案内してくれたし、本当に良い方々だった。

12/1

移動日。出発は15時くらいだったので、午前中は余裕があったら観光するか迷ったけど、起きたら雨めっちゃ降ってたし、気力もなかったので、ホテルの目の前のショッピングセンターを30分くらい見て回るぐらいに留まった。

22時に羽田に着く。ハノイは25度くらいあったのでとても寒い。

おわりに

以上の3泊4日で、ベトナムに行ってきました。ご飯おいしかったし、現地の人優しかったし、何より成績が良かったので思い出に残るICPC海外Regionalでした。横浜でもがんばります

CERC 2016 D - Dancing Disks

Codeforces programming

問題

gym

問題文

問題概要

ハノイの塔のような、いくつかの棒と、それに積み重なった輪っかを考える。

棒は6行、6列の36本の棒が立っている(上からr行目、左からc行目の列の棒を棒(r,c)と呼ぶことにする)。 輪っかは全部でn個あり、大きさはすべて異なる。輪っかには小さい方から順に1,2,3,...,nと番号をつける。

次のようなパズルを考える：

はじめ、n個の輪っかは棒(1,1)に任意の順番で積み重なっている(下からi番目には輪っかd_iがある)。これらを棒(6,6)に大きさがソートされた状態(大きいのが一番下、小さいのが一番上、つまり上から1,2,3,...,nの順)になるように移動させたい。1回の操作で出来るのは、ある棒を選び、上からk個をとりだして、そのまま下の棒か右の棒に移動する(棒(i,j)からは棒(i+1,j)または棒(i,j+1)に移動できる)ということである。

nとはじめの状態dが与えられるので、このパズルを解く操作列を出力せよ。解は存在すると仮定して良い。

  • 1 \le n \le 40000
  • 1 \le d_i \le n
  • d_iはすべて異なる(つまり順列)

アイデア

簡単な例を考えてみる。nが少なかったらどうかを考えてみると、4*4の棒があったときに、15個の輪っかを運びたいとする。

f:id:imulan:20181019054312p:plain

そして、空いている15マスのところに1箇所ずつ輪っかを運ぶ場所を指定して、(手間ですが)山の上から順番に1つずつ指定された場所に運ぶ。

f:id:imulan:20181019054542p:plain

あとは、これをいい感じの順番に右下に回収していけばソート完了になるのが想像できる。

ということで、こんな感じで棒がいっぱいあればソートは出来ることがわかる。ただ、1つの棒を1つの輪っか専用にするのが明らかに無駄な感じがする。

そこで、次のように同じ場所を2つの輪っかで共有するような方法を考えてみる。 今度は輪っかが22個ある。

f:id:imulan:20181019055137p:plain

そして、ごちゃごちゃのままではあるが、この山を輪っかの大小を基準に小さい方を右へ、大きい方を下へ運ぶ。

f:id:imulan:20181019055338p:plain

2つの山に分けたあとに先程のような割当てを行い、順番に回収していくことを考える。

f:id:imulan:20181019055606p:plain

そうすると、2つの輪っかに割り当てられるマスが発生して、先程より効率よく使えていることがわかる。この方法に限って言えば、青い山の方を先に処理して、12から22を先に右下に集めてしまえば、赤い山は青い山に影響されることなくソートを行うことが出来る事がわかる。

このように、操作の前に既に下に何かあったとしても、その上の処理が終わるまでは一旦床とみなしてしまうことができ、その先の処理に何も影響がなさそうだ、ということが想像できる。

あとは、この例のような分配を再帰的に行ってソートをすることを考えたい。そこで、今回nの上限が40000なので、6*6マスで実現できるかを確かめよう。そこでf(R,C)を残りR行C列残っているときに、任意の並びの山をソート済みにできる最大の個数とすると、

再帰的に右下全部のマスで処理させることを考えると、処理可能な個数は \displaystyle f(R,C) = \sum_{r \le R, c \le C, (r,c) \neq (R,C)} f(r,c)である。初期値はf(1,1) = 1で計算すると、fの値は以下のテーブルの通りになる。

f:id:imulan:20181019060706p:plain

これでは、40000個を処理できない。もう少し工夫することを考える。

そこで、 f(1,2) = 1となっていることに注目すると、これはもっと良くなる。具体的には、2にできる。なぜなら、2個ということはソート済みか、ひっくり返ってるかのどちらかしか無いが、ソート済みならそのまま一気に2個運んでしまえば良いし、ひっくり返ってるなら1個ずつ移動させればソート済みにできる。

ということで、新たに初期値f(1,1) = 1, f(1,2) = 2, f(2,1) = 2としてテーブルを埋めると以下のようになる。

f:id:imulan:20181019082521p:plain

よって、このアルゴリズムに従ってあとは操作列を出力すれば良いことになり、出力の行数も輪っか1つに対して10回が限度なので400000行ぐらいで、間に合う。

実装(C++)

続きを読む