ARC28とSRM631
* ARC28 ○---
詳しくは以下。
AtCoder Regular Contest 028 解説
- A:
シミュレーション
- B:
priority_queue、pairの使い方が参考になる。
- C:
木構造。制約から、循環はしないことが保証されてる。（あるノードは自分より小さいものにしかエッジを張らない）
木をたどっていくdfsの書き方とか参考になる。
Submission #223649 - AtCoder Regular Contest 028 | AtCoder
- D:
よくわかってない。
*SRM631 Div2 ○--
- A:
N×Nの文字列が与えられて、WかBで埋まってる。列を見て、同じ文字が連続している数を数えて、もっとも長く連続している数を答える。
境界とか気をつけて数えるだけ。
- B:
時間tが経過した後、１つの場所にせいぜい1匹までしか猫がいられない。猫は初期場所とその場所に何匹いるかと時間が与えられて、各猫は時間ごとに左右1マスどちらかに動くか、その場にとどまるか選択できる。
どうやって1匹のみという状態があるのかを調べるかわからなかった。
→範囲小さいし、全探索ぽい。
→どう全探索する？
解法：
全探索ではなくて、貪欲。
<s>Impossibleなパターンが限られるぽい。</s>
>|cpp|
vector<pair<long long, long long>> p;
||<
とかにpositionとcountを入れて、猫のポジションを小さい順に並べる。
左から詰めて並べるようなイメージ。可能な限り左から並べる（直前の猫が並んでるところの右端か、いま見てるポジションで猫が最大限左まで行ける場所のうち、より右にあるほうから並べる）。かぶり発生したら、Impossible。最後までImpossibleにならなければ、Possible。
- C:
2^Kの価値のコインを２枚ずつ所持してて、それを用いてNを表す方法のパターン数を答える。
解いていない。
暇な時に確認する。
