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

ABC140の時の考察まとめ

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

AtCoder Beginner Contest 140

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値に丸める必要ないからこっちのが素直ですね。

提出 #7380924

B-Buffet

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

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

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

例1)

3
3 1 2
2 5 4
3 6

1回目:A1の3番目の料理を食べるとB3の満足度4を得る。 A2の値が1なので、ボーナスなし。

2回目:A2の1番目の料理を食べるとB1の満足度2を得る。 A3の値が2なので、ボーナス発生。 C1の満足度3を得る。

3回目:A3の2番目の料理を食べるとB2の満足度5を得る。 A4の値は存在しないので、ボーナスなし。

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

提出 #7391660

C-Maximal Value

Bimax(Ai,Ai+1)

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

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

A[0]==B[0]

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

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

(前から解いても良さそうだし、普通にMath.maxで解いても良さそう?)

5と2の場合、最小値としてとれるのは2のみ

提出 #7394560

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)とすることで、答えを導き出せそう。

提出 #7429556

使用するテクニック

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とか)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする