トップ > プロコン > ABC211

ABC211

プロコン

E以外の5完。全体的に重かったけど、典型ではあるしどうにかスピードを出せた。

A - Blood Pressure

A問題で知らない言葉を出すな。今見るとちゃんと加重平均みたいになってるね。コンテスト中は時間がないので言われた通りに計算式を打ち込む（式の意味がわかってないので時間がかかる）。

B - Cycle Hit

vector<string>を2つ用意して、片方を入力、もう片方を模範解答とし、両方ソートして一致するかを見た。

（解説を見て）あー、全部違ってればいいのか。難しいなあ。自分の解法も悪くないと思うけど、実戦では色々思いつかないといけないから。

C - chokudai

典型90で見た気がするDP。Cにしては難しいけど典型だから300点になってほしいということか。in-placeにしたほうがコピー要らずで楽そうだったのでそっちに切り替えた。最初、chokudaiに同じ文字がないか時間かけて目で確認してたけど、関係なかったか。8文字中何文字まで取ったか9通りを持つ。慣れたもんだ。

D - Number of Shortest paths

最初ダイクストラを貼ったアホ。経路復元みたいにして配っていこうかと思ったけど、これはBFSのほうが簡単。BFSしながら配ると、全ての距離dからd+1に配るというシーケンスができて明快になる。最短距離を事前に求める必要もない。ここは少し時間がかかった。

E - Red Polyomino

Kの制約を見落としてDFSが無理だと思ったのでFに専念していた。「Avoid War」みたいなDPも考えたけど、非連結なものが下で連結になるケースがあるのでまとまらなかった。

Fが解けて戻ってきてしばらくするとKが8以下であることに気づく。DFSができそうなので最初に考えていたの（開始地点を全通り試し、開始地点より上（同じ行なら左）には行かないようにする）を書く。残り10分を切っていたが、書き上がってしまった（実装力あるね）。しかしサンプルが全く合わず。しばらく悩んで、番兵を置くためfor文を書き換えたとき1からN未満（正しくはN以上）にしてしまっていたことに気づく。あと、グローバル変数にj0を使ってコンパイルが通らなかったり、同じマスを2回通らない処理を忘れていたりもしてた。だが、そもそもこのDFSでは経路の異なる同じ塗り方を区別できない。残り1分とかでは何も思いつかなかった。今気づいたけどDFSでは一筆書きしかできないじゃん。だからサンプル出力より少ない値になってたのかあ。

（追記）解説を見てAC。上で書いた開始地点より前に行かないようにするやつ、試した開始地点は黒く塗るという楽な方法があると知った（天才かよ）。問題はDFSで、これは思いつかない。俺は64頂点のグラフでDFSを考えていたのに、実は頂点数2^64（探索で訪れる頂点だけでも10^5とか）のグラフでDFSするのが解法とか、思いつけるわけがない（経路数ではなく訪れた頂点数が答えになる）。本当に頭が固い。

F - Rectilinear Polygons

やったばかりのPASTと同じ問題に見えたので、「モノクロデザイン」の自分のコードを持ってくる。こちらは座標圧縮済み（というのも変な言い方だが）なので楽。が、縦の辺のどちら側が多角形の内側なのかがわからない。手段はあるけど短時間の考察と実装でできそうなものを探す必要がある。このとき、入力の添字を間違えていてサンプルを試したときの挙動が無意味なものになっていたこともあり混乱する。辺の向き（角度）を追って1周どちらに回ったかを見るのが本筋っぽいけど、何も考えたくないので多角形の内角の和の公式を使い、角度の和から内角の和を引いて思った向きなら0になりそうでないなら0以外（何になるかはもうわからん）になることで判定した。向きは外積で判定した。どっちがどっちなのかは気にしなくていいのでまだ楽だった。最終的には判定を逆にすると出力がマイナスになるようになったので、想定通りの挙動でOK。入力を受け取ったら2つはみ出させ（辺同士の角度を見るので前後を含む3頂点が必要）、まず向きを判定し、逆だったらreverseする。よくわからんけど上向きの辺は右側が内側らしいのでそう書く（手で試してそうだったけどわかってない（この辺り、適当な基準点をとってこの多角形の面積を外積で求めようとして基準点から見てどっちが内側とか他のアイデアもあったけどコンテスト中はとにかく時間がかからないものを選ぶしかない（悲哀）））。あとはクエリと共にソートして区間加算と点取得。これはBITでできるんだったと思い出す。PASTもそうだったのかなとか思いながら。ここまで来るとあっさりサンプルが通り提出してAC。嬉しい。

（追記）えー。言われてみればそうだけど、なんで知らなかったんやこれ。で、反時計回りだと左側が内側になる。コンテスト中に上向きの辺の右が内側に（必ず）なる理由がわからなかったが、時計回りに揃えていたということで、そもそも（辺の向きに対して）左右どっちが内側になるか揃えるために向きを判定してたので揃うのは当たり前。