AtCoder Beginner Contest 027

 ものすごく考察回。

結果

 400/400 103:03(1) 14位相当


 開始時刻 2017/08/14 21:40:00 提出履歴

A: 長方形 - AtCoder Beginner Contest 027 | AtCoder

 1:19(WA)1:52(AC)
 同じ長さのペアをひとつ見つけて、そのペアに含まれない一辺が答え。改行を忘れてWA。

B: 島と橋 - AtCoder Beginner Contest 027 | AtCoder

 11:27(AC)
 橋それぞれに対して、かける必要があるか否か判定していく。橋をかける必要があるのは、橋の左にいる全住民がキャパシティ丁度でない時。Bにしては難しい問題だと思う。

C: 倍々ゲーム - AtCoder Beginner Contest 027 | AtCoder

 80:24(AC)
 個人的にはD問題よりも難しい。
 Nが二進数でd桁で表される時、d-1回目の操作をする人(以下LA)が、その操作でNを超えなければ勝ちである。dが偶数ならLAは高橋君、奇数なら青木君である。
 LAは自身の操作で作れる数字をなるべく小さくしようとするし、LAでない側は自身の操作で作れる数字をなるべく大きくしようとする。何処かのタイミングでLAの勝敗が決まる部分があるので、そうなればあとは勝者を出力すればいい。ビットシフトをうまいこと使うとできる。
 今自分で解法書いてて思ったけど、もう少し簡単に解けた気がする。

D: ロボット - AtCoder Beginner Contest 027 | AtCoder

 98:03(AC)
 順当に考えれば得点を確定させるタイミングは+-だけど、得点は各Mで正に移動するか負に移動するかの変数によって決まる関数なので、そういう方向で考える。具体的には、Mで正に移動する時の影響力は、それ以降の+の数だけ上がり、-の数だけ落ちると考えればいい。
 こうすると、各Mに関して正に移動する時の影響力が計算できる。あとは影響力の上位半分を足し、下位半分を引けばいい。

感想

 考察回は解けると嬉しいね。Cでビットに縛られすぎて実装につまづいたのが勿体なかった。