ゆらのふなびと

競プロ, Python, C++

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って書けたんですけどすごくないですか??

競技プログラミングを始めて1年間でやったこと

この記事は Competitive Programming Advent Calendar 2016 3日目の記事として書かれました。

競技プログラミングを始めてちょうど1年くらいになるので、今までやってきたことをまとめてみようと思います。

これから競技プログラミングを始める人の参考や、既に競技プログラミングをやっている人の昔を思い出す材料にでもなれば幸いです。

と言いつつほとんど日記なので、お正月によくある1年をまとめた特番的なアレだと思ってまったり読んでください。

これを書いているのは現在青くらいの人です(競技プログラミングyurahunaという名前でやっています)

目次

  • 振り返り(2015年12月~2016年11月)
  • 成果(レーティングとか解いた問題数とか)
  • 最後に(ポエム)

2015年12月

研究室でデータ分析のためにPythonを身に着けないといけなくなった。 本を読むだけだとつまらないので何か問題を解きながらやりたいと思って調べていたら、競技プログラミングの存在を知った。 みるみるうちに競技プログラミングにハマった。問題を解いてACがつくのが本当に楽しくて、ABCのA,B問題をひたすら埋めていた。

プログラミング経験は、工学系なので大学でC言語をやりはしたけど、情報系ではなかったし、自発的なプログラミングはほとんどしたことないという感じだった。

Twitterをやっていたので競プロ界隈の人たちをフォローした。その影響でABC(AtCoder Begineer Contest)とCodeforcesにはこの頃から出ていたらしい。あとはyukicoderもやっていた形跡がある(★1,2あたり)。

競プロerたちをフォローすると、間断なく競プロ情報が流れて来るのでいいと思う。数日間競プロをやらなくても忘れてそのままフェードアウトするようなことがない。

2016年1月

卒論を書きながらABCを埋めていた。1/19にABCのA,B問題埋めが終わり、C問題をメインに解くようになった。

twitter.com

最初は典型アルゴリズムなんて知らないので1問2時間くらい普通に考えていたのだけれど、ダイクストラやワーシャルフロイドがよく出てきたので蟻本を買って読んだ。1章はよくわからないのでほとんど飛ばしてしまった。ABCのCまでは蟻本の初級編(2章)まで読んでいれば知識としては足りたように思う。蟻本の例題は難しいので、自分で別途類題を集めて解いていた(↓こんな感じ)。

pakapa104.hatenablog.com

CodeforcesはA問題を落としまくってレートが下がる一方だった。

2016年2月

Codeforcesで1,2完が安定してとれるようになりレートがシアンになった。問題をちゃんと読むようにしたのがよかったのかもしれない。

AtCoder埋めを続けていて、2/14にはARCのA、2/16にはABCのCが埋まった。2/20にARCのBも埋まった。この辺りは並行してやっていたらしい。AtCoder Virtual Contestなる神サービスが誕生したので、ひたすら埋めたい問題をコンテストに入れて解いていた。時間制限があると途中でダレなくてよかった。Codeforcesのvirtual participationもちょこちょこ使っていた気がする。

twitter.com

ひょんなことから作問をすることになり、yukicoderで初めて出題をさせていただいた。

No.345 最小チワワ問題 - yukicoder

No.346 チワワ数え上げ問題 - yukicoder

作問には割とハマって、ひたすら問題案をひねり出してはいろんな人にテスターをしてもらっていた覚えがある。問題を作る中でアルゴリズムの新たな側面を知ることもあって面白かった。作問に関しては「AtCoderでいつか作問できるようになりたい」という気持ちがあって、これが作問についても競プロ自体についても割とモチベーションになっていた。

この頃まではPythonで解いていたが、いちいちTLEしてつらいのでC++に乗り換え始めた。

蟻本の3章を読んだのもこの辺りの時期な気がする。ただ、3章の内容はまだ自分の実力でたどり着ける位置の問題には出てこないようなものも多かったので、とりあえず一通り読んでおいて必要になったらまた勉強しようという気持ちだった。二分探索やしゃくとりは割とよく出てきたので問題を解きながら覚えられたけど、フロー周りは正直今でもまだまだ奥が深いなあ……という感じ。

本を読んでがっつり勉強したのはたぶんこれが最後で、以降はコンテストや埋めで解けなかった問題から学ぶ、必要なら蟻本に立ち返るという感じだった。なのでこれ以降は取り組み方に関してあまり言えることがない(その分イベントまとめみたいになります)

2016年3月

RUPCに行った。

pakapa104.hatenablog.com

初めてのオンサイトなのでビクビクしながら行ったが、これがとても楽しかった。競プロerとの交流やチーム戦の楽しさを知った。 ICPCの存在は知っていたが、早生れならM2でも出られるらしいということを知って興味が湧いた。この時から「ICPCに出ること」が自分の競技プログラミングをやる上での1つのモチベーションになったように思う。

オンサイトに行くと楽しいし、モチベーションが爆上がりする。さらにオンサイトで解いた問題は記憶によく残るので勉強のためにもオススメ。

埋めの方はと言うと、LCM-Rushに心を折られながらABCのDを埋めた。ARCのCは半分くらい埋めたけど残りはしんどくて、AtCoder Virtual Contestで解ける適性難易度の問題が見つけづらくなってきた。そんな中YazatenさんにAOJ-ICPCを薦められて解き始めた。Yazatenさんとのdiffを埋めるという名目でやっていたのだけれど、これは結構モチベーションが湧くのでオススメ。適当に実力が少し上くらいの人を見つけて、適正難易度から埋めていくといいと思う。他のコンテストよりも実装重視の問題が多く、実装力の面でだいぶ鍛えられた気がする。

2016年4月

大学を卒業し、進路変更のためにニートをしていた。ニートなので競技プログラミングに打ち込んだ。

ICPCの、JAGによる模擬国内Aがあった。チームメンバーを募集していたらなぜかuwiさんと組ませていただけることになり2人チーム(tempura)で参加した。僕はA,Bを解いたがCの構文解析が永遠に組めず冷え。壁を感じた。一方uwiさんは後ろの方の問題をバンバン通していてすごかった。

この頃から競プロ界隈(で僕が観測している範囲)ではTypingWar(対戦型タイピングゲーム)が流行り始めたらしい。

作問ブームはまだ続いていて、yukicoderで2回目の出題をさせていただいた。

yukicoder contest 136 - yukicoder

★1で出した問題が★2になったりしかも既出だったりして冷えたが、問題を作って人から反応がもらえるのはやはり楽しかった。ますます作問にハマった。特にbtkさんにはテスターとしてかなりお付き合いいただいた(この成果は半年後に日の目を見ることになる)。

2016年5月

Codeforcesのレートがブルーになった。Div2Cが2回に1回くらいは解けるようになったらしい。

Google Code Jamの予選があった。 Round1Cで確か1000位以内に入るとTシャツがもらえたのだが、1063位で悔しかった思い出がある。 と同時に、今年1063位だったなら来年はもらえるだろうという気持ちもあった。 GCJの問題は解いていて面白かったので、来年はもっと上に行きたい。

ICPCのWorld Finalがあり、Twitterに流れてくる写真を眺めながらなんだこの楽しそうな世界は、と思っていた。

2016年6月

大学院入試の勉強の傍ら競プロをしていた。

JAGによる模擬国内Bがあり、チームMusyoku(1人)で参加した。4完できたので、自力2完だった模擬国内Aに比べると成長が感じられる。C,Dを1人で実装しきれたのはAOJ-ICPCを解いていたおかげかもしれない。

ICPC国内予選の本番もあり、観戦勢としては進学先(予定)のNAISTのチームが通ってくれてうれしかった。

2016年7月

院試が終わったのでまた競プロ漬けの日々が始まった。

AtCoderが新しくなり、AGC001が行われた。良問すぎて震えた。C問題が木の直径と中心に関する問題だったのだけれど、このあたりの話がよくわからなくて2週間くらいずっと考えていた記憶がある(ネットで見つけた英語のpdfとにらめっこしていた)

2016年8月

ICFPCに参加した。

pakapa104.hatenablog.com

主にソルバーを担当していたが、長いコードを書いたことがないので実装が進まなかった。

このときチームを組んでいたshora_kujira16さんがビジュアライザとかをパパッと作っていたのに影響されて競プロ以外のプログラミングにも手を出していたが、あまり続かなかった。僕は「プログラミングに興味はあるけど特に作りたいものはない」人だったので、競プロ向きだったんだと思う。

この頃semiexpさんがSlitherlink Playerを作っていた影響でペンシルパズルにドはまりし、競プロがおろそかになりかけた。

2016年9月

JAG夏合宿と会津合宿に参加した。めっちゃ楽しかった。

pakapa104.hatenablog.com

pakapa104.hatenablog.com

この頃は人と会うたびに「次はこどふぇすで会いましょう!」と言っていた(行けるといいなという気持ちも込めて)。

Twitterで話したことがある人とは割と話せたので、オンサイトでいろんな人と話すには普段からTwitterで仲良くしておくのがいいと思った。

会津合宿の直前にやっとフローに再挑戦した(2月のところに蟻本の3章を読んだと書いたが、そのときにはあまりよくわかっていなかったのと、解ける問題を増やしたいという気持ちがあった)。結局会津合宿で出たフローの問題は解けなかったが、復習はできたのでよかった。ざっくりとでもアルゴリズムを知っておくことは、学ぶ機会を活かすために必要だと思う。

2016年10月

KUPCに行った。5時間ソロのオンサイトなので座るだけにならないか心配だったが、最後まで楽しませてもらえた。Eがなかなか嘘をつかせる問題で、解説でカットと聞いてなぜ気づかなかったのかと悔しくなった。

大学院に入学した。新入生向けのガイダンスでICPCの黒いTシャツを着ている留学生がいて、話かけたりした(来年一緒にチームで出られるかと思ったけどそれは無理みたいで残念だった)。

入学前からNAISTの人たちとコンテストを主催したいという話をしていたのだけれど、そのプロジェクトがこの頃から発足した。ひたすら問題を作っていた。

2016年11月

引き続きNAISTコンテスト(仮)に向けて作問をしていた。講義が意外と忙しかったのであまり過去問演習はしていなくて、せめてと思いAtCoderのコンテストには毎週出るようにしていた。

CODE FESTIVALに行った。めっちゃ楽しかった(イベントについてこれしか言ってない気がする)

pakapa104.hatenablog.com

という感じで、最後の方ほとんど箇条書きでしたが振り返り終了です。

成果

1年やった結果をまとめてみます。(レーティング、AC数は2016/12/1現在のものです)

AtCoder

f:id:pakapa104:20161201220515p:plain https://atcoder.jp/user/yurahuna

f:id:pakapa104:20161201220528p:plain http://kenkoooo.com/atcoder/?kind=user&name=yurahuna

レーティングはAGC001以降のやつ。青の上の方という感じ。こどふぇすで落としたのがもったいなかった。

問題数でいうと553問解いた。来年中にARCも全部埋めたい。

Codeforces

f:id:pakapa104:20161201220537p:plain http://codeforces.com/profile/yurahuna

これも青の上の方という感じ。来年はdiv2 3,4完を安定させてdiv1に行きたい。

AC数をhadroriさんの修行で確認したところ、104問だった。

topcoder

f:id:pakapa104:20161201221126p:plain https://www.topcoder.com/members/yurahuna_/details/?track=DATA_SCIENCE&subTrack=SRM

topcoderはつらくてあまり出ていないが、最近はkoyumeishiさんのSRM埋めをやっている。来年は黄色にしたい。

yukicoder

f:id:pakapa104:20161201221243p:plain 🍡yurahuna - yukicoder

yukicoderはアルゴリズムを初めて勉強したときにタグ埋め(ここからタグごとのページに飛べる)でお世話になった。226問解いたらしい。

AOJ

f:id:pakapa104:20161201221619p:plain http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=yurahuna#1

f:id:pakapa104:20161201221744p:plain http://aoj-icpc.ichyo.jp/?aoj_rivals=&sort2_order=desc&year_max=&source4=1&aoj_username=yurahuna&point_max=1200&sort1_order=asc&source2=1&source3=1&source1=1&point_min=100&sort2_by=num_aoj_acceptances&year_min=&sort1_by=point

AOJ-ICPCがメイン。気まぐれでJOI非公式難易度表(5,6あたり)も埋めたりした。AOJ-ICPCは10月頃にそろそろ50000ポイント行けそうと思って埋めまくっていたんだけど、途中で力尽きてやめた。青と黄色の壁が高いので、来年は黄色レベルをしっかり解けるようになりたい。


上記でAC数がわからなかったtopcoder以外のすべてを足すと、553+104+226+244=1127問ICPCの問題がAtCoderとAOJで被っているのを差し引いても1000問は解いたらしい(今となってはやるだけな問題も多いですが)。

最後に

最後なのでポエムを書きます。

僕は割と飽きっぽい性格で、何をやっても続かないことが多かったです。そんな中、競技プログラミングを1年間続けてやってこられたというのは結構驚くべきことです。なぜ競プロを続けてこられたのかと言うと、競プロ自体が面白いのはもちろんなのですが、大きいのは競プロerとのつながりだと思います。Twitterでもオンサイトでも競プロ界の人々、競プロerのコミュニティが大好きでいつまでもここに居たくなってしまいます。競プロをやっていると「なぜこんなに苦しいのに競プロをしているのか…」という気分になることもあるのですが、そんなときは「競プロerたちとのつながりを失いたくない」というのが歯止めになってくれていたように思います。

1年を通して、大きなモチベーションの源になっていたのもオンサイトのイベントでした。RUPCやKUPCなどの各大学による競プロ合宿、CODE FESTIVAL、あるいは競プロer同士のオフ会などです。

そんなこんなで、種々のイベントには今後も積極的に顔を出そうと思っているのでどうぞよろしくお願いします。

来年(今年がまだ1ヶ月あるけど)は、黄色になることと、ICPC国内予選突破を目標に頑張りたいと思います。


Competitive Programming Advent Calendar 2016、明日の4日目はchokudaiさんの「競技プログラマは競プロのコンテストを開いてる会社に就職しろ!って記事」と54k3yさんの「競プロで使いたい✨文字列アルゴリズム達??」です。

CODE FESTIVAL 2016 に参加しました

予選

A

焼肉を食べていたので出なかった。

B

4完したが108分かかり落ちた。冷えた。

C

3完+部分点で通過!

夏合宿や会津合宿で「こどふぇすで会いましょう!」と言いまくっていたのが嘘にならなくてよかった。

1日目

集落を6時半に出発した。なんだかテンションが上がっていて、新幹線の中で過去問の練習コンテストをしていた。11時半頃着いた。

ちょくだいさんやsnukeさんを発見したので声をかける。仕事なので忙しそうだった。見つかった知り合いには挨拶して、席に用意されていた軽食(コッペパンのサンドイッチみたいなやつ)を食べた。

しばらくするとBGMやオープニングムービーが流れてきて、すごいという感じだった(ムービーではみんなのIDがぐるぐるしていた)

本戦

4完+部分点でパーカーを取るぞ!と意気込んでいたら3完で激冷え。

Aは今朝動画で見ていたりんごさんの挑戦状のやつだ、と思いながら解く。AC。

Bを読むが全然わからない。1 + 2 + ... + k を取れるだけとって余った分を他に振り分けるみたいなことをやっていたけどWA。30分くらい取り組んでいたけど光が見えないので、まじか……と思いながらCに行く。

Cは頂点を人と言語で分けて(人,言語)の辺を張れば2乗にならないことにすぐ気づいたので、書く。AC。↓で似たようなことをした記憶があった。

arc061.contest.atcoder.jp

Dは2つ目のルールから使う方がよさそうというのは第一感であった。modをとってiとM-iのやつを貪欲にマッチングした後余ったやつで同じ数字のをマッチングする(0と真ん中(あれば)は自分の中だけ)としたけどサンプルが合わない。それはそうで、同じ数字のペアをできるだけ残さないといけない。ということで奇数個残っているやつから貪欲に使うというのを書いたけどWA。バグってたのか見落としがあるのかわからなかったけど、Bを飛ばしていたので腹をくくってBに戻る。

Bは最大値を決めうちしてあとはいい感じにやるというのを考える。Nをdistinctな正整数の和で表すとき、最大値Mを決めると、あとはN-MがM-1以下のdistinctな正整数の和で表せればよい。そのための必要条件は N-M <= 1 + 2 + ... + M - 1であることだけど、実はこれが十分条件でもあるらしく大きい方から貪欲にやるとできるっぽかったので投げた。通った。終了5分前だった。

以後は安静にして精神の回復に努めていた。

~~~

この後touristのトークライブがあって、これまでの人生で一番「英語を聴けるようになっておけばよかった」という気持ちになった。

ここから割と自由行動になる。メシを食べないとやってらんないですよという気分だったので、メシを食べる。おいしかった(鳥を煮たような洋風のやつとチーズケーキが特に好きだった)。前々から面識のあったYazatenさんやmemphimさん、kazu0x17さん、tubo28たちと話しながら食べていた。ドラクエのマップを歩くのがIDA*だという話が出て面白かった。

歩いていたら高校の同期に出会う。kobae964さんだった。こういう場所で5年ぶりに会えるとは思っていなかったので感激する。

秋葉さんのペアプロを聴く。問題は知っていたやつだったけど、解法が洗練されていく過程がわかって面白かった。

エキシビションマッチを見る。座ってるだけじゃつまらないので立ち見であちこち動いていた。スクリーンがいくつかあってそこに各チームの画面が映し出されていたのだけれど、やっぱり強い人はコーディングも速いなという感じだった。順位表を見ながらみんなで一喜一憂したりして、結構盛り上がった。

あとこれは1日を通しての感想なんですが、りんごさんがずっと徘徊しているのが面白かった。

~~~

そんなこんなで1日目終了。ホテルがみんなバラバラで、徒歩で移動した後はお風呂に入ってすぐ寝た。

2日目

トーナメントなるものがあった。今年初の試みらしい。1日目の成績で8人ずつのグループに分けられ、グループ内で上位4人が通過(Round 1)、4人のグループ2つをマージしたグループからまた上位4人が通過(Round 2)、また4人のグループ2つがマージされ最後は各グループでの順位で表彰(Round 3)という感じだった。ラウンドは各2問で時間が30分,30分,40分と短く、しかも部分点が多い(どの問題にも3個ずつくらいある)ということで、かなり戦略性を問われるスタイルだった。

このときcamypaperさんと初対面して、最初に問題を読んでどっちに賭けるか見極めるのが大切そうという話をしていた。motiさんとも初めてお話できた。

Round 1

Aを読む。Kruskalをいじればいけそう。500点取れる気がしたので書こうかとも思ったが、とりあえずBを読む。

Bの200点はビット全列挙で、400点は区間DPっぽいことをするのかなあという気がした。トーナメントのルールとして正の得点を取らなければ次に進めないとのことだったので、とりあえず正の得点を取ろう思い200点に手をつける。さすがに手癖で書けた。10分くらいでAC。

Aに戻って500点解法(のつもりで実は200点だった)を書いた。Kruskalの判定部分に「sのグループとtのグループをマージするような辺は採用しない」を入れた。Q<=105, M<=4*105なので当然TLEするのだがQ=1の200点分は取れた。

結局、A200+B200でRound 2に進出できた。

終了後は周りの人たちと解法の議論ができて楽しかった。t8m8さんに、A問題はsとtの間にコスト0で辺を張ると考えてよいという話を聞いて、天才かなと思った。

Round 2

Aを見てすぐ「確率だ!逃げろ!」と思ったのでBに行く。

Bは200点なら書けそうな気がしたので書く。4分でAC。順位表を見るとAの200点が解かれていたのでAに戻る。

Aを読むと200点がド自明でビビる。AC。ここまで8分。あとはAの300点を考えていたが、間に合わず。

またA200+B200で、Round 3に進出できた。

Round 3

Aは問題文がぱっと見よくわからなかったのでBへ。

Bは400点分ならセグ木やるだけを感じる。M...Mm...mということは最初に幅固定の最大値を取って、最後にそれらのminを取ればよい。ACしたけど17分くらいかかっていたらしい。

Aの100点は大きい数字から採用すればよさそうと思って書いたがWA。200点はDPだろうなと思うもうまく落とし込めず、そのまま終わった。

結局Bの400点だけで入口から1番近い列グループの1位になってしまった。akiさんがBの満点解法を書いていたらしいので、それが通れば圧倒的に負けていた。

今回はラウンドを1つ勝ち進むごとにステッカーをもらえてそれをコンプするとCODE FESTIVALのロゴが出来上がる(+ちょっとイラストがある)という感じだったのだが、そのステッカーのコンプ&表彰で登壇をさせてもらえて光栄だった。

トーナメントは、競技プログラミングの「競技」面を強く感じるイベントだった。普段は自明な部分点を取っても学ぶことがないと思い満点を考えにいくことも多いが、今自分が出せるものを最大限活かして勝ち進むというのも楽しいと感じた。GCJとか割とそんな感じなのかもしれない。

~~~

昼を食べる。お弁当争奪戦でキジ肉弁当なるものを珍しさから選んだが、肉が硬くてあまりおいしくなかった。海鮮にすればよかった。

トイレに行ったりしていたらきゅうりさんのライトニングトークを聞き逃した。ちょくだいさんのを立ち見していたけど、ひたすらテンションで押し切っていて面白かった。

りんごさんの挑戦状2(トークライブ)を見た。りんごさんが出すよくわからない問題に競プロ界の強い人たちが答えるというイベント。いろいろゆるくて好き(競プロ界隈のアットホームさを表していると思う)。今回の解答者の皆さんはhogloidさん、semiexpさん、snukeさん、tozangezanさんだった。snukeさんが自己紹介でクソなぞなぞコンテストの戦歴を語っていて面白かった。世界地図のやつを見ていたら皆さん地理力高すぎてビビった。

そして最終イベント、チームリレーへ。

チームリレー

大人数での団体競技ということで不安もあったが、いざ始まってみると結構楽しめた。チームはKチーム(黒)で、海外勢はsevenkplusさん。戦略としては順位順に1問ずつ割り当てて、必要なら適宜相談しながらやるという感じだった。

自分はとりあえずA問題を解いた。さすがにやるだけだったのですぐAC。帰ってきてからは色々ちょっかいを出していた。Cを考えていたutsubo_21さんにシミュレーションだが実装はどうするのが楽だろうと聞かれ、vectorを2段持ってバケツリレーしていくのが良さそう的なことを言った。Fを、担当していたnkshnさん&既にBを通していたt8m8さんと一緒に考えた。切る回数を最大化するには 1, floor((N-1)/2), ceil((N-1)/2) と切るのが良さそうで、これを使えば二分探索で解けそうということを言った。あとはパソコンの順番が回ってくるまで一緒に紙コーディングをしていた。割と翻弄してしまって申し訳なかった。

以降は強い人たちが既に解法を作りきっていてあまりすることがなかったので、レッドブルを飲んでいた。後半の問題の解き方をdrafearさんやsortreewさんに教えてもらったり、Kを解くsevenkplusさんの姿をみんなで見守ったりしていた。J問題が面白いと思った。

~~~

あとは表彰式。川柳とか太鼓の達人とかいろいろあったけど自分はノータッチだったのでひたすら拍手を送る機械になっていた。書道コーディングでまさかの芸人書道家が出てきて面白かった。natriumさんが「劣モ」をリクエストしていてさすがだったのと、「十億七」は普通にかっこいいので欲しかった。

表彰式が終わるとついにこどふぇすも終わりで、関西勢と一緒に新幹線に乗って帰った。駅弁の牛肉弁当がおいしかった。

まとめ

CODE FESTIVAL、とても楽しかった。コンテストは良問揃いだったし、一口にコンテストと言ってもいろんな楽しみ方があるのだと思った。イベント面でも有名な人の話を聞けたりして貴重だった。

競プロ界の知り合いたちに再会できたのもよかったし、初めてお話しできた方はたぶんもともと名前を知っていた人だけでも10人以上いて、またどこかで会えるといいなと思った。今回お話しできなかった人もいるが、競プロをやっていればまたいつか出会えるだろうからいいということにした。

ぜひ来年もやってほしい。もしやるならばぜひ出たいし、出られるように頑張りたい。