naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 103

7/21 21:00-22:40
起きてたので出ました

D - Islands War (400)

最初いもすして山を描いたりとか、UnionFindで島に分けるとか考えたけど
そうじゃなくて
「可能な限りまとめて切る」
「できるだけ並行している場所で切る」?
あ、左から見て行って、もう重なる区間が来なくなるまで束ねて、切らなくちゃいけないギリギリまでこらえてからばっさり行く感じか
区間を始点でソートして昇順に
priority_queueに終点を入れて行って(但しpqは小さい順に出てくるようにする)
次の区間の始点がpq.topより後なら1カット&pqの中身を処分
そして次の区間の終点をpqに投入
最後pqが空でなければもう1回カットして終了
→AC
https://beta.atcoder.jp/contests/abc103/submissions/2880263

解説

何言ってるか分からない(右から見てる?)

C - Modulo Summation (300)

m=全部の積-1、にすればこれ以上大きくなりようのない \sum a_i-1 が得られるよね
互いに素でないケースでそういう値が取れないケースとか…少し考えたけど…ないよね
a_iも2以上だし、変なコーナーケースもなさそう
(mは求める必要なし。long long使ったけど、3\cdot10^3\cdot(10^5-1)\lt3\cdot10^8なのでintで足りる)
→AC
https://beta.atcoder.jp/contests/abc103/submissions/2881263

解説

自分の解法と同様

B - String Rotation (200)

pythonで書いた(if S in T+T: みたいに書きたかったから)
Sの前半が1つ目のTに,後半が2つ目のTにマッチするなら、マッチした部分を入れ替えてくっつけたらTになる、ということはSをローテートしたものがTに等しい、ということで。(vice versa
→AC
https://beta.atcoder.jp/contests/abc103/submissions/2881478

解説

|S|回操作

A - Task Scheduling Problem (100)

最初pythonで書こうと思ったけど
ああーこういうの考えるの面倒くさい
next_permutation砲で総当たりだー
→AC
https://beta.atcoder.jp/contests/abc103/submissions/2881831

解説

max() - min()

タスクを完了する順序を全通り調べて最小値を求める方法でも解けますが、実装が若干大変です。

あ、はい