読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

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

AOJ UnionFind LCA

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

問題

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 に参加しました

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人以上いて、またどこかで会えるといいなと思った。今回お話しできなかった人もいるが、競プロをやっていればまたいつか出会えるだろうからいいということにした。

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

AOJ-ICPC 400 インビジブル

ICPC JAG DP ゲーム ミニマックス法

問題

インビジブル | Aizu Online Judge

D: インビジブル - JAG Contest 2016 Domestic | AtCoder

解法

先手はスコアの最大化、後手は最小化を目指すのでミニマックス法で解ける。

先手, 後手のデッキでスタックにつまれている区間をそれぞれ[l0, r0), [l1, r1)とすると、状態として(l0, r0, l1, r1, 今どちらの手番か, スタックが空になってから何回パスが連続したか)を持つだけでよいというのがポイント。パスで得点が変化するときには相手が最後に置いた妨害カードより上にある自分の得点カードの和がわかればよいので、実装ではこれらも引数に入れると楽だった。

あとこれはインビジブルあるあるなんですけど、スタックが空になってないのにパスの回数を足して死んでいた。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8A%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf

gist.github.com

AOJ-ICPC 300 Line Gimmick

ICPC

問題

Line Gimmick | Aizu Online Judge

解法

実装しんどいなーと思いながら書いたら一発で通って最高↑↑な気持ちで解説を見たらすごい簡単で悲しくなったので書きます。

ある'>'(=R0)からスタートすると、向きが変わるのはR1より右側にある1つ目の'<'(=L1), R0より左側にある1つ目の'>'(=R1), R0より右側にある2つ目の'<'(=L2), ...という風に続きます。左から順にR0をすべて試すとすると、どこが最後の反射になるかをしゃくとり(?)っぽく更新していくことができます。詳しくはコードのようにやりました。

ところがしゃくとりっぽくやる必要はなくて、累積和だけわかればどこが最後の反射かわかります。

mayokoex.hatenablog.com

実は n - min(左端に連続する'<'の個数, 右端に連続する'>'の個数) でいいらしい。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf