A – Sharing Cookies
問題文
すぬけくんは 3 匹のヤギにクッキーを渡したいです。
すぬけくんは A 枚のクッキーが入った缶と、B 枚のクッキーが入った缶を持っています。
すぬけくんは A, B, A+B のいずれかの枚数のクッキーをヤギたちに渡すことができます。
3 匹のヤギが同じ枚数ずつ食べられるようにクッキーを渡すことが可能かどうか判定してください。
制約
- 1 <= A,B <= 100
- A,B はいずれも整数
考えたこと・解答
素直にA, B, A+Bを3で割った余りが0かどうかチェックすれば良いです。どれかひとつでも割り切れればOKです。
B – Snake Toy
問題文
すぬけくんは N 本の棒を持っています。
i 番目の棒の長さは l_i です。
すぬけくんは K 本の棒を選んでつなげて、ヘビのおもちゃを作りたいです。
ヘビのおもちゃの長さは選んだ棒たちの長さの総和で表されます。
ヘビのおもちゃの長さとしてありうる長さのうち、最大値を求めなさい。
制約
- 1 <= K <= N <= 50
- 1 <= l_i <= 50
- l_i は整数
考えたこと
ソートして上からK個取れば良いです。ソートがO(nlogn)でそれがボトルネックです。
解答
考えた通りでした。
C – Splitting Pile
問題文
すぬけくんとアライグマは N 枚のカードの山を作りました。カードの山の上から i 番目のカードには整数 a_i が書かれています。
N 枚のカードを分け合うことにしました。
すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。
このとき、すぬけくんもアライグマも 1 枚以上のカードを取る必要があります。
すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれ x,y として、|x-y| を最小化したいです。
|x-y| としてありうる値の最小値を求めなさい。
制約
- 2 <= N <= 2 * 10^5
- -10^{9} <= a_i <= 10^{9}
- a_i は整数
考えたこと
C問題は全探索。偉い人がそう言ってました。
この問題も御多分に洩れず全探索すればO(n)ですむのでいけそうです。
解答
考えた通りでした。
D – Fennec VS. Snuke
問題文
フェネックとすぬけくんがボードゲームで遊んでいます。
このボードゲームには 1 番から N 番までの番号がついた N 個のマスと、マスどうしをつなぐ N-1 本の道が存在しています。 a_i 番のマスと b_i 番のマスは i 番目の道を介して隣り合っています。どの 2 つのマスも隣接するマスをいくつか辿って必ず辿り着くことが可能です。すなわち、グラフ理論の言葉を用いると、マスと道から構成されるグラフは木です。
はじめに 1 番のマスは黒く、N 番のマスは白く塗られています。その他のマスはまだ色が塗られていません。
先手のフェネックと後手のすぬけくんは残りのマスに交互に色を塗ります。
自分の手番において、2 人はそれぞれ以下のような行動を行います。
- フェネック：黒く 塗られたマスに隣接したマスであって、色が塗られていないマスを 1 つ選んで 黒く 塗る。
- すぬけくん：白く 塗られたマスに隣接したマスであって、色が塗られていないマスを 1 つ選んで 白く 塗る。
手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。
制約
- 2 <= N <= 10^5
- 1 <= a_i, b_i <= N
- 与えられるグラフは木
考えたこと
とりあえずグラフ書いて全辺重み1として最短経路の情報を使うのかな〜と思いましたが、それではどの点を選んでいけばいいのかわかりません。
そこでこのゲームに勝つには相手の行ける点を潰すように動けばいいんだな、と考えました。
相手が行ける点ってどこだろうと考えた時に、相手のスタート地点からの距離が近いほど相手が行ける点指数が高いんじゃないかと考えました。
証明はしていませんが軽く手を動かしてみても正しく動いたので一回これを実装してみようとなりました。
実装としては単純でダイクストラで点1と点nからの距離を求めておき実際にシミュレートしてやれば良いです。オーダーとしてはダイクストラのO(nlogn)がボトルネックなのでそれになります。
そして提出してみるとACでした。やったぜ。
解答
どうやらO(n)で解ける方法があるらしい。
グラフが木であることに注目すると点1から点nへのルートは一通りであり、そのルートを支配していくのがお互い最良の戦術になる、ということです。
これは僕の考えた「相手の行けるところを潰す」とも合致していて、要するに相手に近づいていけばいいわけなので確かにそうだと言う感じです。
木の特徴をもっとしっかり抑えて注目するべきでした。
