【祝】AtCoderでレーティング1000を達成/やったこと振り返り

どうもーー

さて、タイトルの通りレーティングがようやく1000にのりました！

ABC140
ついにratingが1000に!!
めちゃくちゃ嬉しいんですけどぉ〜!!

Guam行ったら思考力向上したw pic.twitter.com/T1b5Mtg9Zb

— teramex🇲🇽/エンジニア (@mktrdbg) 2019年9月7日

まあ普通の人にとっては大したことではないのかもしれないけど、
自分にとってはなかなかに嬉しいことです！

特に最近は停滞（プラスマイナス5とか）が多かっただけに、
ABC139とABC140で自分なりの好成績が出せたのがより嬉しい！

ということで感想を書きつつ、一応どんなことをやってきたのかを書いときます。
成田エクスプレス内でコーディングし、渋谷駅で仕上げ＆提出したのでコードのひどさはご愛嬌ということで。
一発ACじゃなかったら恐ろしいことになってた。ローリスクハイリターン。
しかしリスクを取らずに何が面白い。

ABC140
A: N**3。焦っていたので(N-1)**3を一回試した。
B: なにげにむずい。どれがどれか把握
C: Maximal Value

A = [None] * N
while any(a == None for a in A):
    min_idx = B.index(min(B))
    if A[min_idx] is None:
        A[min_idx] = B[min_idx]
    if A[min_idx+1] is None:
        A[min_idx+1] = B[min_idx]
    B[min_idx] = inf
print(sum(A))

まずAを[None, None, ... None]と長さNの配列に。
Bの各要素は、Ai, Ai+1の大きい方となる。
Bの中でも小さい値から見ていき、Aの各要素を確定させていくことですべてのAの要素を確定することができる。

6
0 153 10 10 23

なら
0のところに対応するAの要素は絶対に0になるので確定する
この時点で
[0, 0, None, None, None, None]
次に小さい10の部分のAを確定させると
[0, 0, 10, 10, None, None]
もう1つの10も確定させて
[0, 0, 10, 10, 10, None]
23の部分を確定させて
[0, 0, 10, 10, 10, 23]
となり、合計53となる

D: Face Produces Unhappiness
顔面が不幸を生み出す

tmp = 1
l = []
for i in range(N-1):
    if S[i] == S[i+1]:
        if i == N - 2:
            tmp += 1
            l.append(tmp)
        else:
            tmp += 1
    else:
        if i == N - 2:
            l.append(tmp)
            l.append(1)
        else:
            l.append(tmp)
            tmp = 1

len_l = len(l)
len_l -= 2 * K
if len_l <= 1:
    print(N - 1)
elif len_l <= 2:
    print(N - 2)
else:
    ans = N - len_l
    print(ans)

前半の部分で、塊の長さをリストに入れます。
例えば
RLRRLRLL
なら、つながっている部分をカウントして
1, 1, 2, 1, 1, 2
というようなリストを作ります

この時点で、全体の幸福数は
2のところの1人と、もう1つのところの2のところの1人のあわせて2人です。

K回できる操作をしていくと、どこを回転させても
4, 1, 1, 2なら3+1=4
1, 4, 1, 2なら3+1=4
1, 1, 2, 4なら1+3=4
と、端だけ回転させる以外のどんな操作をしても幸福人数は同じになります。
結果、
N-1が最高点(LLLの場合は2になる)ということを考えると
(N-1) - 塊の数
が求める答えということが言えます。
RLRなど1のところは、幸福数が0です。

塊の数を数えると
最初
1, 1, 2, 1, 1, 2
で6個でした
次に
4, 1, 1, 2
で4つに
さらに
6, 2
で2つになりました。

一回の操作で、塊を2つ減らすことができます。
ということは、幸福数が2増えますね。
こうすると、K回操作して塊が1つになるならN-1
塊が2つになるならN-2
塊がi個になるならN-1 - i
といえます。
最終的な塊の数は
最初の塊の数 - 2*K
で求められるので、答えが出せるのではないでしょうか。

説明が鬼下手。

疲れたので終わらせに行きます。

今までにしたこと

atcoder problemsでC埋め
最近のDであれば前のよりは簡単なのでちょっと手を出したり

A, Bは本当に初めたばかりの時以外はやっても時間の無駄かと思い手をつけておりません。
とりあえず緑安定させたかったので、Cを重点的に。
水色になりたいのですが、Dをやらないと厳しそう
Cを全埋めする合理性はあまりなさそうですが、意地があるので一旦埋めてからDをもう少し手をつけようかと思っております。

疲れたので終わります。