トップ > プロコン > ABC289

ABC289

プロコン

6完。時間かかる回だった。

直前にウンコして水飲んだんだけど、また嫌な感じのお腹になってきて、Cを通した段階でスマホでDとEの問題文を撮影しトイレで読んだ。Dはわりとすぐ解けてEが難しそうだった。

途中で「DREAM PLACE」を口ずさんでいることに気づいて、なんでだと思ったらEの問題名が「Swap Places」だった（placeだけじゃん）。

A - flip

'0' ^ '1' でxorかけた。

あ、'0' が偶数なのをマウスオーバーで確認しておけば ^=1 でよかったのか。'0' ^ '1' も1だからコンパイル結果は同じだろうけど。どっちが実装時間短かったかは微妙だけど文字コードが連続してるのは知ってるし、発想は出てほしかった。

B - レ/V

レ点の仕様を忘れている。しかし問題文を読むと意外と単純な規則なので、レ点のことは忘れて問題文に従う。辺がないところに来たらそこまでのものを逆順に記録する。辺のありうる場所はN-1通りしかないがもう1個加えてそこで残りも入れる（ここが正しい処理になっているか不安で提出前に確認した）。どう実装するかが難しい問題だった。

C - Coverage

久しぶりの全探索。計算量がすぐには見えない。ビットに詰め込めば各集合の情報はintに入って見通しがよくなる。あとは2^M通りについて確認するだけ。実装してて、NとM変数名が逆じゃねって思った。

D - Step Up Robot

ただのDP。配るとわかりやすい。DPテーブルは最初全部0で、モチがあったら1、行ける場所は2、とした。モチは-1にすればよかったな。

（追記）モチを-1にするやつを一応書いた。あと、bitsetでも通りそうなのでやってみて129ms。

E - Swap Places

最終手を考えると、頂点1と頂点Nの色は異なる必要がある。それを判定してさっさとreturnするのだが、マルチテストケースなので入力は全部受け取る必要がある。可能なときの行動回数の最大を見積もろうとしたがよくわからない。高橋君の経路の向きと色を逆にすると青木君の経路の必要条件になって、まあ色々な経路が考えられそう。高橋君の位置と青木君の位置のペアを頂点とするグラフでBFSすれば解けそうではある。他の方法も思いつかないので実装を始めようとするが、計算量が不安。新しく作ったグラフの頂点数はN^2で400万だからけっこう大きい。辺の数は、色が異なる必要があるからそれぞれの移動先の半分と半分の積が2つみたいな。少し考えて、これは縦横に各頂点から出ている辺の数を書いて表を作りマスにはその積を書き込むようにすれば全体でO(M^2)になっている（色関係なく全部辺を張っても400万*2*2で済む（無向グラフなので2倍されるの忘れてた））。O(N^2+M^2)だから大丈夫とはいえ、グラフにしては大きめなので警戒して定数倍をある程度考えた実装にする。辺の列挙は普通に二重ループ。

F - Teleporter Takahashi

操作してから隣の格子点でまた操作することを考える。すると2だけずれた位置に戻る。そもそも操作によって座標の偶奇は変わらない。なのでまずそれをはじく。そうすると、基本的には移動できそうだ。問題は長方形が小さいとき。格子点が1個しかないときは、元の位置と1回操作したした位置のみ。2個のときは、2個が並んでいる方向へは自由に動かせて、もう片方の方向は操作回数の偶奇で決まる。これをうまく書く必要があって大変。1WAを出してしまった（格子点が1個しかないとき2通りしか行けないが4通り行けるコードになっていた）。

G - Shopping in AtCoder store

Gっぽい見た目なので時間がかかりそうなFよりも先にやることを考えたが、ちゃんと読むと自分の手に負える感じではないとわかりFに集中した。

Bはソートしていいし、Cもソートしておきたい。三分探索を思ったが、よく考えるとダメそう。三分探索が使えるような単調性はなさそうであるものの、C_iが大きくなるほど買う人数が増える的な単調性はある（C_iが小さくなって買う人数も減ると単価も人数も減るんで最大にならない）。商品価値最小をまず計算してみると、それより人数が多いところだけチェックすればよくなる。なんとかして計算量を削減できないかと考えていたが、できなかった。こう、ジグザグのグラフに一次関数を足してくみたいなイメージなんだけど、できそうでできない。

（追記）なるほどなあ。まあしかし、自分が考えていた方針の延長にwiter解があったのは嬉しさもある。