足跡-sokuseki-

りかの日進月歩の記録

ICPC2018 アジア地区横浜大会 参加記

12/8~10に行われたICPC2018アジア地区横浜大会にpriMe.caTというチームで参加しました。
Asia Yokohama Regional Contest 2018 | ACM-ICPC 2018 Asia Yokohama Regional

国内予選の様子→ACM-ICPC 2018 国内予選 参加記 - 足跡-sokuseki-

ぼくは初めてのアジア地区でしたが、める先輩とT.M先輩は昨年もアジア地区に出場し15位を取っていたので、その順位を上回りたいなあという目標が密かにありました。

チーム練

アジア地区を見据えた初めてのチーム練はJAG夏合宿(JAG夏合宿2018 / 会津合宿2018 参加記 - 足跡-sokuseki-)でした。
夏休みが明けてから、週2のサークルの活動でAOJ-ICPCの英語の問題を解いていました。
本番まで2週間を切ったあたりから5時間セットをやりました(codeforcesの北ユーラシアのミラーとLive Archiveにあったアジア地区の過去問を4セット)。

day1

受付が13時~14時なので当日入りで間に合うため朝から新幹線。


昼食を北大の人たちと食べようと思っていたんですが、飛行機が欠航/遅延になる罠があったらしく険しい感じになる。

たぶさんとえびちゃんとめる先輩と4人で中華街に行く。


中華料理を楽しむ。やさいをたべる。

中華街ではいたるところで豚まんが売られていておいしそうだなあと思っていたんですが、受付時間が迫っていることに気づき会場に向かう。

会場についたらすぐにチームの写真を撮った。運営はオタクに厳しい。

開会式が始まるまでは知り合いと†オフ会†をしていた。マスコットとして雛鶴あいちゃんのフィギュアを持ち込んでいる人がいておもしろかった。

開会式では英語で注意事項とかスケジュールとかを話していたみたいなんですが、英語ができないのでよくわかりませんでした。気づいたらpracticeが始まっていた。
エディタの設定やTLやMLの確認、ライブラリの整理をしていました。印刷クエリをたくさん投げてた。

practiceが終わるとチーム紹介が始まる。大学名の辞書順で、前に出て英語でチーム紹介する間にスライドが各モニターに映るという感じだった。ネタに走っている人が多くて面白かったけど、席が一番後ろで前に立っている人が一切見えなかったのが悲しかったです。
ぼくはチーム紹介中に頭にティッピーを乗せる仕事をしていました。
チーム紹介フェーズの途中にカツやお菓子やアイマスクなんかが配られていて意味不明だった。これは何ですか?




これは暁美ほむらです。



チーム紹介が終わるとすぐに解散だったので、ホテルに向かう。
どうして横浜に来て天一なんてたべているのか…(ホテルの近くでおいしそうな匂いがしていたのがすべて悪い)


そのあと夜ご飯を食べました。ラーメンは夜ご飯じゃないです。

ABCがあって、時間がいい感じにこどふぉったので出ました。
えらいので日付が変わる前におふとんいんしました。

day2

7時半くらいにおきる。
会場に行く。会場についたらすぐ電子機器を預けたので写真とったりとかツイートしたりできなかったです。かなしい。




以下コンテスト。

始まってすぐAをぼくが読んでBをT.M先輩が読んでエディタの設定やテンプレ写経をめる先輩がする。Aはやるだけなのでとりあえず実装してもらう。その間にCをT.M先輩が、D以降をぼくが読んでいく。Aを提出するとWAって、実装を聞いてもまちがっているところがよくわからなかったので先にBを実装してもらう。ぼくはAのコーナーケースを考えるやつをする。Bの実装が終わったらしく提出したらTLE。チームが不穏な感じになる。Aでどういうケースがだめなのかを調べる。Cの解法もわかったらしいのでそっちを実装してもらう。AC。Aのミスも発見できてAC。Bもなんか工夫して提出したらACできたみたい。1時間以内に3ACできてよかったけどペナルティが結構大きくて険しい雰囲気になる。
順位表からGが簡単そうな感じだったのでGをやる。Gは転倒数みたいな感じでBITを持てばできるのでやる、AC。この段階で上位チームがDとEとKを解いていたので考える。3人でしばらく考えて、Kは前から順番に考えて行ったらできそうな感じがするのに対し、Dは文字列が1つだとできそうだけど2つになったらわからない、Eは補グラフを考えてフロー?みたいな話になる。Kを実装してもらうことにする。このくらいからIJのACが増えてきてとりあえず目を通す。わかんない。AC数の多いDとEを考える。KがACする。再び3人で考察する。残り2時間弱くらい。
DがDPぽいという話になるけど遷移がよくわからないなあとなる、Eは頂点数が奇数のときは完全グラフにすればよくて、偶数のときは完全グラフにしてから辺をn/2個削ればいいという方針になるけど具体的なやり方がわからない。煮詰まったのでIとJの問題概要を2人に共有して考えてみるけどこっちも良い方針が立たない。しばらくして順位表が凍結し、順位表DのAC数がKとあまりかわらないしなんとかしてDを通したいなあとなるけど、何も浮かばず無を過ごしていました。

コンテストが終わって隣の建物に移動し、解説を聞く。英語なのでスライドの雰囲気で理解しようと努める(無理)。偉い人や企業の人のお話をきく。みなさん英語が流暢だなあという感想を抱く。最後にyes/noがあってぼくたちはnosubなのであんまり関係ないなあと思っていたけど、知り合いのチームや優勝争いのチームのyes/noは盛り上がって楽しめたのでよかったです。

f:id:wk1080id:20181212014843p:plain

結果は5完17位で、Dを通せていたら3つくらい順位があがった、という感じでした。Dは実装ではなく考察なのでもっと考察力があればなあという後悔が強いです。


結果発表後、コンテストをしていた会場に戻って企業賞の発表と集合写真の撮影がありました。priMe.caTが突然呼ばれてよくわからないまま壇上にあがったけど(全部英語なので何もわからない)、どうやらGoogleの企業賞をもらえたようです。Google Home Miniをいただけました。

そのあとはclosing partyで乾杯をした後、各企業ブースを回りました。ニコニコのマスコット(?)とindeedTシャツをゲットできたのはよかったです。ドワンゴボドゲが最初から最後まで盛り上がっていてすごかった。勝ったらカチューシャもらえるらしくて欲しかったんですがボドゲわからないので仕方ない…。あとは い つ も の をしていたり、マスコットオフ会をしたりしていました。

closing partyも終わり、解散の時間になったので解散しました。

そのあとは10人くらいで横浜に戻ってゲーセン旅行をしました。

みんなと別れてホテルに戻るをする。企業ブースで大量の荷物をもらったのでホテルについた頃には体が壊れた。

youtubeのコンテスト中継を見て寝た。

day3

3日目は企業見学で、bitFlyerindeed → LINE でした。



きゅうりさんの頭にティッピーを乗せるをした。


社内をあんまり撮れないからマスコットの写真を撮りがち。
企業見学が終わって、同じグループのメンバーとサイゼ。



各大学の強い人の話や企業コンの話をして盛り上がった。


その後みんなと別れ、秋葉原に行った。てんぷらさんと初エンカ。

そんな感じでICPCが終了しました。


最後に

priMe.caTは今年限りのチームですが、とても楽しくて、たくさんの思い出ができました。
また、横浜大会はいろんな人と会うことができて、新しい知り合いができたりみんなで遊んだりして充実した3日間でした。交流していただいたみなさんありがとうございました。
ぼくは来年もICPC出場資格があるので、チームメンバーは変わってしまいますが、また横浜大会に来たいし、そのためにいっぱい頑張ろうと思いました。

AOJ2321 Butterfly

Butterfly | Aizu Online Judge

問題概要

 N 個の用事があり、  i 個目の用事は時間が  M_i 区間拘束され、  j 個目の区間 s_j 時から  e_j 時である。また  i 個目の用事をすると満足度が  L_i 得られる。
時間がかぶらないように行う用事を決めるとき、得られる満足度の最大値を求めよ。

制約

 1 \le N \le 100
 1 \le M_i \le 16
 1 \le L_i \le 10^8
 6 \le S_i < E_i \le 22

解法

制約から、時間は16個しかないので

dp[i][j] := i個目の用事までするかしないか決めたときに拘束される時間がjの状態のときに得られる最大の満足度

とするbitDPをすると、状態は  N \times 2^{16} 個しかないので間に合う。
入力で  i 個目の用事の区間を受け取るときに、bitに変換しておく( 6+j 時から  6+j+1 時まで拘束されるときに  j ビット目を1にする)と、遷移できるかどうかは&をとればわかるので楽になる。

AIZU ONLINE JUDGE: Code Review

AOJ1336 The Last Ant

The Last Ant | Aizu Online Judge

問題概要

長さ  l cmのトンネルに蟻が  n 匹いる。最初、蟻  i はトンネルの左端から  p_i cmの場所に向き  d_i の状態でいる。トンネルは広い場所と狭い場所があり、狭い場所はトンネルの端から1cmおきのところにある。トンネルのある場所で蟻と蟻が逆向きに歩いて来るとき、その場所が広い場所だと2匹の蟻はすれ違うことができるが、狭い場所だと2匹の蟻はすれ違うことはできず、衝突して今までと逆を向くことになる。

与えられた状態から同時に蟻が動き出すとき、トンネルを最後に出る蟻の番号と、その蟻がトンネルを出るまでにかかる時間を答えよ。

制約

 1 \le n \le 20
 n + 1 \le l \le 100
 d_i は"L"(左向き)または"R"(右向き)
 1 \le p_1 < p_2 < ... < p_n \le l - 1

解法

蟻本の最初に載っているAntsという問題を知っていると、どの蟻についても、トンネルから出る時間がトンネルの長さより大きくなることはないということがわかります。
よって、1秒後から  l 秒後までのすべての時間について、各蟻がどの場所でどの方向を向いているのかをシミュレーションしてあげると良いです。
計算量は  O(l^2) となります。

AIZU ONLINE JUDGE: Code Review

AOJ1237 Shredding Company

Shredding Company | Aizu Online Judge

問題概要

整数  t と数字のみからなる文字列  num が与えられる。文字列  num をいくつかの箇所で分割し、分割後の数の総和が  t 以下になるようにするとき、総和の最大値とそのときの分割の仕方を答えよ。なお、分割後の数の総和が  t 以下にならないときは"error"、答えとなる分割の仕方が複数存在するときは"rejected"と出力せよ。

制約

 t < 10^6
 | num | \le 6

解法

分割の仕方は高々  2^{|num|-1} 通りなので、全て試して、総和が  t 以下になる最大のものを調べてあげればよいです。
AIZU ONLINE JUDGE: Code Review

AOJ1325 Ginkgo Numbers

Ginkgo Numbers | Aizu Online Judge

問題概要

Ginkgo Numbersは整数 m, n のペア (m,n) です。
Ginkgo Numbersの掛け算は (m, n) (x, y) =  (mx − ny, my + nx) で定義されます。
 (m, n) (x, y) =  (p, q)となるとき、(m, n) (p, q)の約数です。

どんなGinkgo number  (m, n)にも少なくとも8つの約数が存在し、それらは  (1, 0),  (0, 1),  (-1, 0),  (0, -1),  (m, n),  (-n, m),  (-m, -n),  (n, -m)です。 もし  m^2 + n^2 > 1 ならば、これらの8つの約数はすべて異なります。

 m^2 + n^2 > 1 かつ約数がちょうど8つのGinkgo number  (m, n)をprimeと呼びます。与えられた(m, n)がprimeであればPを、そうでないならCを出力してください。

なお、Ginkgo numberには以下の2つの性質があります。

  •  m^2 + n^2 > 0 の場合、 mp + nq  mq − np がともに  m^2 + n^2 を約数としてもつときのみ、 (m, n) (p, q)の約数である。
  •  (m, n) (x, y) =  (p, q)ならば、 (m^2 + n^2)(x^2 + y^2) = p^2 + q^2 が成り立つ。

制約

 1 < m^2 + n^2 < 20000

解法

 m^2 + n^2 のすべての約数  a について、 a = x^2 + y^2 となる  x,y が存在するなら、xm+yn   xn-ym がともに  x^2+y^2 で割り切れるか調べ、もし割り切れるなら  (x, y)  (m,n) の約数となる。このようにして調べていき、 (m,n) の約数が8個かどうかで判定すれば良い。

AIZU ONLINE JUDGE: Code Review

AOJ2243 Step Step Evolution

Step Step Evolution | Aizu Online Judge

問題概要

3*3のマスを左右どちらかの足で順番に踏むゲームをする。与えられる指示に従って左右の足で交互にマスを踏んでいきたいが、右足よりも右側のマスを左足で踏んだり、左足よりも左側のマスを右足で踏んだりすることはしたくないので、そのような場合は同じ足で続けてマスを踏むことになる。
踏むマスの順が文字列で与えられるので、左右の足で交互にマスを踏めない回数を答えよ。

制約

文字列の長さは  10^5 以下

解法

一番最初にマスを踏む足(右足か左足)を決めると、求める回数は一意に定まるので、小さい方を答えれば良いです。
AIZU ONLINE JUDGE: Code Review

AOJ1316 The Sorcerer's Donut

The Sorcerer's Donut | Aizu Online Judge

問題概要

ドーナツ状の物体の表面に文字列が書かれている。ある文字から8方向に移動し続けてできる文字列のうち、2度以上出現する文字列で長さが最長のものを答えよ。複数存在する場合は辞書順最小のものを答えよ。

制約

 3 \le h \le 10
 3 \le w \le 20

解法

すべての文字について、その文字からはじまる文字列を全部調べ、mapなどに入れて、2度以上出現する文字で最長なものを探せばいいです。
AIZU ONLINE JUDGE: Code Review