オンサイトで未確認

ukuku09の活動記録。

† 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

解法

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

 

 

AtCoder Beginner Contest 010 D: 浮気予防

問題文

abc010.contest.atcoder.jp

解法

サンプルのグラフを見ると「あー最小カット」という気分になるので最小カット。最大流-最小カット定理より、最大流のアルゴリズムそのままで最小カットの問題も解ける。