ABC160:水色競プロerのムーブ備忘録(コンテスト中の考察の流れ)
久々の備忘録です。
コンテストには参加していましたが、ブログを更新する時間がなかなかとれませんでした。
せっかく参加したコンテストの考察は残しておきたいのですが・・
日立コンで初の黄パフォ出してHighest更新したり、その後のパナソニックコンで茶パフォ出してレートを大きく削られたりで
結局ABC160開始前のレートは1300
〇コンテスト名：ABC160
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
いつも通りのABC
〇コンテスト開始時のsyunsukeのレート 1300
〇今回の方針
いつも通り。
基本前から順番に解く。
詰まったら順位表を確認して、解きやすそうな問題から解く。
コンテスト開始！
A - Coffee
長さ6の文字列が与えられる。
3番目と4番目、5番目と6番目が同じ文字ならYes、そうでなければNoを出力せよ。
0-indexを知っているかを問う問題でしょうね。
文字列のまま入力を受け取っても良いし、Listで受け取っても良いでしょう。
Listで受け取っていたようです。
pythonは文字列もListも0-indexなので(というか1-indexの言語ってあるんでしょうか？)、
下記のコードを出しました。
S=list(input()) if S[2]==S[3] and S[4]==S[5]: print("Yes") else: print("No")
1:22 AC
B - Golden Coins
500円玉は1000点、5円玉は5点とする。
X円の点数を最大にせよ。
ただそれだけの問題ですが、問題文の理解に時間を食われました。
問題文中の「金色の硬貨」に引っかかってしまい、500円玉が金色なら、他の硬貨は金色ではないか？大丈夫か？
となりました。
入力例を見れて確認し、
500円玉は2点/円
5円玉は1点/円
なので、可能な限り500円玉を集めて、残りは5円玉にすれば良いですね。
N=int(input()) A=N//500 N%=500 B=N//5 print(A*1000+B*5)
3:52 AC
C - Traveling Salesman around Lake
円周上のAiメートルの点に家がある。
隣の家との距離の最長距離を求めよ。
と読み替えられますね。
この手の問題は、各家の位置Aをリストで受けて、一番小さい値に、円周1週分の長さを足した値をリストの最後に加えれば、処理が簡単になりますね。
K,N=map(int,input().split()) A=list(map(int,input().split())) A.append(K+A[0]) MAX=0 for i in range(len(A)): if MAX<A[i]-A[i-1]: MAX=A[i]-A[i-1] print(K-MAX)
6:47 AC
D - Line++
N頂点で、1と2,2と3の様に、隣接する頂点を距離1で双方向につないだグラフがあり、頂点Xと頂点Yの間も距離1でつながっている
各距離の組み合わせがいくつあるか？
これは、基準点を定めてもらえばただの最短経路問題。ダイクストラで1発でしょう。計算量Nlog(N)で解けますね。
ただ、全ての点から開始するのなら、点の数がNなので(N^2)log(N)。
これでは間に合いません。計算量をいかに落とすかがこの問題の肝でしょう。
しばらく考えるも、計算量を落とすアイデアは降りてきません。
問題文を見て、どこまで計算量を落とせば良いか考えます。
・・・
あれ？N<=2000？
これなら(N^2)log(N)でも通るのでは？pythonでは厳しいかもしれませんが、おそらくこれが想定解でしょう。
python でコードを書いて、TLEしたら高速化を考えましょう。
・・通りますね。
これは実力者でもNの制約に気づかなかった方？が結構苦戦したようです。
N,X,Y=map(int,input().split()) ans=[0 for i in range(N+1)] L=[[]for i in range(N+1)] for i in range(2,N+1): L[i].append(i-1) L[i-1].append(i) L[X].append(Y) L[Y].append(X) import heapq for i in range(1,N+1): C=[10**5 for i in range(N+1)] C[i]=0 Q=[] for a in L[i]: Q.append((1,a)) heapq.heapify(Q) for b in range(10**4): if len(Q)==0: break d,p=Q[0] heapq.heappop(Q) if C[p]==10**5: C[p]=d ans[d]+=1 for c in L[p]: if C[c]==10**5: heapq.heappush(Q,(d+1,c)) for i in range(1,N): print(ans[i]//2)
28:04 AC
制約を確認するまでの考察がもったいなかった。
E - Red and Green Apples
X個の赤リンゴとY個の緑リンゴを食べる。
赤リンゴはA個あり、それぞれおいしさはAi
緑リンゴはB個あり、同様においしさはBi
無色リンゴはC個あり、おいしさはCiで赤にも緑にもなる。
食べるリンゴのおいしさの最大値を求めよ。
この手のよくわからない問題はまずこの流れで考えます。
・無色リンゴをソートしておいて、どこまで使うかを2分探索！
無理
・よくわからないけどなんかDP！
よくわかりません
・グラフに落とし込む！
意味がある気がしない
！！！
これって、heapを使って、
赤リンゴのheap、緑リンゴのheap、無色リンゴは逆順でソート
赤リンゴか、緑リンゴの最小値よりも無色リンゴのほうがおいしければ入れ替え。
これをくりかえせば良いですね。
import heapq X,Y,a,b,c=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) C=list(map(int,input().split())) heapq.heapify(A) if len(A)<X: while len(A)<X: heapq.heappush(A,0) else: while len(A)>X: heapq.heappop(A) heapq.heapify(B) if len(B)<X: while len(B)<Y: heapq.heappush(B,0) else: while len(B)>Y: heapq.heappop(B) #print(A,len(A)) C.sort(reverse=True) for i in range(c): if A[0]<B[0] and A[0]<C[i]: heapq.heappop(A) heapq.heappush(A,C[i]) elif B[0]<=A[0] and B[0]<C[i]: heapq.heappop(B) heapq.heappush(B,C[i]) else: break A=list(A) B=list(B) print(sum(A)+sum(B)) #print(B,len(B))
45:15 AC
いやこれよく考えたらheapもいらなくないですか？
しかし、50分以上残してる。これはいけるのでは！！
F - Distributing Integers
・・こんなん無理です。
気分を変えるためにお茶を入れたり、手洗いうがいをしたり・・・
それでも何も降りてきません。
そのまま時間切れ。
結局
45:15 5完 0WA 767位でパフォ1658 レートは+41で1341
今年度はレート1234からスタートしたので、レート+107
40過ぎのおっさんが、若い人たちの実力インフレに巻き込まれながらもレートが上がっているなら上出来？
プログラミング2年目の人の年間レート増が+107では、伸びが停滞していてヤバイ？
悩ましい結果ですが、今年度のコンンテストは終了。
対戦ありがとうございました。
