キーエンス2020:水色競プロerのムーブ備忘録(Dの考察の流れが良かった)
〇コンテスト名：キーエンスコンテスト2020
〇配点 A:100 B:200 C:400 D:700 E:900 F:1100
〇制限時間 120分
いわゆるARC級というやつですね。
〇コンテスト開始時のsyunsukeのレート 1266
〇今回の方針
配点的に恐らく緑、水、青によるC早解き競争。
1WA覚悟で速さ優先。チェックは甘めでサブミット！
コンテスト開始！
A:縦(H)横(W)のどちらかを足す。N以上になるまで繰り返す。最短で何回必要か？
合計をSUM=0 としておいて、HとWの大きい方を足し、足されたなかった方は1を引き・・
引く必要はなさそうですね。
最初にHとWのどちらが大きいかを判定し、大きい方を足し続けて何回でN以上になるか？
なので、NをHとWの大きい方で割り、答えを切り上げれば良いですね。
pythonで切り上げを行うなら、mathの中にあるceilを使うと良いです。
import math H=int(input()) W=int(input()) N=int(input()) print(math.ceil(N/(max(H,W))))
全部のチェックは行わず、速さ優先で提出
2:40 AC
B:N個のロボットが直線状に並んでいる。ロボットはXi-LiからXi+Liの範囲で動く。ぶつからないように並べられるのは最大何個か？
[Xi-Li,Xi+Li]をリストで持っておいて、ソートして・・
いやいや200点問題でそれはない。
もう一度問題文をよく読んで・・
でもやっぱり[Xi-Li,Xi+Li]をリストで持っておいて、ソートして・・
いやいや200点問題でそれはヤバい。
だんだん焦ってきた。想定解じゃないかもしれないけどこの方針で一旦提出。
位置をDとして、D=-10**9で初期化
[[Xi+Li,Xi-Li]をリストに入れて、ソート
Xi-LiがD以上なら使用できる。DをXi+Liに更新。
そうでなければぶつかるから使用しない。
N=int(input()) L=[] for i in range(N): a,b=map(int,input().split()) L.append([a+b,a-b]) L.sort() ans=0 X=-10**9 for i in range(N): if L[i][1]>=X: ans+=1 X=L[i][0] print(ans)
一応テストケースでチェックして提出
11: 33AC ヤバイかなり時間をロスした。
C:N個の整数Aiを持つリストで連続するAiの和がSになるものがK個になるものを作れ。
あれ？KがN以下なら、SをK個並べて、あとは1にでもしとけば良くない？
いや、Sが1の時に死ぬ。Sが1の時は残りを2にしておけばOK？
テストケースで確認して提出
WA!
・・そんな単純なわけないですよね。
でも、なにが悪いか分からない。
今回のコンテストはこの問題の早解き勝負なのに・・ 焦るばかりで頭が回りません。
！！！
1がたくさんならんでいたら、どこかで合計Sになるケースが出てくる！
S!=10**9なら、SをK個並べて残りは10**9で埋める。
S==10**9なら、10**9をK個並べて、残りは10**9-1で埋める。
N,K,S=map(int,input().split()) if S!=10**9: ANS=[10**9 for i in range(N)] for i in range(K): ANS[i]=S else: ANS=[10**9-1 for i in range(N)] for i in range(K): ANS[i]=S print(*ANS)
上のコードは、初めに10**9もしくは10**9-1をN個並べておいて、あとでK個だけSに書き換える方針です。
22:54AC 1WA
恐る恐る順位表を見ると・・ 480番台！ 1WAのペナルティを考えても700番台で終われそう？
って油断してやらかしたのが前回。
今回は時間いっぱいD問題にかじりつきましょう。
D:N枚のカードがあり、表と裏にそれぞれAiとBiが書かれている。隣のカードと入れ替えて良いので右のカードは左のカードと同じかそれ以上になるように並べる(広義単調増加)ことができるか？できるならその最小入れ替え回数を示せ。
考察開始。
まず、偶数番目のカードは、偶数番目にもってくるとAiが上、奇数番目にもってくればBiが上になる。奇数番目のカードはその逆。
偶数ででてくる数字と最初の番号をいれたヒープEVE、奇数で・・ヒープODD、すでに出た番号を管理するリストCを用意すれば、並べられるかどうかは判定できそう？
でもその時の入れ替え回数はどうする？
制約をもう一度確認
N<=18
簡単に入れ替え回数を把握する方法は無いから、何らかの全探索をしなさいってことですね。
だったら・・・
・0インデックスで考えて、0は偶数なので偶数位置のカードの数>=奇数位置のカードの数になる。
・奇数位置のカードの内、x枚を偶数位置で使用する。偶数位置のカードもx枚奇数位置で使用する。
・x枚ずつの変更を終えた後、奇数位置は[数字,最初のカード位置]でリストを作りソート。偶数も同様に
・奇数位置のカードからx枚を選ぶ組み合わせを全数探索。偶数位置も同様に。
・そして、偶数リスト、奇数リストの順で小さい方から並べる。
・全探索！広義単調増加が可能か？可能なら最初の位置と実際の位置の差を取る(実際の位置が最初の位置より前なら、その差を足す！)
これでいけるのでは？
祈りながらテストケースを試すと？
通る！！
勝利を確信して提出！！！
ジャッジ開始とほぼ同時にWA!
方針はどこも間違ってないはずだが？
凶悪なコーナーケース？
問題文を読み直してもそんなものは無い。
・・・
ところで、最初の位置と実際の位置の差で本当に移動回数になる？そういえば、なんか転倒数って言葉なかった？念のため調べてみたらそれっぽい！コードを探してペタリ。
でも、転倒数を調べて、現在の最小値と転倒数の大きさを判定し、転倒数のほうが小さければ最小値を更新。の方針にすると、毎回最小値を０に更新してくれる。何で？
転倒数を変数tcntに入れて出力すれば・・ちゃんとでてくる。
だったら、tcntと現在の最小値を比較して・・
テストケースは通る。
もうよくわからないし時間もないので、提出。
あれ？ジャッジが進んでる？？
AC！
今思えば、転倒数が毎回0になるのは、転倒数を数えた際に、リストを並べ替えていたんでしょうね。なので、転倒数と現在の最小値を比べた際は正しい転倒数。そして、最小値を転倒数に更新する際は、転倒数は0になっていたんでしょう。
110:09AC 1WA+Cの1WA
残り10分弱ではもうE,Fは解けません。E,Fは開くことなくコンテスト終了
結局110:09 4完2ペナ
パフォ1846,レート+73で1339になりました。
パフォもレートもHighest更新
自己ベストが出たことはもちろん良かったのですが、今回は考察の流れが良かったです。
・Dで奇数と偶数に分けて考えられたこと。
・制約を見て、何らかの全探索であることに気づけたこと。
・転倒数は偶然ですが、コンテスト中は蟻本の目次をすぐに開けるようにしておけば、何かアルゴリズムが必要そう？ってなった時に役立つかもしれません。
今日のコンテストからはそうしましょう。
提出したDのコードはこれです。随分無駄の多いコードですが。
N=int(input()) A=list(map(int,input().split())) B=list(map(int,input().split())) o=N//2 e=N-o import itertools E=[] O=[] for i in range(N): if i%2==0: E.append(i) else: O.append(i) ANS=10000 def mergecount(Z): cnt1 = 0 z = len(Z) if z>1: A1 = Z[:z>>1] A2 = Z[z>>1:] cnt1 += mergecount(A1) cnt1 += mergecount(A2) i1=0 i2=0 for i in range(z): if i2 == len(A2): Z[i] = A1[i1] i1 += 1 elif i1 == len(A1): Z[i] = A2[i2] i2 += 1 elif A1[i1] <= A2[i2]: Z[i] = A1[i1] i1 += 1 else: Z[i] = A2[i2] i2 += 1 cnt1 += z//2 - i1 return cnt1 for i in range(o+1): X=list(itertools.combinations(E,i)) Y=list(itertools.combinations(O,i)) for j in range(len(X)): for k in range(len(Y)): ev=[] od=[] for n in range(N): if n%2==0: if n in X[j]: od.append([B[n],n]) else: ev.append([A[n],n]) else: if n in Y[k]: ev.append([B[n],n]) else: od.append([A[n],n]) ev.sort() od.sort() #print(ev,od) Z=[] Num=0 F=0 for x in range(N): if x%2==0: if Num>ev[x//2][0]: F=1 break else: Num=ev[x//2][0] Z.append(ev[x//2][1]) else: if Num>od[x//2][0]: F=1 break else: Num=od[x//2][0] Z.append(od[x//2][1]) if F==0: #print(Z) tcnt=mergecount(Z) if F==0 and tcnt<ANS: ANS=tcnt if ANS==10000: print(-1) else: print(ANS)
