BAPC 2018 D - Driver Disagreement
問題
Dashboard - 2018 Benelux Algorithm Programming Contest (BAPC 18) - Codeforces
問題概要
個の交差点がある。交差点
は道が二手に分かれており、左に行くと交差点
に、右に行くと交差点
に辿り着くことが分かっている。また、交差点
からピサの斜塔が見える時は
、見えない時は
という情報がある。
今、自分が交差点か
のどちらかにいることが分かっている。そこから左右の選択を適切にすることによって、ピサの斜塔が見えるかどうかの情報から最初に自分が
か
のどちらにいたのかを特定することは可能か。不可能ならば
indistinguishableと答え、可能ならば最短の操作回数を答えよ。
アイデア
一番素直な方法として思いつくのが今いる位置のペアを管理しながらBFSをするというものだが、これは状態が個あるので、TLEしてしまう。
簡単のために、まず
indistinguishableなのかどうかだけを考えてみる。
以下では、問題をグラフとして置き換え、ピサの斜塔が見える頂点を黒、見えない頂点を白と呼ぶことにする。
頂点と
が
indistinguishableであることの意味について考えてみると、どのように移動してもそのペアの頂点の色は等しいということになる。
つまり、仮想的には同じ頂点にいると考えてしまってもいいと言える。
今、と
が
indistinguishable、かつと
が
indistinguishableであるということが分かっているとすると、と
の関係に注目したとき、直感的にはわざわざチェックするまでもなく
indistinguishableなのでは？と思える。
実際にこれは正しい。
と
が
indistinguishableではないとすると、ある操作(例えば、LLRLRみたいな)によって、の方は黒、
の方は白の頂点にいるという状況が発生しうる。
しかし、上の2つの仮定から、
は黒でもあり白でもあるということになってしまうが、これはあり得ない。
この同値関係が成り立つことを利用して、BFSの状態を減らすことを考える。
以下のBFSではindistinguishableでないペアが見つかり次第ストップするということを前提とする。
「既に2つの状態：と
をチェック済みである場合は
を
indistinguishableであるとしてそれ以降はチェックしない」というBFSを行う。
これはちゃんと機能するBFSとなる。
もし、本当にが
indistinguishableなのであればやっていることは正しいし、
が本当は区別可能だったとすると、BFSが
と
の両方をパスしてしまっていることに反してしまうからである。
このような状態を効率よく管理するためには、UnionFindなどのデータ構造を使えば良い。
この状態のマージによって、BFS内で訪れる状態は個となり、十分に速い。
元の問題に戻ると、区別可能な時は最短の回数が必要になるので、BFS内で同時に回数も管理する。
実装(C++)
続きを読むACM-ICPC 2018 Asia Yokohama Regional Contest に参加しました
2018年12月8,9日に横浜でACM-ICPC 2018 Asia Yokohama Regional ContestにWAsedACというチームで参加しました。
メンバーはimulan(私)、ryoissy、yamadで結果は60チーム中10位でした。
早めに書こうとは思っていたのですが、結局遅くなってしまいました。簡潔に参加の感想を書きます。
1日目
お昼ごろからregistrationだったが、その前にコーチと4人で、registrationの前に中華街でご飯を食べた。この日はリハーサルとチーム紹介をした。
リハーサルでは__int128が使えるかとか、sampleをwgetで一気にダウンロードして遊んだりしてたら「正解が無いけど大丈夫ですか」的な感じでスタッフの方が来てすいませんってなった。
夜は近くのビジネスホテルに泊まった。ダブルの部屋に2人で泊まったんだけど、ダブルベッドに2人で寝るのはあまりおすすめできません。
2日目
この日はコンテストだった。コンテストの感想を細かく書く気力はないけど、自分の感想を簡単にまとめると
- 傾向変わりつつあるかと思いきや、なんだかんだ実装量は多かった(めちゃくちゃ問題文長い、みたいなのがないので幸せ
- 序盤悪すぎる(ペナルティが物語っている(+も多いし
- PCの前に座ってから手が止まるシーンがあった(もうちょっと細かいところを詰めておくべき
疲れてて懇親会はあんまり交流できなかった...
3日目の企業見学も(完全に交流が目的になるが)余裕があれば行きたかったけど、行きたい気持ちを抑えて学校に行きました(できれば卒業したいので)。
おわりに
去年に続き、早稲田からは2チームがアジアに進みました。その6人のうち4人は今年で引退となりますが、来年以降もアジア予選に進むチームが複数出てほしいですね。ICPCがあることでなんだかんだモチベを保ってきた自分からしても、アジア予選に進めることは良い経験になりました。来年はそんなチームに多くの風船を配りに行けたらいいなと思います。
