オンサイトで未確認

ukuku09の活動記録。

† The 2017 ACM-ICPC Asia Daejeon Regional Conetst 参戦記 †

Abstract

くっくっく、なぁ〜はっはっはっはぁ〜!!!人間どもよ、己が支配者の前にひれ伏しなさい!そう!この私こそが、いずれ世界を掌握する唯一無二にして絶対の王、胡桃沢=ウクニキア=マクドウェルよ!

今宵この私が自ら筆をとったのは他でもない……。無知で愚かなお前たちのために、ここに我が偉業を記そうと思ったの!感謝しなさい!

 

私に忠誠を誓ったお前たちなら当然知っていると思うけど、11/10〜11/11に開催されたICPC Daejeon(韓国)大会に参加してきたわ!7月の国内予選で日本を手中に収めたわけだけど、この世界の全てを掌握するためには他の国でも我が力を振るう必要があったのよ。

 

ちなみに結果は全体24th、大学別12thよ!!

 

……ビミョウって言うな!!ふ、フン、まぁいい。そう言ってられるのも今のうち……この記録を読めば、どんなに愚かな人間であろうと、私の†悪魔的活躍†に恐怖することになるわ……。

 

ちゃんと最後まで読みなさいよ!わかった?!

(ここまでウクニキア)

 

 

Day 0 † 出国 †

いろいろありすぎて面倒くさくなったので箇条書き

  • 目が覚めたら服が乾いてなかった
  • 駅まで全力疾走(10秒ぐらいで息切れしたが)
  • 学割を忘れる
  • うさぎがいない…うさぎがいない…うさぎがいない!!(駅前の本屋)
  • 車内で働く
  • うさぎがいない…うさぎがいない…うさぎがいない!!(空港の本屋)
  • 機内でアニソンを聴く
  • beetくん(JS)と同じ部屋に泊まる
  • beetくん(JS)の肌色が

Day 1 † Practice †

Before Practice

日本の高速バスはクソ。あと韓国のタクシー乗り場で待ち行列FIFOは機能しない。

学食で†本場の石焼ビビンバ†を食べた。

 

Practice Session

特に開始の合図もなく、雰囲気でスタート。

マスコットの私に唯一割り当てられた、キーボード持ち込み兼接続係という仕事を見事に果たし、あとはシモベの二人に任せて右端の椅子を温めることに専念。

しようと思ったが、どうやら問題文も読む必要があるらしい。全く、人間とは困ったものだ。

PracticeはA,B,Cの3問。問題を見た私「ん?これ全部知ってるぞ」、勝利を確信(ア。

とりあえずhajiさんが設定ファイルを書いている間に、beetくんと問題を共有。

beetくんにAを投げ、私は”解いたことのある”Bを担当することに。

古の時代の記憶を呼び覚まし、大量のWAと引き換えに、微調整を繰り返してACした気がしてくる。

設定ファイルを書き終えたhajiさんに代わり、beetくんがAを実装。

その間にhajiさんと問題を共有。「これ去年のDaejeonだよね?」

ばちゃでCをhajiさんが通していたので、Cはhajiさんに。私はBの紙実装に入る。

beetくんがAをACするが、紙実装は終わってない。

私が紙実装している間に、beetくんが実験を始める。前もって列挙しておいた項目を順番に調べ、だいたい問題ないことを確認する。

紙実装が終わり、実験のキリの良いところでPCをもらう。右端の椅子とはさようなら。

紙実装しておいたコードに沿ってキーボードを叩く。マイキーボードは最&高。

実装が終わり、サンプルを試したところ、合わない。キレそう。すぐに不足しているパートに気づき、再度考察(という名の想起)。

「実装で殴った気はするけど全然思い出せん…」Cの進捗が気になったのでbeetくんとhajiさんに方針を聞き、「ばちゃの時はそれで通った気がする」

CがWAになる。ところで私は何故か中央に来てしまい、beetくんとhajiさんが私を挟んでCを考察する中、一人黙々とBを考える。

この辺りで愚直な実装でBは解けない気がしてくる。同じ高さが複数あった時、マッチングを考える必要があるのでは?と一瞬思ったが、そんなことをした記憶がなかったので、愚直を頑張って考える(ァ……。

私がBでinf時間消費している間に、二人はCの方針が生えてはWAを出していた。

どうやらばちゃの時はジャッジデータが弱かったらしい。

二人がPCを使っていないタイミングを見計らって、愚直実装でサンプルを合わせにいく。が、実装で詰まってしまい、beetくんに怒られる。

たぶんこの辺りでPracticeが終了した。

反省点は多かったが、明日に活かそうとポジティブシンキング。

……Practice後、hajiさんが「BってWFの問題じゃない?フローのやつ」と言ってきて、なぜ今更言ったし…みたいな気持ちになった。

京大チームがBを通していたので、解法を確認しにいったところ、やはり二部マッチングの問題だったことが判明。

てか私解いたことないじゃん。何が「この問題、ばちゃでやったやつだ!!」だよ。やってないよ。

 

After Practice

京大チームと†本場の焼肉†を食べた。

 

Day 2 † Contest †

Before Contest

 忘れた。No airconditioning.

Contest

流れを忘れたので捏造した。

こどふぉった。

昨日と同様、私は右端の椅子に座る。今日は絶対に離れないぞ!と意気込んでいたが、キーボード接続係だったので開始早々離れてしまった。

光の速さでキーボードをUSBメスに差し込み、急いで右端の椅子に戻る。

戻ってくるとbeetくんから後半の問題を渡される。仕方がないので読む。私が1問読み終えるまでにbeetくんは5問くらい読んでた気がする。

beetくんがすぐに解けそうな問題をいくつか見つけたらしいので、hajiさんと交代する形で実装に入る。

hajiさんが右端に座りたがったので、泣く泣く中央に移動。右端の椅子に座るためなら、大悪魔にすら立ち向かってくる雄姿を讃えたのだ。

hajiさんと問題を共有していると、CがDAGの最長経路で解けそうなことがわかってきたので、あとでbeetくんに投げることにする。

†悪魔的直感(デビルズ・センス)†で、(制約を見ずに)Hが簡単そうだと言ったが、制約を見たbeetくん「やるだけではないです」(HはFFTだった。

beetくんが問題を通して(?)帰ってきたので、問題を共有する。やっぱりCが解けそうだったので任せる(てか共有とかじゃなくて勝手に持っていった気がする)。

hajiさんが「LがDijkstraできるのでは?」と言うので、少し話を聞く。そういえばLの問題概要を忘れたので、beetくんと相談してもらうことにした。

ここから1時間以上Eに時間を使う。その間のチームメイトの動向も把握せず、ひたすらEを考える。(そしてContest後に解法を聞いて自分の頭のNASAに絶望することになる。)

最初は、「G'上の最小全域木に必ず含めたい1辺eを決めたあとは、それ以外の辺で二つの最小全域木を作って最後にeで二つの木をつなぐ」みたいな考察をhajiさんとした。

しかしここで昨日の反省が活きる。サンプルを手で試してみると、どうやら最小全域木アルゴリズムではうまくいかないことがあるらしい。

いろいろな作り方を手で試してみたが、なかなかうまくいかない。

ここで驚くべきことが起こる。なんと順位表が開始2時間ほどで凍結してしまったのだ。どうやら1位のチームが†全完†する前に凍結したようだ。

私がEの沼にのめり込んでいると、beetくんから「解ける目処が立ちそうなんですか?」と言われる。あっあっ、ちょっと厳しいです……Aに戦略的撤退(逃げてないよ)。

順位表は凍結してしまったが、風船は一応配られていたので、順位表の提出と風船の色からどの問題がいいかは推測できた。

そしてこの段階では、Aはそんなに提出されてなかった。それなのになぜAに行ってしまったのか……。

Aを見た瞬間、木の分割統治だと思った。木の分割統治はあまり解いたことがなかったが、「こういうのを解ける形に持っていければシモベたちの私に対する忠誠心が一層強まるのでは?」

なんとか†全方位木DP†とかで解けないかなぁと考察を始める。←なぜ捨てないんですか?

EやAの考察の合間にちょいちょいデバッグを頼まれるが、マスコットなのでコードを眺めるだけ眺めて何もしない(†悪魔的行為†)。

残り1時間半、Aを木DPでやるのは厳しいことがようやくわかってくる。一応二人にアイデアを出してみたが、やはり無理だという判断を受ける。

1時間ぶりにEに戻ってみると、辺eを含むサイクルの数が答えになる気がしてくる。ただそのサイクルというのが難しくて、極小(?)かつ辺eのコストよりも小さい辺から構成されるサイクルを数える必要がありそうだ。

そのようなサイクルの数の数え上げに、なんとなくlowlinkが使えるのではないかと思い始める。ここで私の†悪魔的発言(デビルズ・ライ)†が発動。大嘘な考察をhajiさんにする。

が、自分でダメなことに気づく。さすが優秀な大悪魔である。

その後もサイクルという考え方に取り憑かれ、うーんうーんと頭を捻ってはみるものの、思いつかず、最後は諦めてHのデバッグの手伝いに入るものの、そこでContest終了。

…………どう?!最高に悪魔的な活躍でしょう!?(涙目)

ちなみにEは最小カット。それはそうすぎる。

After Contest

 ARCに参加した。Dでやらかした。Eが解けなかったので解説を見たらフローだった。フロー一生解けない。もう”フロー”っていう文字列も見たくない。

Day 3 † 帰国 †

 寝てたら機内食食べ損ねた。

 

感想

や、参加記秋田

 

† ACM-ICPC 2017 国内予選 参加記 †

前置き

私は大悪魔、胡桃沢=ウクニキア=マクドウェル…。今日は我が力を世界に知らしめるための第一歩として、ICPC2017国内予選に参加してきたわ!

ちなみに結果はこんな感じよ!↓

f:id:ukuku09:20170714223109p:plain

 

…ふっふっふ、なぁーはっはっはぁー!6完で8位!どう?!これが我がチームの実力よ!予選通過はもらった!

 

今回はこの私がいかにしてこの悪魔的な結果を得たのか、愚かな人間どもにもわかるようにブログにしてやるわ!私の健闘を刮目するがいい!

(ここまでウクニキア↑)

 

 

前日譚

(ここからうく↓)

昨年のICPC国内予選では26位、惜しくも予選敗退。

この悔しさをバネに、この1年は日々精進。来るICPC2017に向けて競プロに心血を注いできました。

…というわけにはいかず、実際にはかなりダレていて、競プロ以外のことに手を出して遊んでいたら、あっという間に同輩の某甜菜においていかれ、終いにはCODE FESTIVAL予選敗退というなんとも不名誉な結果を残してしまったのでした。

 

そして新年を迎え、僕は自分の宿命を思い出し、大悪魔として覚醒。世界の支配者になるべく覇道を行く決意をしたのです。

 

3月、立命館大学での競プロ合宿を終えた後、部内でICPC2017に向けたチーム練習が始まりました。

ダレていたとはいえ、一応AOJ-ICPC埋めをちょこちょこやっていたので、首尾よく(?)†天才†の@beet_aizuくんと†怒髪先生に褒められた†@haji149さんと組めることに。

beetくんとはバンコク大会で同じチームでしたが、はじさんとは実質初めてだったので、チーム戦略をいろいろ考えながら、チーム練習に励みました。

 

5月には弊学の某チームがICPC WFに出場しました。先輩方の活躍に感化され、(また彼らが引退することで学内予選通過の敷居が下がったため、)サボり癖のある僕もちょっと精進に力を入れ始めたり。

 

そしてついに、我がチーム最強の戦略が決定!それは…

???t「うくさんは実装しないで(バグらせるため」

 

??????????

まぁわかるよ(わかるので。

 

ちなみにオンラインコンテストのレートは上がりませんでした(悲しみ。

 

チーム紹介

(ここからウクニキア↓)

大悪魔であるこの私の名を与えられた最凶最悪のチーム、UKUNICHIA…。

その主力砲台はこの1年で圧倒的成長を見せ、部内最強の座まで昇りつめたunratedの申し子、†天才†の異名を持つbeet!

その隣に並び立つは、かの怒髪先生によって鍛えられた正統な後継者、当代ICPC部部長のhaji!!

そしてそんな実力者である二人すら顎で使う暗黒の司令塔(?)がこの私、ukuku09こと胡桃沢=ウクニキア=マクドウェル!!!

この三人でICPC国内予選を通過、人間どもにさらなる恐怖と絶望を届けるため、決戦の地†つくば†へ向かうわ!

 

  • チーム名:UKUNICHIA
  • †全方位天才†:@beet_aizu
  • 考察界のプロ:@haji149
  • マスコット兼印刷係:@ukuku09

 

予選直前

(ここから流れのみ↓)

普通に1限の英語に出席。5限を消したので1限も消せばよかったなぁと後悔しつつ、なんとか乗り越えて一時帰宅。

昼頃に予選会場へ一時集合。練習セッションで1ACを出したのでもう満足。beetくんと学食へ行く。

その後は前日にライブラリの印刷を終えていたので特にやることもなく、暇だったから†やるだけ†をやり始めたら予選開始30分前までバグらせて縁起が悪かった。

 

予選本番

(若干時系列が違うかもだけど許して)

開始と同時に印刷を開始。この数ヶ月で鍛え上げられた僕の印刷スキルが光る。

はじさんがAを瞬殺する。気づいた頃には全てが終わっていた。

とりあえずC以降を読む。Cが僕にも解けそうだったのでbeetくんにあげる(?)。

代わりにBをもらう。beetなのにBを僕に投げるのかなんて思ってない。

Bが読めたのでbeetくんに説明する。わかってもらえたので嬉しかった。

一通り問題文に目を通し終える。Dをはじさんに投げて、Eは†構文解析†っぽかったのでbeetくんにとっておく。

beetくんがCとBを通す。プロ。Eをくれてやる。

はじさんがDの考察に詰まってそうだったのでふろーふろーと鳴いてみる。違うと言われる。

FとHはよくわからなかったのでGを考えることにした。beetくんにも言われたが、フローの気配を感じる。DかGのどっちかがDPでどっちかがフローだなと思う。

Gで悩んでいるとbeetくんに蟻本を見たら?とアドバイスをもらう。俺には蟻本なんて必要ねェッ!みたいな感じでスルーする(コンテスト終了後後悔する)。

Dがフローじゃない方法で解けそうらしいのでGはフローだと確信する。

Gで嘘フローを何種類か思いつく。全部嘘だから嘘だなって思った。

はじさんの解法でbeetくんがDを通す。なんか0WA4完早解きできたっぽいので予選通過できそうだねみたいな雰囲気になる。

残りの問題は全部難しそう。Gの考察っぽいことを説明したらbeetくんが何かひらめく。僕の考察はガン無視だったけど、似たようなことを言いたかったのでまぁいいか。

beetくんがGの解法を生やす。全然フローじゃないけどなんかあってそうなので任せる。そういえば1問も解いてないので0完の危機を感じ始める。

EよりFが解かれているらしいのでFを見る。意味不明。これ解けるの人間じゃないと思う。

即席折り紙で遊んでいたらGの反例が見つかったらしい。見てみると確かに反例っぽい。やっぱりフローなのかなって思って勝手にGの考察を再開。

beetくんがFをひらめいたらしいが、僕にはよくわからなかった。とりあえず実験(折り紙)が無駄になったことはわかった。

はじさんがGは右手法でいけると教えてくれる。適当に反例っぽいものをつくって聞いてみるが、うまく対処できそうなのでおーってなる。

beetくんがFを通した。もう一人でやってるよね?

とりあえず今出た話をしてみる。なんか実装できるっぽい。面倒臭いとか言いながら光の速さで実装を終えやがる。は?

サンプルが合ったらしいので提出を見守る。1個目が通る。おぉ。2個目。うぉーーーーまじか?!?!?! A C 。

Eを考えるべきとか言われたけど戦意喪失。自分の0完が確定して辛くなる。Gはフローで通したかった…。

 

終結

  • beet:BCFGの考察・解法・実装とDの考察・実装
  • haji:Aの考察・解法・実装とDの考察・解法とFの考察
  • ukuku09:>> 印 刷 と 折 り 紙 <<

 

感想

(ここからウクニキア↓)

私の勇姿はどうだったかしら?え?1問も解いてないじゃん、ですって?バカね〜、私に解ける問題はbeetくんもはじさんも解けるんだから、わざわざ私が実装する必要はないのよ!まぁ確かにチームに貢献できなかったのは悔しいけど、そもそも国内予選ごとき私が手を下すまでもないわ。Gはフローでも解けるっぽいことを聞いたから、ちょっと考えてみるわね。とりあえず予選は通過したみたいだし、アジア地区で私の本領発揮ってところかしら?人間どもぉ、私の力にひれ伏すその日までせいぜい悪足掻きでもすることね!

 

AOJ 2370: RabbitWalking

久しぶりにブログを書くわ!自分用メモだけど。

 

問題概要

RabbitWalking | Aizu Online Judge

 

解法

まず"-1"の判定ですが、グラフが奇閉路を含まないことと二部グラフであることは必要十分条件なので、与えられたグラフの各連結成分が二部グラフであるかどうか判定します。もし二部グラフでない連結成分が一つでもあったら"-1"です。

二部グラフ判定はUnionFindやDFSを使って判定できますが、今回は後から各連結成分の各色(ここでは黒と白とします)の個数を利用したいので、DFSで2彩色しながら個数を数えるのが良いと思います。

(後述しますが、正確には各色の個数というより、二部グラフを構成する2つの頂点集合の大きさが必要になります)

 

もしすべての連結成分が二部グラフである場合、辺を0本以上追加して二部グラフを保ったまま各連結成分を連結することができます。

課題から、辺の追加本数を最大化したいので、各連結成分は完全二部グラフにしてしまって良いことが考察できます。さらに、各連結成分を連結してできる二部グラフもまた完全二部グラフにできます。

完全二部グラフの辺の本数は(黒の個数)*(白の個数)なので、結局(各連結成分の黒の個数の和)*(各連結成分の白の和)を最大化すると良さそうです。

 

先ほど各連結成分ごとに適当に2彩色しましたが、連結成分内ですべての頂点の色を反転させても2彩色状態は保たれるので、二部グラフの2つの頂点集合の大きさのみに注目します。

今、いくつかの連結成分を連結してできた完全二部グラフ$K_{n_i,m_i}$と、まだ連結していない連結成分$K_{a_j,b_j}$を連結すると、新たな完全二部グラフとして、$K_{n_i+a_j,m_i+b_j}$または$K_{n_i+b_j,m_i+a_j}$を得ることができます。このようにして得られる完全二部グラフ$K_{n_k,m_k}$における$n_k*m_k$の最大値が求めるべき解です。(あとで元からある辺の数$E$を引きます)

(2つの頂点集合$V_1,V_2$の大きさをそれぞれ$x,y$とする完全二部グラフを$K_{x,y}$と表記しています)

 

これを解くために次のようなDPを考えてみます。

$dp[i][j][k]:=i$番目までの連結成分を用いて$K_{j,k}$を作ることができるか

これを計算すると、$dp[V][j][k]==true$を満たす$j,k$の積の最大値が解となります。

さらに、$k$の最適値は$i$と$j$がわかれば一意に定まるので、$dp[i][j]$としてしまっても良さそうです。しかし、このDPでは計算量が$O(V^2)$になってしまうので当然間に合いません。

 

計算量を落とすためのアイデアとして、各連結成分$K_{a_j,b_j}$における2つの頂点集合の大きさの差分$abs(a_j-b_j)$($c_j$とします)と、$Σmin(a_j,b_j)$($L$とします)を考えます。すべての連結成分を用いてできる完全二部グラフは、どちらの頂点集合の大きさも必ず$L$以上になっているはずです。また、完全二部グラフの$V_1$の大きさの増分はいくつかの$c_j$の和$sum$として表すことができます。全体の頂点数は$V$なので、この完全二部グラフは$K_{L+sum,V-L-sum}$となります。($a_j>b_j$なら、$n_k$に$a_j$を足して$m_k$に$b_j$を足すのは、$n_k$に$b_j+c_j$を足して$m_k$に$b_j$を足すと見なせます)

(補足ですが、求めるべき完全二部グラフは必ずすべての頂点を含んでいます。これは、完全二部グラフの2つの頂点集合の大きさが連結に伴って単調増加するためです)

 

したがって、先のDPは次のように書き直すことができます。

$dp[i][j]:=i$番目までの差分を用いて$j$を作ることができるか

さらに、$c_j$の種類数は$O(√V)$程度に収まるので、個数制限付き部分和問題(詳しくは蟻本P62参照)と見なして$O(V√V)$で解くことができます。

 

gist85ccc57cc00c88617e78bccfb8de48fc

 

すごく冗長、しかも変数や添字が最高にわかりづらいわ…。はぁ〜、なんて悪魔的なのかしらぁ〜!

 

RUPC2017参加記

  • 前置き
  • Day 0: 移動フェーズ
  • Day 1: 立命館セット
  • Day 1.5: 懇親会 & 準備
  • Day 2: 会津セット
  •  Day 2.5: 懇親会
  • Day 3: 北大セット
  • 感想
  • ※お詫び
続きを読む

AtCoder Beginner Contest 007 D: 禁止された数字

問題文

abc007.contest.atcoder.jp

解法

桁DPしてくださいという問題。桁DPがわからない人は pekempey さんの記事がとてつもなくわかりやすいのでそちらを見てください。

pekempey.hatenablog.com

 

AtCoder Beginner Contest 008 D: 金塊ゲーム

問題文

abc008.contest.atcoder.jp

解法

問題文が無駄に長くてわかりづらいが、よくあるやつだと思った。

ある装置を起動させると、その装置を基準に領域が最大4つ(左上・左下・右上・右下)に分割されるので、そのそれぞれについて再帰的に調べていけば良い。

 

 

AtCoder Beginner Contest 006 D: トランプ挿入ソート

問題文

abc006.contest.atcoder.jp

解法

抜き取らないトランプに注目すると、それらは増加数列になっているはずなので、最長増加部分列を求めて全体から引いた数が答え。