ゆらのふなびと

競プロ, Python, C++

KUPC2017参加記

京都オンサイトで参加しました。

コンテスト前

NA勢(shora_kujira16, Yazaten, ratea, yurahuna)で一緒に登校

13:00に着けばいいと思っていたらそれはコンテスト開始時刻で、12:00の集合には自明に遅刻する

行きがけにラーメンをACして会場へ

コンテスト開始には間に合った

一部の競プロerが喜びそうな北海道土産があったので差し入れ

コンテスト

kupc2017.contest.atcoder.jp

A: ソートして大きい順に履修する

B: 大きい方から割る*1

C: なんか解けなくてつらかった

D: 数字が2つあればいけそう

何もわからないので実験のコードを書く*2

5x5を見ると8通りしかなく、パターンに規則性がありそう

if 文を書いてエイってしたら通ってしまい笑う

こういう問題作れる人頭いいなあ

E: 宝箱を頂点、鍵を辺とするグラフを考えて、サンプルを図示する

「x か y を開けられる鍵で x を開ける」⇔「辺 {x, y} を x <- y に向きづける」だと思うと、入次数が1以上の頂点の価値の総和を最大化したい

連結成分ごとに独立

1つの連結成分について考えると、適当に頂点 s を1つ決めてそこから辺の向きを外向き*3に決めていけば s 以外の入次数は1以上にできるので、各連結成分で空けられない宝箱は高々1つ

連結成分に閉路があれば、閉路をぐるっと1周してその閉路から外に向ければよいのですべての頂点の入次数を1以上にできて、木だと辺が足りないので入次数0の頂点が1つできる

UnionFind で閉路検出して、木のグループは最小値引いてAC

あとは解説を聞いただけ

Fはひたすらやばそうだった

Gはいろいろ解き方があるらしく面白そうだった

懇親会

懇親会では drafear さん、amano さん、kimiyuki さん、odan さん、shora さんと一緒のテーブルだった

京大の drafear さん、amano さんに作問裏話を聞いたり、kimiyuki さんに Piet を "png で圧縮した結果を" ゴルフするというエクストリームスポーツの存在を聞いて震えたりした

途中で asi さんがやってきて、asi さんと shora さんから 6 年前の SuperCon の話を聞いた*4

当時参加者たちでやっていたという「バイオレンス・ノベル・ポーカー」が面白そうだった*5

お店から出た後、富山から来た kuuso さんから車で 4 時間かけて帰るという話を聞いて大変そうだなあと思うなどした

まとめ

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

*1:入力の N 要る?

*2:ここでバグって1時間くらいかかっていてダメ

*3:例えばBFS順

*4:その頃から知り合い/競プロやってるってすごいなあ

*5:「漢字の書かれたカードを5枚集めて一番面白い必殺技を作ったやつが優勝」というゲームらしい。バイオレンス・ノベル・ポーカー - Google 検索

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