AGC024(AtCoder Grand Contest 024) - lab2Gがプログラミングするブログ

　今日はAtCoder Grand Contest 024の日でしたね(もう24時回ってる) お疲れ様でした　今回の私ですが、なんと…

AGC024
3完！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ pic.twitter.com/rBr8quU8CN
— lab2G (@lab_2_g) 2018年5月20日

天　啓

3完でした！ABCは3完まで、ARCは1完までが限界だった自分とは思えない怒涛のプレイングを発揮できました！クッソ嬉しい〜〜〜〜〜
後から聞いた所C問題はかなり逆詐称だったとか、やっぱりかｗといった所ですが、嬉しいことには変わりないですね　今回みたいな神が降りる回が今後続くといいなぁ…(もっとも、神が降りなくても解けるのが一番なのですが)

　「続きを読む」から今回解けた問題についてお話します

コンテストページ

https://beta.atcoder.jp/contests/agc024

解けた問題

A：Fairness

B：Backfront

C：Sequence Growing Easy

すごくどうでもいいんですけど、音楽ゲームの楽曲名みたいですよね　上からレベル17,17,18…？(SDVX)

各問題について

A：Fairness

別の2人から数値を貰いあい、ドンドン足して増えていく…そしてA-Bを求めるという非常に面倒臭そうな問題ですが、なんとこの問題「数を増やしてもAとBの差の絶対値が変わらない」という大穴が潜んでいたんですね
それがわかると数行で書けます　今回この問題についてあまり言及せず、皆実装が同じになると思われるので、コンテストの解説をご覧ください(一応解説メモは作ったので要望あれば貼ります)

B：Backfront

自由に選べる要素を先頭か末尾に投げて、最小回数で昇順並び替えを行うという問題です
この問題は「＋1間隔で連続する最長の部分列」を見つけ出して、Nからその部分列の長さを引くと最小回数が導出できるというものでした　中々見つかならなそうで、わかっても実装が浮かびにくい！問題に思えます(自分は4231(例の逆)等のケースを浮かべたりして見つけました)

C：Sequence Growing Easy

要素を選び、それに＋1をしたものを次の要素に"置き換える"という配列パズルのような問題
ミソな所は「加算」ではなく「置き換え」な所ですかね(？)初見ここ誤解して逆順とか考えようとしました💧
定石をあぶり出して場合分けしていきます　先の値の決定に前の値の状態が鍵となってくるので、先頭と次の値を比較した結果から回数を順々に出していく感じになりますが「どの塊から置き換えを行うか」を考えねばなりません　その塊の優先度が前から順に辿って判別できるとグンと答えに近づきます

方針

B：Backfront

連続部分列リストをイメージする　がしかし、リストで持っていると判定が何となく狂うので楽に実現したい　そこで

連続部分列の末尾をkey、長さをvalueとした辞書Lを作り、判定が真なら要素に対応するkey名および長さを更新、偽なら新規に辞書登録させる

最後に、Nから辞書内最大のvalueを引く

入力例３[6,3,1,2,7,4,8,5]に対して、連続部分列および辞書の中身は

連続部分列	L.key	L.value
[6,7,8]	8	3
[1,2]	2	2
[3,4,5]	5	3

となります　はじめにkeyがそれぞれ6,3,1となり、1→2、6→7、3→4…と先頭から更新を繰り返す形となります

C：Sequence Growing Easy

まず、どう頑張っても作れない「書いてある数字が現在のindex未満」の値が書いてあったら無理判定する(これいらなかった気がする)
以下に従い場合分けを行う(リストLは入力配列)　L[i+1]がL[i]と比べて…
- 小さい・同じ値であるとき：まずL[i+1]から作る必要があるので、L[i+1]回ぶん回数を増やす
- ＋1だけ大きいとき：L[i]から生成可能な値であるので、1回増やす
- ＋2以上大きいとき：作れません　無理判定する

＋2以上大きいときもL[i+1]から作ればいいじゃない！と思われますが、作れません(ここで1回WAしました) なぜならこのパズル、小さい値を大きい値に上書きすることは出来ますが、大きい値を小さい値に上書きすることはできないからです
まず数を飛ばして生成することは不可能なので、当然大きい値を作るには小さい値より長くスペースを使用するわけですが、なんとここから小さい値を作ろうとすると作り始めの部分に既に大きい値が邪魔しています ゆえに上書きできないといえます
例）01224
01234をまず作り次に3の部分を2に変えようとする時、手前が1でなければならない所が2なため変えられません　更に遡り2の部分を1に変えようと試みても、その手前は1であるため結局変えられません　これの繰り返しで「作れない」という結論に至ります

ソースコード

B：Backfront

N = int(input())

L = {}
for i in range(N):
    n = int(input())
    if n-1 in L:
        L[n] = L.pop(n-1)
        L[n] += 1
    else:
        L[n] = 1
    
ans = N
for k,v in L.items():
    if N-v < ans:
        ans = N-v
        
print(ans)

C：Sequence Growing Easy

N = int(input())

ans = 0

L = []
isok = True
for i in range(N):
    n = int(input())
    if n>i: isok = False
    L.append(n)

for i in range(N-1):
    if L[i+1] <= L[i]:
        ans += L[i+1]
    elif L[i+1] == L[i]+1:
        ans += 1
    elif L[i+1] > L[i]:
        isok=False
        break
    
if isok:
    print(ans)
else:
    print(-1)

感想

「AGCか〜〜〜今日こそは2完したいが、無理やろなあ」と思ってた所、想定外に良い結果が得られて感激でした　この一言に尽きます
B問題で2回WAしてるのが痛いところだったかもしれないと反省していますが、このWAそもそも全く見当違いの方向から求めようとしていまして、「最高値を設定して先頭から値を見ていき、最高値より高ければ更新、低ければその値を最小回数とする」みたいな解法を書いたらWAしたんですね　逆もせなアカンな！とか言って逆からも同じ動作を行ったのですがこれで2回目のWA　入力に4231を与えておかしいことが判明し、正しい解法に辿り着けた所存です
今回の成功はB問題を時間に余裕をもってACできたのが大きかったかもしれませんね

これから2週間、研究室の論文輪講に向けて準備をしなければならないので、のこのこと競プロしている場合では無くなるかもしれません　内職が無いショック(激寒)
論文輪講以外にも期末レポート等が入ってくる予感がするので、かなり恐ろしい月末を迎えそうです　この月末終わって欲しいですが、頑張ります…

それではまた