AtCoder140 コンテスト中に考えた事＠灰色目線

ABC140の時の考察まとめ

なんでこう解いたのか？っていう知識が風化するのでなるべく備忘録していく。

TL;TD

入力例見て、累乗っぽいなーでコード書いたけど最初N^Nにして間違った。

その後、N^3に修正して提出してAC。（実装はMath.pow())

解説見たら、N * N * Nしてたけどint値に丸める必要ないからこっちのが素直ですね。

最初問題文の追加で食べたCiの意味が理解できず、iが1じゃない場合に加算するのだと勘違い。

Ai→Ai+1の差が１だった場合のみ、そのAiのインデックスをCから取得した値がボーナスとして入る。という条件だと理解。

分かりづらいので例１を元に図解。

例１）

後から解説見るとBNは必ず全部食べるっぽいので、SUM（BN）で、条件に合うCだけ抽出すればOKだった模様。

Bi≥max(Ai,Ai+1)

という部分を割と無視して、直観。

配列の長さが、A+1 = BなのでAの末端は自動的に決まりそう。だと仮定。

A[0]==B[0]

A[N]==B[N-1]

それ以外の要素はBの後ろからMath.min(Bi, Bi+1)で解く。

（前から解いても良さそうだし、普通にMath.maxで解いても良さそう？）

正直問題文の意図が理解できなかったので、コンテスト中の提出は見送りました。

解説PDF読んでもいまいちピンとこなくて、youtube解説見てやっと理解しました。

まとめ

一番左の人（０番目要素）は確実に不幸せ→つまり、最大値は文字列長-1

RRとかLLといった幸せな部分を数える→ここは変える必要がない。

１回の操作で必ず２人が幸せになる。→K回まで変更できる→2Kの人が幸せになる。

となると、まず文字列の幸せ数を抽出してカウント。

そこから2Kを加算した値が出力候補１。

LLLLLLやRRRRRRなど、既に全員が幸せであることを考慮してN-1が候補２。

Math.max(候補１、候補２)とすることで、答えを導き出せそう。

B問題のA列の全要素に対して使うと、インデックス操作でいちいち-1しなくて済む。

rep(i,n-1) a[i]--;

Javaだとこう書ける。

for(int i=0; i<a.length; i++){
    a[i]--;
}

D問題でRRRRLLLLなどの文字列を、RLといった塊にする圧縮方法。

今回のD問題では、操作時にこの塊内の幸福度は変更されない。という性質を使う。