ゆらのふなびと

競プロ, Python, C++

JAG夏合宿2017参加記

昨年に続き 2 度目の参加。

うちのチームは 3 人とも夏合宿に参加していたが、3 日目の JAG セットだけ一緒に出ることにして、他の日はめいめいに他の人たちと組むことにした*1

1 日目

1日目は btk さんと一緒に参宮橋駅前のラーメン屋「空海」でお昼。

会場につくと shora さんや not さんが受付や会場の準備をしていて、夏合宿だなあという気持ちが高まる

jag2017summer-day1.contest.atcoder.jp

コンテストは snuke さんによる 3 時間セット。

imulan さん、yana さんの SyntaxSato チームが 2 人だったので入れてもらった。

解いた順に感想

J: 98 以下の数を全探索すればよさそうと言ったらチームメイトが書いてくれた

K: 担当した。貪欲みを感じたので何でソートするのかいろいろ試す。 G - C ? 違いそう。冷静になってカードの部分集合 S を召喚できる条件を不等式で書くと C + G の昇順にとれば良いことが分かったので書く。 数式をいじれば分かったけどもうちょっと直感的に理解できるようになりたい……。

D: yana さんが算数*2をしてくれて AC

A: imulan さんと yana さんが議論して通してくれた

H: 担当した。上下左右斜め 8 方向に進むコストを考えると、まず斜めに進めるだけ進んでその後上下左右に動けばよい。8 通り場合分けしてコードを書いたのでしんどかった*3

E: 問題を読んだ imulan さんに話を聞くと ‘*’ の両端が vector か expr かで対応を変える必要があって、そこが難しそうとのこと。似たような問題を解いた記憶があったのでアイデアを imulan さんに伝える*4。僕が書くと無限に時間がかかりそうだったので imulan さんとペアプロして解く。僕がざっくり方針を伝えると imulan さんが綺麗にコードに変換してくれてすごかった。

F: imulan さんと yana さんが O(|S|Q) 解法までは出してくれていた。その後 yana さんから S における各文字の出現位置を set で持っておくと次の文字に行くのが O(log|S|) でできる => O(Qlog|S|) で解けるという指摘が来て、解けそうな気持ちになったので僕が書くことに。僕が set の lower_bound の使い方をよくわかっておらず 2 人に助けてもらいながら書いた。 実は set を使わなくても dp[i][j] = 位置 i から最も近い右側にある文字 j の位置 を前計算しておくとできるというのを後で聞いてなるほどとなった。

結果は 7 完 11 位。結構健闘したと思う。0 WA なのもポイント高い

f:id:pakapa104:20170925194359p:plain

snuke さんの公式解説がわかりやすそう

twitter.com

夜は Yazaten, okaduki, btk, btkさんのチームメイトの地頭モンスター氏*5と一緒に sake で優勝しに行った。実質懇親会

宿泊棟の談話室でボドゲをしていた人々もいて、そっちも楽しそうだった

2 日目

朝食チャレンジに AC

codeforces.com

“2015 ICL, Finals, Div. 1” なる 5 時間コンテスト

競プロチームマッチングサービスとして名高い Twitter を活用し、 Div さんと ferin さんの I MUST GO チームに入れてもらう。

以下時系列順

L を読むが題意に確信が持てない。動かせるのが各レーンから高々 1 人なのか全体で高々 1 人なのか……。サンプルが弱いので検証のしようがない。とりあえず様子を見ることにして他の問題へ。

G が解けそうという話を聞いたので読む。確かに解けそう。直線で前にも後ろにも動けるなら移動距離が最小になるのは中央値というのは知っていたが、円環で前にしか動けないのでしゃくとりっぽくやる

L は他のメンバーにも読んでもらったところ「動かせるのは全体で高々1人」らしいので考える。O(n2) は自明だが n <= 105 なので O(n) でやらねばならず意外とめんどい。結局書いたのはどれを左右どっちに移すかを全探索するやつで、元の最大値を m として m の個数と m-1 の個数を持っておいて、(動かした後の最大値) * (その個数) でスコアを計算する、というようなことをやった。

B を Div さんが解いているがバグっていてつらそうなのでコードを読ませてもらうが、特に間違いが見つからない。方針転換ということで僕が別の DP を考え、Div さんに書いてもらうと AC。不明

H は ferin さんが解いてくれた

結果は 4 完。あとは I が解けるか解けないかという感じだった

昨日ボドゲをできなかった無念を晴らすため snuke さんにちょっとだけボドゲを教えてもらった(きゅうりのカードのやつ)

夕飯は夏合宿の聖地「万豚記」へ

僕は辛いものが苦手なので普通のラーメンにしたけど、隣の nvip さんが頼んでいた唐辛子マーク 4 つのやつは運ばれてきた途端香りだけで辛くてやばそうだった

帰宅後は談話室でこどふぇす予選 A オンサイト

D がそもそも構築とかいう発想がなくほげという感じだった

JAG の人が Wi-fi 環境を用意してくれて感謝

3 日目

jag2017summer-day3.contest.atcoder.jp

JAG による 5 時間セット。

Yazaten, ratea と sparsely_populated_regions で出た。

問題が難易度順に並んでいるかどうかわからなかったので、適当に読めそうな問題から読んでいくことに

A: A はさすがに簡単だろうということで、PC の前に座っていた僕が A を読む。O(n3) でもいけるけど ‘*’ の位置の深さを求めればいいだけということに気づいたので書く。

B: まだ読まれていなかったので読む。解けそう*6。「X周以内でクリアできるか?」でにぶたんした*7

C: Yazaten がバグらせていて辛そうだったので話を聞く。外周から1周ずつぐるぐるはぎ取っていくという解法でやっていたらしいが、それより上から1行ずつ埋めていく方が楽そうという話をする。Yazaten が書いて AC。

F: 僕と ratea で考えた。問題を理解するのに 10 分くらいかかった*8。 まず二部グラフだと必ず無限ループするということに気づく。 二部グラフでないときは、奇数長の閉路に含まれる辺の両端が current に含まれるとそこから current が広がっていくので必ず有限ステップで終了する。 そこで解法としては、各辺の両端が初めてともに current に属するまでのステップ数を求める -> その情報を使って全頂点が被覆されるまでのステップ数を BFS で求める、というようなことをした。 解説を聞いたらもっとシンプルでひょええとなった*9

解いた問題はここまで。

D: bitDP解法は思いついたけどずっと O(4N) で間に合わないと思っていた。部分集合の部分集合をすべて考えると O(3N) になるやつは知っていたのに気づかなかったのが悔やまれる

E: 掛け算の中でまず DP をしてその後足し算の世界で DP をすればよさそう。Yazaten に実装してもらっていたけど間に合わず

結果は 4 完 29 位。このセットできっちり 6 完できるようにするのがアジア地区に向けての目標になる気がする。

終了後チームの 3 人で築地にお寿司を食べに行った。とてもおいしかった(写真は他のメンバーが上げてくれるはず)

うにを食べた Yazaten が、retea に話しかけられたとき「今うにが美味しくて忙しい(から話せない)」と言っていたのが面白かった*10

まとめ

JAG スタッフのみなさんありがとうございました。

つくばに行く人はまたつくばで会いましょう。

そうでない人もまたどこかで会いましょう*11

懇親会がないのはちょっとさみしかったです*12が、チーム戦やボドゲを通じてまた新しい人と知り合えたのでよかったです。

正直言うと最近全然競プロをしていなくて、自分が夏合宿に行っていいのかと思っていたのですが、チーム戦を通して「やっぱり競プロは楽しい」という気持ちを取り戻せすことができたのは大きな収穫でした。

またアジア地区に向けてチーム練をやっていきたいと思います。

来年は運営側にいる気がするので、†全方位よろしくお願いします†。

*1:交流の機会は貴重なので

*2:yanaさん談

*3:斜めが右上しか得しないことを考えるともう少し楽に書けそう

*4:構造体にフラグを持たせる的なやつ

*5:Twitter id がわからない……。

*6:この辺りで結局難易度順に並んでいそうだということに気づく

*7:「X日」だと単調性はないが「X周」なら単調性がある

*8:疑似コードをちゃんと読みましょう

*9:解ければ勝ち

*10:実際うにはおいしくて言葉を失った

*11:直近だと KUPC 京都オンサイトには行きます

*12:日程的に仕方ないですが

ICPC2017 国内予選 参加記

作戦

  • ICPC 国内予選では、問題が紙で届くまで 1,2 分かかるかつ 1 チーム PC 1 台という制約があるので、コンテスト開始直後はディスプレイに問題文とコーディング画面とを別のウィンドウで表示して作業することにした
    • ratea: テンプレを打つ→問題が紙で届いたら A を読む
    • yurahuna: B を読む
    • Yazaten: C を読む
  • ratea は解法がわかったら yurahuna に説明する→大丈夫そうなら ratea は A を書く
  • B, C の順で解く
  • D を考える
  • あとはよしなに

本番

  • プリンターのトラブルで、印刷が届くまでに時間がかかりそうだったので、戦略を以下に変えた*1
    • ratea: A を読む
    • yurahuna: B を読む
    • Yazaten: テンプレを打つ
  • 作戦では ratea は A の解法を思いついたら僕に話すことになっていたけど、代わりに(問題文が届かなくてフリーな)Yazaten が聞く役をやってくれた
  • ここら辺特に何も相談してなかったけど Yazaten がうまく立ち回ってくれて助かった(5年目の経験ゆえか)

%%%

  • ratea が A を書いている間に僕は B を読む
  • 問題文がややこしいので慎重に読んだ
  • 文字列をダブルクオーテーションマークで分けてよしなにすればよさそう
  • ratea が A を通したので B の実装に取り掛かる
  • Yazaten が C++ の split 関数をライブラリとして持っていたので、借りて AC
  • 他のメンバーのライブラリを把握しておいてよかった*2

%%%

  • ratea から D 問題の内容を聞く
  • ratea はいつもサンプルの図を描いておいてくれるのでとても助かる(おかげで今回もすぐに内容がわかった)
  • n*m <= 500 という制約があるのでどうせ bitDP するんだろうなあと思ったけどよくわからず
  • 考察していると、n <= m のときは 2n 全探索で解けることがわかる
  • m < n のときは……と考えていたら Yazaten が C を通してやってきたので D の進捗を話す
  • 話していたら bitDP 解法らしきものを思いついたので伝える
  • いけそうだねとなったのでやる
  • 計算量が不安だったけど†二分(にふん)探索†の精神でやる
  • 僕が bitDP パート、Yazaten が全探索パートを書くことに*3
  • 2人で順番に書く
  • サンプルが両方の解法で合うことを確かめる
  • サンプルが合ったのでテストケースを落として実行

%%%

  • Segmentation Fault
  • 思考が停止する

%%%

  • bitDP でメモリ取り過ぎなのかなあという話になり僕が bitDP パートを配列を使いまわすように書き換える
  • せぐふぉが取れない
  • Yazaten の発案で入力のどのケースでせぐふぉってるのか見ることに
  • n<=mなので全探索パートでせぐふぉっていることがわかった
  • 全探索パートのコードを読むと、添字がおかしいところを発見
  • 直す
  • せぐふぉが取れた!!
  • ケース 1 通った!!!
  • ケース 2 通った!!!!
  • AC!!!!!!!!!!!

%%%

  • この時点で 30 位ちょい(0WA)だったので、いけそうだけどもう1問通したい気持ちになる
  • E と F の説明を ratea から聞く
  • E は構文解析、F は考察ゲーっぽさを感じる
  • 精神に余裕がないと考察ゲーには手を出しづらい
  • Eをとる
  • yurahuna「入力の文字列の長さが16以下なのでvalidな論理式を列挙してもそんなに多くならないでしょ」Yazaten「ほんとかなあ」
  • Yazaten が変数のない論理式を評価する関数を作る
  • yurahuna は列挙パートを考える
  • Yazaten がガリガリ実装してくれるが間に合わず終了
  • 35位なので通りそうだけど微妙な後味

反省

  • 実装力を Yazaten に頼りすぎなので、自分ももっと鍛える必要があると思った
  • 特に「実装寄りの考察力」
  • E の列挙パートで自分が提案した方針はよくなかった
  • AOJ-ICPC の黄色をやっていくのがよさそう
  • アジア地区がんばるぞい

*1:Aのペナルティタイムを短くするため

*2:Pythonで書けばもっとよかった

*3:ここでわざわざ分担しているのは、Dを早く通したかったのと、僕が全探索パートの計算量をよくわかってなかったため

PyCPXで最短経路問題,最大流問題を解く

PyCPX Introduction — PyCpx -- Python Wrapper for CPlex Optimization Suite 0.01 documentation

PyCPX は,整数計画問題のソルバーである CPLEX の,Python によるラッパー.

研究で使うことになったので練習.

グラフの問題に使いたいので,最短経路問題と最大流問題を PyCPX で解いてみた.

実行環境の都合でコードは Python2."pycpx" を “PyCPX” にしないと動かないとかあるかもしれない.

最短経路問題

gist.github.com

最大流問題

gist.github.com

26, 27行目,制約式も sum で直感的に書けるのが良い.

RUPC2017 参加記

RUPC2017(立命館大学競技プログラミング合宿2017)の参加記です.

atnd.org

昨年に引き続き 2 度目の参加.チーム戦ができる数少ないオンサイトということで楽しみにしていました.

Day 1: 立命館&阪大セット

この日は作問チームに参加していました.

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=RitsCamp17Day1

経緯としては,立命館の作問人員が足りなくて大変という話を Yazaten さんから聞いていたので手伝うよと言っていたところ,誘っていただいたという感じです.阪大もくっついて巨大化したのでむしろ問題数が増えて 4 時間 11 問になりました*1.当日までは,問題案を投げたりテスター解を投げたりしていました.

会場に向かう途中,湖西線トラップ*2にひっかかり近江舞子まで行ってしまいました.おかげで駅メモが捗りました. 会場に着いたのはコンテスト開始 5 秒前でした.

僕が作問を担当したのは E 問題「卒業式」と I 問題「Islands Survival」です.

E 問題は,自分の作問ストックにあった問題にストーリーをつけて出したものです.卒業式と RUPC が被っているフレンズが多かったのでネタにしました.

I 問題は,ノートにグラフを描いて遊んでいたら生えました. 生えたての頃は入力のグラフが木に限られていて「Tree Survival」という問題名だったのですが, Slack で議論していたら木じゃなくても解けることに気づき,「Islands Survival」になりました. 絵を描いてみると解法がわかる感じが気に入っています. 実装が少し辛いのもあってか,本番の AC 数は下から 2 番目でした.

コンテスタントのみなさん,作問チームのみなさんありがとうございました. また機会があればどこかの作問チームに紛れ込むかもしれません(?)

余談ですが,作問の副産物として,数式・アルファベットの両端に半角スペースを入れる習慣が身に着きました.スペースがないと地味に読みづらいので,問題文を書く人はぜひ気にしてほしいです*3

コンテスト後は学内で懇親会でした.生協の揚げ物フィーバーだったので,油の摂取量がオーバーフローしないように気をつけていました.同学年の競プロerたちと就活話をしたり,n_vip さんや rian さんを特定したりしていました.

家に 2 時間半かけて帰ると既に 23:30 で感情を喪失したので,次の日は会場最寄りのアーバンホテル南草津に泊まることにしました*4

Day 2: 会津セット

7:19 に限界集落を出発し会場へ.

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=RitsCamp17Day2

この日は odan さん,tsutaj さんとチーム toy18 で参加しました*5

昨年の CODE FESTIVAL でもらったノートをまだ使っていなかったので,この機会に使うことにしました.

この辺りから敬体と文体が混ざります(sorry)

~~~コンテスト開始~~~

C 問題を読む.構文解析っぽいので NLP のプロである odan さんに投げる.

代わりに A 問題をやることに.式が書いてあったのでそれをありがたく使わせていただくが WA.別に式が間違っていたわけではなく,僕が出力する角度を [0, 360) の範囲に納めるのを忘れていた.AC したけど意外と辛かった.

次は E 問題を読むことに.「比の最小化→二分探索」は幸いすぐ気づいた*6.操作後のグラフは全域木になるので,最大全域木をやればよさそう.クラスカルを写経して submit したが WA.よく考えると,全域木側で比を最大化したからといって,他の辺についての比が最小化されるとは限らない.適当に式をいじったら実装できる形になったので書いて AC.FA が取れて歓喜

D 問題を解いていた tsutaj さんがバグっていて辛そうだったのでヘルプに入る.当初は dp[i][j] = ( i 日目までに励まし力を j 使ったときの,今まで登校できた日数の最大値) という O(NP) の DP を考えていたが,それが嘘だと気づくのに 10 分ほどかかった.i 日目に必要な励まし力を求めるには,i - 1 日目までに連続で何日登校したかが分からないといけない. 紆余曲折を経て dp[i][j][k] = ( i 日目までに j 日登校し,i - 1 日目までに k 回連続で登校したときの,残っている励まし量の最大値) という DP に至る.励まし量を添え字ではなく配列の値にするというのは,ナップザックの重みと価値を入れ替えて DP するやつのイメージで考えていた.添え字のエラーにさいなまれながら AC.

I は BIT を 10 個持てばよさそうという話を聞くも,change クエリの処理方法がわからずパス.

F は最小カットっぽいけど,サイズが大きいので最大流できない.よく考えると,岩は少なくとも 2 個あれば非連結にできるので,岩が 0 個 or 1 個で済む場合の判定だけ真面目に考えればよい*7.方針としては岩を set に突っ込んで DFS すればよさそうということを言って odan さんに任せる.コンテスト終了 5 分前くらいにバグが取れたものの TLE.set を unordered_set にしたら通るのでは~?と思って書き直すも,コンパイルエラーが消えず間に合わなかった*8

~~~コンテスト終了~~~

E を自力でさっと解けたのはよかった.D や F も考察では貢献できたものの,実装ではいろいろ振り回してしまって申し訳なかった.F は UnionFind でやると楽という話を他のチームの人に聞いて納得した.「連結性の判定→UnionFind」は出てくるべきだった.

実装に時間がかかり,後半の問題にほとんど目が通せなかったのが悲しかったです. 解説を聞いていたらどの問題も面白そうだったので,解きます.

懇親会の写真はたぶんみんなが上げます.お腹が MLE しそうなほど食べられて幸せでした.ありがとう御社.

↓ホテルからの写真

Day 3: 北大セット

http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day3

rian さん,Pulmn さんとチーム ElogV で参加しました*9

北大の運営陣が tsutaj さんが 1 人だけで大変そうだった(ありがとうございます……)*10

~~~コンテスト開始~~~

A 問題を読む.よくある回文の問題なので適当に実装して投げるが WA.文字長が奇数のときの処理が間違っているのを rian さんが指摘してくれたので直して AC.結局切り上げを切り捨てにするだけでよかった.

E を読むとセグ木っぽいが,セグ木の経験値が低いので投げたくなった.D を読んでいた rian さんもグラフっぽいけどよくわからないという状態.僕はグラフの問題が好きで,rian さんはグラフよりはセグ木の方がいいという感じで不安定マッチングだったので D と E を交換した.D の速度の範囲が小さいことは rian さんが気づいてくれていたので,適当にダイクストラをすればよいだろうとたかをくくる.頂点 1 → n → 1 のサイクルの最短距離を求めるというのが特殊だが,それは頂点 n を既に経由したか否かのフラグを持てばよさそう.結局 d[i][j][k] = (頂点 i に 直前の体感速度が j でたどり着き,すでに頂点 n を経由している (k=1) / していない (k=0) ときの頂点 i までの最短距離) としたダイクストラを書いてAC.

僕が D を書き終える頃には rian さんが E の方針を立ててくれていた.連続する 1 の区間を set で管理すればよさそうだが,rian さんが使っている C# には lower_bound がないので辛いということで,僕が実装を担当することに.といっても僕も慣れていないので C++er の Pulmn さんに助けを求めるなどしていた*11.実装に 30 分くらいかかって submit するも WA.更新処理で足りていない部分があることに気づく.G の解法を rian さんと Pulmn さんが生やしていたので G を rian さんにコーディングしてもらいながら,僕は E の足りない部分をつめていた.その後は submit→WA→PCを明け渡してデバッグ→コーディング→……を繰り返していた.結局 E も G も通せず時間切れ.

~~~コンテスト終了~~~

G は完全に解けていたようなので,E を捨てて G に PC を明け渡した方がよさそうだった.特に 3 時間という短いセットだと,自分の実装力の限界を知ることは大切かもしれない*12

rian さんの指摘力がすごかった.A の WA の理由をすぐ見つけてくれたり,B の実装を Pulmn さんが辛そうにしていたのもサポートしてくれたりしていて,チーム戦慣れを感じた.

解説を tsutaj さんが 1 人でやっていてプロだった.

予定があったので,解説が終了すると早々に会場を去りました.

御社にスポンサー感謝の旨を伝えてきました.

金銭面での援助は学生には本当にありがたいです.

まとめ

やはりチーム戦は楽しい.今年は ICPC に出場するつもりなので,できるだけ長く楽しめるように頑張りたいと思いました.

昨年に比べると自分の典型力*13が上がっていることが実感できたのはよかったです(Day2E, Day3Dなど).一方で,「これは解けない」「絶対バグる」等の感覚はまだまだ鍛えていかないといけないと感じました.もちろん典型力を上げる方も(セグ木で殴る力など).

3 日間楽しかったです.運営のみなさん,参加者のみなさん,スポンサー様,ありがとうございました.RUPC はみんなでコンテストを楽しめる場としても,競プロer の交流の場としても非常に良い機会だと感じています.決して簡単に運営できるイベントではないと思いますが,来年もみなさんと一緒に RUPC に参加できることを楽しみにしています.僕にできることがあれば手伝いますので,なんなりと言ってください*14

*1:昨年は 3 時間 7 問だった

*2:琵琶湖線の「湖西線経由」に乗ってしまった

*3:day1 作問チームでは tubo28 さんのご指導によりスペースを入れていました

*4:1 人用の部屋がちょうど 1 部屋だけ空いていて助かった

*5:toy は 3 人の頭文字.18 はみんな 18 卒(B3 or M1)だったので

*6:「これ蟻本で見たことある!」

*7:SRM の div1easy に似たような発想で全探索に至る問題があった

*8:原因は hash を unorder_set を使う「前に」定義していないことだった.気をつけよう

*9:チーム名は Pulmn さんの発案.ダイクストラの計算量

*10:先輩たちはみんな卒業式だったらしい

*11:知見として,set.erase(itr1, itr2) で [itr1, itr2) の範囲を一気に削除できることを知った

*12:ICPC国内予選しかり

*13:「典型力が高い」とは,「典型と思える範囲が広い」ということだと思っています

*14:他のイベントでも,割とやりたがりなのでどうぞこき使ってください

2017年の目標

今年が始まってもう13日目になりますが、2017年の目標を書いておきます。

レーティング

AtCoder: 1996 -> オレンジ(2400)

Codeforces: 1912 -> master(2200)

TopCoder: 1331(highest) -> 黄色安定(1600)

やること

AOJ-ICPCを黄色まで埋める(国内予選までに)

ARCを埋める(今年度中)

蟻本を読み直す(今年度中)

AtCoder400日連続AC→累計1000問


だいぶハッタリもありますが、このくらいを目標に頑張りたいと思います

AOJ1330 Never Wait for Weights

とても面白いと思ったけど、帰着によってはそうでもないらしい?

問題

Never Wait for Weights | Aizu Online Judge

N個のアイテムがある。M個のクエリが与えられる。クエリは次の2種類である。

  • ! a b w アイテムa, bの重さの差はwである(w_b - w_a = w)
  • ? a b アイテムa, bの重さの差は?(w_b - w_a = ?)

クエリは時系列順に与えられる。各?クエリについて、それまでに得られた!クエリの情報のみから答えが確定できる場合は答えを出力せよ。確定できないときは"UNKNOWN"と出力せよ。

制約

2 <= N <= 100000

1 <= M <= 100000

!クエリは矛盾しない

解法

アイテムを頂点とするグラフを考えます。クエリ! a b wに対し、aからbの向きに重みwの辺を、bからaに重み-wの辺を張ることにすると、? c dの答えが確定できるのはそれまでの!クエリのみによってcとdが連結になっている場合で、答えはcからdまでの距離(有向パス上に含まれる辺の重みの総和)です。!クエリは矛盾しないことが保証されているので、cからdへのパスが複数ある場合、それらのパスが表す距離はすべて等しくなります。そこで、!クエリを処理するとき、辺の両端が既に同じ連結成分に属していれば辺を追加しないことにします。

上のようにすべての!クエリを処理した後のグラフは森になります。? a bに対し、aとbが同じ連結成分に属しているかどうかは前からUnionFindしていけばわかります。aからbまでの距離は、各連結成分が木なのでLCAを使うと高速に求められます。実装上は、すべての木をまとめて扱うためにスーパールートsをつくり、各連結成分から1つずつ頂点を選んでsとの間にコスト0の辺を両向きに張りました。これで全体が木となります。ただしsをまたがないと行き来できないような頂点どうしは連結とはみなさないことにします。

LCAの内部でdfsしたらセグフォしたのでbfsにしました。

gist.github.com

DDCC2016に参加しました

「DISCO presents ディスカバリーチャンネル コードコンテスト 2016」参加記です。

japan.discovery.com

今回は割と注釈芸をしています*1

予選は3完75位で、18卒枠で通過しました。

会場まで

始発でぎりぎり間に合ってしまうことがわかったので、5:10に奈良を出発し東京へ向かった。

会場がおしゃれな感じですごかった*2

進行役の女性がプロのアナウンサーっぽい人で、"""本物"""感に圧倒された*3

本戦

配点*4を見て3完を目標にした。時間が120分しかないので、B, Cは部分点を無視して700点から解きに行くつもりだった。

Aはぱっと見、普通に2重ループ回してすべての正方形を見ればよさそうという気持ちになった。しかし左上の格子点が円の内部*5にあるかだけで判定しようとしてバグらせていた*6。正方形の4頂点すべてが円の内部にあるかを判定するようにしてAC。15:16(遅い)。

Bは「この問題予選で見たことある!」となったが中身はちゃんと難しくなっていた。部分点は真ん中から鏡合わせにつなげばよさそうとわかったが満点解法は10分くらい考えてもわからず。しかたないので部分点を取りに行く。300点確保。

Cに行く。部分点は文字列を頂点とみなしてグラフを作るとダイクストラでいけそう。満点はどこから手をつけていいのかわからなかった。しかたないので部分点を取りに行く*7。こちらは実装が結構しんどくて、typedef map<string, vector<pair<string, int>>> Graph;みたいなものをひいひい言いながら書いていた。これを通した時点で71:32。

Bに戻る。いろいろ考えていると、今残っている中で最長のものの長さはコストに加算せざるを得ない……ならばそいつと一緒にできるだけ長いやつを道連れにしてやればいい、というようなことを思った。制約に甘えて毎回ソートするO(N2 logN)解法を投げる。AC! 考察中は円だとだるいので、後で載せる図のように長さの順だけ書いて考えていた。

残り時間はCを考えていた。いろいろ書いていると、"10"があったらそこは反転していなければならないのでそこで左右に分かれるんだろうという気がしたがまとまらず。D, Eはちらっとみたけど皆目見当がつかないという感じだった。

f:id:pakapa104:20161205173843j:plain:w480
▲コンテスト中に取ったメモ

f:id:pakapa104:20161205173848j:plain:w480
▲Bの考察

f:id:pakapa104:20161205173852j:plain:w480
▲†闇のダイクストラ

特別ビュッフェ

おいしかった。なんかお寿司が知ってるお寿司と違った。サンドイッチのパンがクロワッサンっぽい感じでブルジョワっぽかった。チョコフォンデュを初めて食べた。

こどふぇすで会おうと思っていたものの会えなかったtorus711さんを発見したので会いに行った*8。某件でお世話になっているお礼を直接述べたかったので述べる*9。本戦の問題について何人かで話しているとちょくだいさんもやってきてしばらく話していた。どうやら提出を監視されていたらしく、僕がCの部分点をダイクストラで解いたことに対し「ダイクストラって何!?」と言われむしろ「ダイクストラって何って何!?」という気分になった。説明するとあーと納得してもらえたけどどうやら普通に全探索すればいけるらしかった*10。1つ方針を思いつくとそこにハマりがちなので、簡単な方針を選ぶ能力を身に着けていきたい。ICPCに向けてという意味でも。

他にも母校である阪大の競プロerに声をかけてもらえたりして嬉しかった*11

厚切りジェイソン氏特別講演

本当に厚切りジェイソンだった*12。競プロやっててよかったと思った。

ディスコ会社紹介

Kiru Kezuru Migaku

社内ツアー

デュアルカットが生で見られて面白かった。ちょくだいさん曰く「このためのウェーハ」だったらしい。プールやジムなどの福利厚生施設もいろいろ見せてもらったけど、もう少し技術的な部分をいろいろ見たかった感がある。

表彰式・懇親会

表彰式では名だたるプロたちのご尊顔を拝むことができ大変光栄だった。懇親会では↓のツイートをしていたおかげかいろんな人に話かけてもらえてうれしかった。

他にも、E869120氏*13の協力によりLatteMalta氏を特定した。レアキャラのpekempey氏を特定したのも特定ポイント高い。

また食事が出て、ケーキがおいしかった。生ハムが人気だった。

まとめ

今回のコンテストで1つ驚いたのは、スタッフさんの多さです。撮影があったからというのも理由としてあるとは思いますが、これだけ多くの人に支えられてコンテストを開いてもらっているのだなあと思うと感謝の念を禁じえません。

コンテストを開いてくれる方々に感謝しつつ、もっといろんなオンサイトに出られるように精進していきたいですね。

DDCC、来年度も開催されるなら、いいイベントなので特に19卒のみなさんは予選に出てみるといいと思います。

*1:括弧が多くなりすぎたので

*2:語彙不足

*3:ディスカバリーチャンネルの人?

*4:300, 700(300), 700(300), 1000, 1500

*5:境界含む

*6:右端の方で余分にカウントしてしまう

*7:2回目

*8:僕はお会いしたことがなかったのだけれど、一緒にいたshora_kujira16がtorus711さんを知っていたので特定できた

*9:さて某件とはなんでしょう??

*10:空文字から初めて、構成中の文字列と直前に反転したかというフラグを引数に持つ再帰で書けるはず

*11:最近さらに盛り上がってるみたいでOBとして嬉しいです

*12:別に疑っていたわけではない

*13:今そらで869120って書けたんですけどすごくないですか??