ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

会津大学競技プログラミング合宿2018参加記

ということで、9/19~9/21に行われた、会津大学の競プロ合宿に参加してきました。


目次


一日目

立命館大学の方々のセットで3時間8問のものでした。
チームはACPC_KotonohaSistersで、
とまとさん(@25__toma)、怒髪さん(@dohatsutsu)でした。

問題の担当ですが、自分がAとC、とまとさんがBとD、そして怒髪さんが全体の考察を担当しました。
コンテストページはこちらになります。

A問題

解法についてはこちらを。
…愚直にシミュレーションでいいかーと思っていたら、一回数えるだけで答えになっているといわれたのでなるほどと思いながらそれを書き起こしました。

B問題

積分をすると負けになるらしいです。制約を見ると、答えが球になることが確定しているので、体積を求めるコードを書いて終わりだそうです。
自分の解法についてはこちらになります。といっても解説そのままですが…

C問題

解法についてはこちらを。
一瞬、これどうやるんだろう…って思っていたら解法が天から降ってきたので、怒髪さんととまとさんがBの考察を行っている隙に実装しました。まぁ思いつけばあとはなんとでもなりそうかな、という感想です。

D問題

これぞ実装系、という感じの問題でした。
右手法を書いたことがないのと、あまりsetを使ったことがなかったので、とまとさんと怒髪さんに実装をお願いしました。
バグが取り切れなくて間に合いませんでしたが、バグを取り切った後でもTLEになってしまっていたようです。何も力になれず申し訳ないです…
自分の解法はこちらです。

E問題

考察がわからず悩んでいると、怒髪さんが実装してあっという間に通してくださいました。
単純な貪欲法で前から見ていくのに加えて、一つ先の要素を見る場合も加えるとうまくいくようです。
自分の解法についてはこちらになります。

F問題

虐殺問題。残った時間で自分はDの実装に参加できなかったので、F、G、Hのどれかをやっていくしかなかったのですが、Gは怒髪さんが考察を終わらせていてセグ木の実装系だと判明していたためとばしました。
H問題はさすがに最後にあるので無理だろう、と重いランキングの様子を知っていたもののF問題を考えてみることにしました。
が、結論から言うと何もわからなかったです。
まぁほかの上位の方々が最後の方まで誰一人通せていなかったのでそれはそうと思いましたが…

G問題

セグ木を3段階の入れ子にする問題です。セグ木をRMQしか書いたことがないのでおそらく間に合わない、そしてDの実装をした方が可能性がありそうということで切り捨てられました。ですが数分でこの考察を終わらせた怒髪さんはさすがですとしか言いようがありません…(構文解析、ときたらこういうパターンがなくはないのでしょうか?)

H問題

問題を読み、1分くらい考えて離脱しました。最小カットなんですね…

感想

ということで4完でした。序盤の簡単な部分を通すことぐらいしかできていないので力不足を実感しました。とまとさん、怒髪さんありがとうございました。


二日目

会津大学の方々のセットで5時間12問のものでした。
チームは ACPC_ba で、
goodbaton(@goodbaton)さんとのペアでした。

自分は、A、C、Dを担当しました。
コンテストページはこちらになります。

A問題

自分の解法はこちらになります。
とりあえず上の方から貪欲法をしていきましたが、実はすべて500の倍数であるため、500についてのみ考えればいいらしいです。

B問題

実は最初自分が解く予定の問題でした。
めんどくさそうなので先にCを解き、そのあとこの問題に戻り実装をしたのですが、普通に考察が足りていなかったのでgoodbatonさんに通していただきました。
はやく片方のチームの人数を0にしたいので、片方はできるだけ相手が生き残るように、もう片方はできるだけ相手を倒せるように攻撃をしていきます。これは2パターン存在するので、それぞれについて調べた後小さい方を答えにすれば良いそうです。
自分はお互いが常に生き残るようにしか考えていなかったのでもちろん通りませんでした。
自分の解法はこちらになります。

C問題

解法についてはこちらを。
今回の合宿中の3つのB問題、どれもCより難しいような気がします...
Cは割とサクっと通せたのでいいのではないかなと思います。

D問題

自分の解法はこちらになります。
とりあえず幅優先を書いて更新していけばいいのかなぁと思っていたのですが、普通にTLEをしてしまったので、考察で押し通すことにしました。
個数制限のある重複順列の式や配列の添え字関係で、例によってバグをたくさん生み出してしまったのでかなり時間がかかってしまい、goodbatonさんにデバッグを手伝っていただき、答えが合わないケースをあぶりだしてもらいました。
なんとか通せたのでよかったですが…

E問題

goodbatonさんが、原点から、1日目に食べたドーナツの中心座標に引いた直線の傾きを求めればいいということを発見したのですが、なぜか通らなくて数十分二人で悩むハメになりました。
sample2が実はこのコーナーケースにあたっていて、実は1日目に食べる範囲は、もともとのドーナツの範囲からはみ出している可能性がある、というものになっていたのですが、先ほどの直線の式でもたまたま通ってしまうため、気づきにくい、というものでした。
この問題の制約を見ると、xとyが整数という表示がどこにも存在しないのですが、実は整数であるみたいです。
かなり時間を取られてしまいました。
自分の解法はこちらになります。

F以降

自分がDの実装をバグらせていたり、EやHについて考えている間に、気づいたらG、I、Kが解かれていました。
特にKはオンサイト上でのFirst ACになっていたみたいです(似たような問題を解いたことがあるとおっしゃっていました)。
後日解いたI問題の解法はこちらになります。

感想

割と簡単な部分も手をお借りしてしまったので、申し訳なかったです。
2人ペアはかなり忙しく、お昼ご飯を食べる時間がない上、どうしても相談をするとPCでの実装が何もできなくなってしまうので、個人個人で別の問題を解く時間が多く、最初の数時間はお互いがバグを抱えていた関係でなかなか正解数が伸びませんでしたが、結果的にgoodbatonさん一人で怒涛の追い上げをしてくれました。本当にありがとうございました。


三日目

北海道大学の方々のセットで、3時間7問のセットでした。
チームは acpc_yonkanRTAで、
ばたこ(@btk15049)さん、kawabys(@s1230151)さんとのチームでした。

自分はAとDの実装を、ばたこさんがBとEに加えてほぼ全ての問題の考察とデバッグ、kawabysさんがCの実装を、そして自分とkawabysさんの2人でFを解きました。
コンテストページはこちらになります。

A問題

自分のチームの解法はこちらになります。
はい、バグりました。
普通に3重ループ回せばいいものを再帰で書き始めてしまい、結局ループに書き直したのですが、それでも開始と終了関連で細かいところのミスが目立ち、ばたこさんにデバッグをしてもらいながらやっとのことで通しました。ほかのチームはほとんどすんなり通していたので、実装力の差を改めて感じました。

B問題

愚直にやると通らないのでいろいろ工夫をする必要があるのですが、実装がかなり重いらしいので、ばたこさんにすべてお任せしてしまいました。
自分の大学の友人は割とBを実装した人が多かったみたいで、一人ですごいなぁってコンテスト終了後に思っていました。実はコンテストが終わってから問題を読んだのですが、Aをバグらせた今自分にできる自信はあまりないです。
自分の解法はこちらになります。

C問題

これもコンテストが終わってから問題を読みました。やりたいことはなんとなくわかるのですが、やはりAをバグらせた今…
自分の解法はこちらになります。

D問題

チームの解法はこちらになります。 Aを終わらせた時点でDの解法をばたこさんが見つけてくださっていたので、それを自分が実装することになりました。
言われた通りに一発で実装できなくて少し悔しいですが、Aほど大変なことにはなってなかったのでまだマシかなと思います。

E問題

コンテスト後の解説を聞いてへぇ~とはなりましたが、実装する方針が全く見えていないので、時間があるときに実装しようかなと思っています。

F問題

チームの解法はこちらになります。
3日間の中で唯一、後半の問題で自分のコードが通った+大方の考察をした問題です。
実験をすると割と貪欲にやってしまっていいことがわかるので、必要な情報は結構少なく、1クエリあたりO(|S|)ぐらいで求めることができます。コーナーケースをkawabysさんに見つけていただきました。
コンテスト後の想定解の解説を聞いているとき、そんな問題だったっけ…?って思うレベルには違う解法だったのは秘密です。

G問題

既出の問題らしいです。
kawabysさんの考察によって区間DPを使いそう、というところまで出ていたのですが、結局時間が足りず解けませんでした。

感想

序盤の問題は3日間の中で一番ボロボロでしたが、後半の問題はまぁFの基本方針を自力で解けたので良かったのかな?と思います。
考察よりかはまだ実装系の方がいける、と思っていたのでA問題は割とトラウマレベルでした。いまだになぜ再帰を書こうとしたのかわかりません...

まとめ

3日間、普段とは全く違う環境でさまざまな人とチームを組むことができたのは幸せなのではないかなと思います。来年以降は、むしろひっぱっていけるような存在になれるように精進を続けていこうというモチベーションが生まれました。かなり問題のストックがたまったので、1問1問も重いですし地道に消化していこうかなと思います。参加者の皆様、3日間貴重な経験をさせていただきありがとうございました。

ということでここからはおまけです。
といっても写真を羅列していくだけです(たいしたものを撮っていないです)。

行きの新幹線の様子です。思ったより時間が短くてあまりできませんでした…(帰りもずっとやっていました)

会津若松駅です。この時点で、そこそこの参加者の方々が近くにいたため、多くの人がここで写真を撮っていました(もちろんツイートもしていました)。

大学の入り口です。木の陰になっていて文字が何も見えないです。

名札です。とくに書きたいことはないです。エミリアはかわいいですね。


1日目の夕ご飯です。喜多方ラーメンです。

1日目の夜です。この後もボードゲーム等をしていました。


2日目の写真は存在しません。気づいたらその日が終わっていました。


お昼ご飯(の後)の写真です。会津大学の学食で食べました。元々はこちらになります。


会津大学ドミニオンというボードゲームをしている様子です。これをしていたおかげで帰りの電車に乗り遅れかけました。


ということで以上になります。観光はあんまり(ほぼ)していないのですが、それでも会津にしかないものに多少は触れていたと思います。
また来年も参加できるといいですね。