会津大学競技プログラミング合宿2017に参加してきました
いろんな人の参加記を見ていたら自分も書きたくなったので書きます.
9/18〜20で会津大学の競技プログラミング合宿に行ってきました.
3日間の日程があってそれぞれ立命館大学, 会津大学, 北海道大学が作問した問題をICPC同様のチーム戦で解くという感じでした.
ちなみに, チームはほぼその場で強さが偏りすぎない程度に適当に決めてました.
実は初めてのオンサイトコンテストだったのでACすると風船が上がる感じとかとても楽しかったです.
コンテスト自体はAOJ上で行われていて, オンラインで参加している方もたくさんいました.
Day 1
東京駅を9:00に出発, 12:00頃に会津若松駅に到着.
郡山まで東北新幹線使うとかなり近いですね.
そして駅からしばらく歩いて会津大学に到着.
1日目は立命館大学が作問した問題セットでした. ACPC2017Day1 (解説)
チームは会津大学の方二人と組ませていただきました.
自分はB問題を解いたのですが, バグらせまくって本当に申し訳ないという感じです...
B問題を通した時にはすでにA, C, Dが解かれていました.
残ったE, F, Gは結局解けませんでした, 残念.
合宿終わった後に全部問題ちゃんと見た感想です.
- A: 丸付け (解答)
- 2文字ずつ見ていけばO(N)で判定可能.
- B: 全日本帰りたい協会 (解答)
- 次の人を迎えに行くまでに1Fに戻っても間に合うならば, 1Fに行くのが常に最適.
- ...なのですが, 結構チェックしないといけない箇所が多かったりして実装がしんどいです.
- ちなみに, 僕は最初の人を迎えに行けるかどうかの判定を忘れて2WA出しました.
- C: ツイート数 (解答)
- DFSしながら葉からの最短距離を求めていけばOK.
- D: 次元旅行 (解答)
- i次元からi - 1次元にだけ辺を張ってダイクストラすればいいというのが面白かったです.
- 普通に全部に辺を張ったらMLEしたので解説見ました.
- E: 敵襲から守れ
- まだACできてないです.
- あんまり最大フローがよく理解できてないのですが, この期に理解してしまいたいので頑張って通したいと思います.
- F: Steps
- ランダムウォークではよくあるタイプの問題らしいのですが, あんまりちゃんと理解できてないです.
- G: Cryptex
- めちゃくちゃ頑張ると解けるらしいです(遠い目).
Day 2
二日目は会津大学が作問した問題セットでした. ACPC2017Day2
僕 + 立命館の方 + 社会人の方の3人チームでした.
自分はA, C, F, Lを解きました.
A問題は人生初のFA(オンサイトのみ)で結構嬉しかったです.
FAなので風船にかわいい動物がついてきました.
圧倒的にチームのみなさんが強くてオンサイト1位でした.
以下各問題の感想です(解けたもののみ).
- A: Clock (解答)
- 割って余り求めたらいけるやろ〜とか言って提出したら通りました.
- 人生初オンサイトFAやったね!
- B: Hating Crowd (解答)
- ちょっと面倒ですが愚直にやると解けました.
- C: Palindrome (解答)
- N^2が間に合う制約なので, 回文にするときのペアを探してから辞書順に貪欲にとっていけばOKです.
- ちょっと実装がややこしくてバグらせましたが...
- D: Fissure Puzzle Easy (解答)
- 白いマスの連結成分の数を数えて1引いて3で割ると答えが出るというちょっと面白い問題でした.
- 領域を4分割していくのでも解けるみたいです.
- E: Piano (解答)
- 連続して増加, 減少している部分の最大を求めれば解けます.
- F: nCm (解答)
- 問題を見たらすでに考察がされていたので, その通りに実装したら通りました().
- 結局2^kのところだけ見ればO(logN)で解けるようです.
- I: Making Pairs (解答)
- 木の上でマッチングをする問題.
- DFSしながら, マッチしていないものと貪欲にマッチさせていけばOK.
- L: RMQ 2 (解答)
- クエリはQ個しかないので, 全部コピーする時は以前に変更があった箇所だけコピーすれば間に合います.
- コンテスト時間中に通せてよかった...
コンテスト後はリクルートコミュニケーションズのアドテク部さんのおかげで無料で懇親会に参加することができました.
(その謎のお金は一体どこから出てきてるんでしょうねぇ......)
Day 3
三日目は北海道大学が作問した問題セットでした. ACPC2017Day3
僕 + 会津大学の方 + 立命館大学の方みたいなチームで臨みました.
B問題が鬼難しくて, Bとは何かについて哲学的な考察をしていました.
以下問題の感想です.
- A: A-Z- (解答)
- 一文字前の出てきた文字を覚えておき, それ以下の文字が出てきたら答えを1増やすみたいなことをしました.
- B: えびちゃんと数列 - Ebi-chan and Integer Sequences - (解答)
- 等差数列の和を求めると答えが出るのですが, N = 1がコーナーケースになっていたり, modを取るのが足りないとWAしたりと大変でした.
- C: たったひとつの部分列 - Unique Subsequence - (解答)
- 部分列を前からマッチングさせた結果と後ろからマッチングさせた結果が一致していればユニークで, そうでなければユニークでないと判定できます.
- D: 優柔不断 - Indecision - (解答)
- AOJを信じて10^8のDPを投げると通ります.
- E: たい焼きマスターと食べ盛り - Taiyaki-Master and Eater (解説)
- 二次元BITを使う問題です.
- 初めて二次元BITを実装しました(Githubで栽培してます).