はっぴぃ☆わぁるど

思考垂れ流す肥溜め

ABC027

今回は時間ギリギリで四完。個人的にはA<B<D<Cぐらいの難易度だったきがする。どちらにしろABCにしては難しい。

ABC027へのリンクはこちら http://abc027.contest.atcoder.jp

ぶっちゃけスライド(abc027)が有るので解説はいらないと思うけど備忘録的な意味を込めて。

 

A. 

長方形なので向かい合う辺の長さは等しく、三つの中で等しい組を見つければ残ったものが答えになる。

B.

微妙に時間を食ってしまったB. まず、人口の総数%島の数!=0ならば、島の人口を等しくすることができない。次に順番に島ごとに見ていって、平均値に等しくなければとなりの島に人口を移すと考える。このとき途中で島の人数がマイナスになってしまうことがあるが結果的に問題はない。

C.

Nimゲームっぽい。勝利条件をさぐらなければいけないわけだが、MINMAXとかで1〜100までを試すと法則が普通に見えてくるので答えになってしまうっぽい。僕はそれをやらなかった(気づけなかった)。

Nを二進数にして表記する。桁数を考えてみるとNを超えないで最後の手を打つ番がわかる。(精確にいうとNと二進数で同じ桁を言う方)。よって偶奇で場合分けをする。桁数をmとする。最後の桁を言う方は、N以下になっていてほしい。逆にいうと最後の桁を言わない方は前の段階で大きくしてしまえばいいとわかる。さらに逆にいうと、最後の桁を言う方は大きくされる前に小さくしたい。何がいいたいかというと最適な行動は固定されてる。最後の桁を言う方は全部2倍すればいいし、言わない方は全部2倍+1すればいい。

例:N=100100(2) この場合最後の桁を言うのは先手。先手はなるべく小さくしたい。後手はなるべく大きくしたい。よって10->101->1010->10101->101010となり先手がまける。これをシミュレートすればいい。(もっというと101の段階でもう勝利は決まっている)

 

D.

個人的には結構簡単だと思った。ポイントは+の段階でこれまでの正負方向の移動の数を気にするのではなく、式をMについてくくりだすように、あるMの命令以降にある+,-の数に注目してもいいことに気づけるかだと思う。

ここで幸福値を最大化したいので+,-の和がプラスの奴は全部正の方向に動くようにしたいが条件文に原点に戻っていなくてはならないとあるので、和が大きいものから順に割り振っていく。

ここまでの操作で最大のオーダーはソートのO(MlogM)である。よって十分間に合う。

命令以降にある+,-の数の数え方だが、O(n^2)にしないように。(この場合はおそらく通るけど)