AtCoder Beginner Contest 243に参加しました。
結果
A,B,C,Dの4問正解でパフォーマンスが890でした。 C問題がちょっとしたバグで何度も1WAして焦った。 E問題は後少しで解けると思うけどもう1工夫が足りなかった。
A - Shampoo
問題文の通り愚直にシミュレートすれば一応ACできる。
V<A → V-A<B → V-A-B<Cを順番に確認して比較結果がFalseになったタイミングでFかMかTを出力すれば良い。1日だと誰も不足しないかもしれないので誰かが不足するまで延々と繰り返す。
あるいは少し賢く、Vを(A+B+C)で割った余りに置き換えてから上記の比較をすれば最大3回の比較で答えられる。(A+B+C)で割った余りに置き換えることで3人が使っても不足しない日の消費量分を一括で減らせるので、はじめてシャンプーが不足するXデーのシミュレートができる。
B - Hit and Blow
Nの大きさ的に愚直にシミュレートしても間に合うと思う。その場合は2重ループを使うのでになる。
ちょっと頑張ればで答えられる。
mapや連想配列を使ってA,BそれぞれA[value]=index,B[value]=indexとしてデータを保存しておき、
for-each文を使ってAの要素を順番に見て、value,indexを取得。B[value]が存在するかどうかとB[value]の値が取得したindexと一致するかどうかを確認することで、
AとB両方に存在するけどインデックスの位置が違う場合、AとB両方に存在してかつインデックスの位置も同じを判断できる。
C - Collision 2
愚直にシミュレートするのもややこしそうな問題だと思う。 問題文を読んで少し考えると以下のことがわかる。
- 同じy座標の人たちだけに注目すれば良い。
y座標が異なる人とは衝突することはないから。 - 同じy座標にいる人達で、右に行く人の初期X座標 ＜ 左に行く人の初期X座標 となっていればその2人は衝突する。
なので結局、y座標ごとにグループ分けをして各グループでどれか1箇所でも 右に行く人の初期X座標最小値 ＜ 左に行く人の初期X座標最大値 を満たしていれば衝突して、どのグループでもこの条件を満たさないときは衝突しない。 細かい工夫としてグループの人数が2人以上のグループだけ条件を満たすかどうか確認していけば少し探索する量を減らせると思う。
D - Moves on Binary Tree
完全二分木の親や子へのインデックスの移り方を知っていればあんまり困らない問題だと思う。
Uが来ると親に戻るので直前の子への移動はなかったことにできる。(子に行った直後に親に戻ると、同じところに戻ったことになるのでその移動2回分がなかったことになる。)この考えでSを圧縮しようとするとスタックを使うのが楽だと思う。Sを先頭からスタックに入れつつUが来るとUはスタックに入れずスタックの1番上を取り出せばLかRとUの2文字を文字列から除去できる。
Sの最後まで確認したら順番に取り出して文字列に戻せば余計な移動を圧縮した文字列に変換できる。
（Sの長さが最大でもなので圧縮しなくてもTLEにはならない気がする。）
あとはSを順番に見ていき
- Uが来たらXを2で割る。
- Lが来たらXを2倍する。
- Rが来たらXを2倍して1を足す。
を順番に処理すればいい。 Pythonなら桁数の上限がないのでこれだけでACできると思う。
C++などの言語だと扱える値には上限があるので愚直にシミュレートしているとどこかでオーバーフローする。
処理の内容が2倍とか2で割るとかだけなので2進数を連想して、2進数で考えてみると
- Uが来たら1番下の桁を落とす。
- Lが来たら最後尾に0を付け足す
- Rが来たら最後尾に1を付け足す。
とすることで現在位置を管理できる。 なのでXを2進数表記に変換した文字列で管理してSの文字に応じて、文字列的に1番最後の文字を削除する、0を最後尾に付け加える、1を最後尾に付け加えるのいずれかを順番に処理していく。 最後に2進数表記を10進数表記に戻して答える。
E - Edge Deletion
難しかった。サンプルはACできるけどテストケースだと半分くらいWAになった。
Nが十分小さいのでダイクストラをN回実行しても、ワーシャルフロイド法ので一気に全対地間分のコスト計算でもTLEにはならない。
今回はN<300とNがE問題でグラフを扱うにしては小さすぎるとメタ読みをしてとりあえずワーシャルフロイドで処理することにした。（N回ダイクストラ法を行ったほうが多少は計算時間が早い気はするけど。）
全対地間分のコスト計算が出来たとして、そこから削除できる辺を探す方法がわからなかった。
計算したから
への距離と
を比較して
が小さいなら辺
は削除できるかもしれないなとは思ったけど、その辺が頂点xの持つ唯一の辺の可能性を考慮すると、どんな条件の場合はその辺が削除できるといい切れるのかわからなくなった。
