ABC140の時の考察まとめ
なんでこう解いたのか?っていう知識が風化するのでなるべく備忘録していく。
目次
TL;TD
- A:N^3 または N * N * N
- B:ボーナスポイント処理を、ループ内の条件分岐で書いて全探索
- C:B[0]とB[N-2]は固定で取得して、それ以外はBの終端から最小値を取る全探索
- D:コンテスト中は未提出。問題文見て不用意に回答出してWA貰いたくなかった。
- E:問題見て数式が理解できなくてそっ閉じ
- F:入力例4を見てそっ閉じ
A-Password
入力例見て、累乗っぽいなーでコード書いたけど最初N^Nにして間違った。
その後、N^3に修正して提出してAC。(実装はMath.pow())
解説見たら、N * N * Nしてたけどint値に丸める必要ないからこっちのが素直ですね。
B-Buffet
最初問題文の追加で食べたCiの意味が理解できず、iが1じゃない場合に加算するのだと勘違い。
Ai→Ai+1の差が1だった場合のみ、そのAiのインデックスをCから取得した値がボーナスとして入る。という条件だと理解。
分かりづらいので例1を元に図解。
例1)
3 3 1 2 2 5 4 3 6
後から解説見るとBNは必ず全部食べるっぽいので、SUM(BN)で、条件に合うCだけ抽出すればOKだった模様。
C-Maximal Value
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で解いても良さそう?)
D-Face Produces Unhappiness
正直問題文の意図が理解できなかったので、コンテスト中の提出は見送りました。
解説PDF読んでもいまいちピンとこなくて、youtube解説見てやっと理解しました。
まとめ
一番左の人(0番目要素)は確実に不幸せ→つまり、最大値は文字列長-1
RRとかLLといった幸せな部分を数える→ここは変える必要がない。
1回の操作で必ず2人が幸せになる。→K回まで変更できる→2Kの人が幸せになる。
となると、まず文字列の幸せ数を抽出してカウント。
そこから2Kを加算した値が出力候補1。
LLLLLLやRRRRRRなど、既に全員が幸せであることを考慮してN-1が候補2。
Math.max(候補1、候補2)とすることで、答えを導き出せそう。
使用するテクニック
0-indexed
B問題のA列の全要素に対して使うと、インデックス操作でいちいち-1しなくて済む。
rep(i,n-1) a[i]--;
Javaだとこう書ける。
for(int i=0; i<a.length; i++){ a[i]--; }
ランレングス圧縮
D問題でRRRRLLLLなどの文字列を、RLといった塊にする圧縮方法。
今回のD問題では、操作時にこの塊内の幸福度は変更されない。という性質を使う。
アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)