非IT系のアルゴ専門Python競プロerがAHC008のテスターを動かすまで
AHC008でAHCに初参戦しました。
約2年ぶりの記事なのでスペックを書くと
〇40過ぎの非IT職の子持ちのおっさん
〇競プロ経験あり(アルゴのみで、使用言語はPythonだが引退気味。一応青コーダー。)
〇Kaggleにはときどき参戦
です。
何だかIT系の方はMacを使う方も多いようですが、
私は持ち運びの利便性を重視した、軽くて小さめのWindowsPCを使用しています。
また、エディタは何度かVSCodeに挑戦しましたが、結局paiza.ioに戻りました。
KaggleをするときにはGoogleColab上でJupyterNotebookを使いますが、競プロはpaiza.ioです。
こんな背景でAHC008に参戦しました。
コンテスト開始！
・まずは公開されているローカルテスタをダウンロード
よくわかりませんが、Windows用のコンパイル済みバイナリをダウンロード。
眺めていたらダウンロードファイルが更新されたので、更新済ファイルをダウンロード。
⇒これは問題なくできました。
・readmeを読んで、使い方を理解。
windowsの場合の操作もPythonn用の例もあってこれなら余裕のはず。
python3 で main.py というプログラムを実行する場合
cargo run --release --bin tester python3 main.py
Windows用のコンパイル済バイナリを使用する場合は
cargo run --release --bin tester の部分を ./tester.exe に置き換えて下さい。
⇒①書いてはいませんが、コマンドプロンプト上で動かすんですよね？
また、私は test01.py ファイルを作ったので
コマンドプロンプト上で
./tester.exe python3 test01.py
はい動きません。
②冗談です。
READMEの上部に
「このREADMEが置かれているディレクトリに移動して作業することを想定しています。」
と書いてあります。
ダウンロードファイルはデスクトップに展開したので、
コマンドプロンプト上でcd操作を繰り返して、dirでREADMEのあるディレクトリであることを確認して、
./tester.exe python3 test01.py
はい動きません。
③そういえば、python動かすときって、python3の部分をpythonにしたら動くことってありますよね？
./tester.exe python test01.py
はい動きません。
④どうしましょう？コンテスト中なので、うかつにTwitterでヘルプを出せば、
答えてくれた方に迷惑がかかるかもしれません。
この時点ではまだ2月12日(開始日)
⑤そういえば、このPCってPythonのパス通ってる？
paiza.ioやGoogleCloabでpythonを使えることと、
このPCにPythonがインストールされていることは違いますよね。
PythonそのものはAnacondaを何度かインストールしてそのままのはずですが。
その辺が怪しい気がしてきました。
Pythonのパスはもうよくわからないのですが、Anacondaが入っていたので、
コマンドプロンプトではなくAnaconda Pronptを立ち上げて、
(これならパスを考えなくてもPythonを起動できます)
ディレクトリを動かして、
./tester.exe python test01.py
「指定されたファイルがありません」
はい動きません。
⑥もしかして、in.txtの部分って inフォルダに入ってた 0000.txt とかにしないとダメ？
./tester.exe python test01.py <0000.txt> out.txt
「指定されたファイルがありません」
はい動きません。
⑦指定されたファイルがありませんって・・よく考えたら0000.txt達はtester.exeと違うフォルダにありますね。
tester.exeと同じフォルダにあるのは0000.txt達が入ったinフォルダ。
0000.txt達をinフォルダから出してtester.txtと同じフォルダに移せば・・
./tester.exe python test01.py <0000.txt> out.txt
はい動きました！！
テスター操作AC！！
この時点で2月24日の夜。
コンテスト終了まで48時間を切っているし、金曜は仕事です。
解法の方針はいくつか思いつきましたが、土曜日だけでは全ての方針は実装できません。
一番簡単そうな方針を実装して、エラーを潰してなんとか点数が出ました。
結果は402位でパフォ1224
もう一日あれば順位を上げられたかもしれませんが、
ひとまず参戦できたし、とても楽しかったのでよしとしましょう。
コンテストを開催いただきました
MC Digital様
AtCoder社様
ありがとうございました。
次回のAHCでは、
・はじめからAnacondaPronptを起動
・ディレクトリとファイルの位置などPCの基礎はよく考える
に気を付けて、本格参戦したいと思います。
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では、伸びが停滞していてヤバイ？
悩ましい結果ですが、今年度のコンンテストは終了。
対戦ありがとうございました。
ABC157:水色競プロerのムーブ備忘録(コンテスト中の考察の流れ)
〇コンテスト名：ABC157
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
いつも通りのABC
〇コンテスト開始時のsyunsukeのレート 1269
〇今回の方針
いつも通り。
基本前から順番に解く。
Cまではテストケースも程々に速度重視で。
(Dが難しく、Cまでのペナで死にたくないので。)
はまったら順位表をチェック。
・今見てる問題を飛ばす？
・何か簡単な解法がある？
の判断材料に
コンテスト開始！
A - Duplex Printing
Nページを両面印刷する。
紙は最小で何枚必要か。
Nが偶数ならN//2、奇数なら(N+1)//2ですね。
それをそのままコードにすれば良いのですが、
コンテスト中は焦っているようです。
わざわざmathをimport して、math.ceilを使っていました。
もちろんそれでも解けるので大きな問題にはならないのですが、
シンプルに解ける問題はシンプルに解きたいところですね。
import math N=int(input()) print(math.ceil(N/2))
0:57 AC
B - Bingo
3x3のマスのビンゴを行う。
N個の数字が選ばれたとき、ビンゴが成立しているか否かを答えよ。
いやこれ普通に難しくないですか？
ビンゴのマスが3x3で9マス
選ばれる数が最大で10なので全探索でも余裕ですね。
入力を受け取るリストLと
はじめに0で初期化してある3x3のリストBを用意して、
リストLの中に選ばれた数字があれば、リストBの該当箇所を1にする。
最後に、縦、横、斜めにビンゴ成立の可否を確認。
L=[] for i in range(3): l=list(map(int,input().split())) L.append(l) #print(L) B=[[0,0,0]for i in range(3)] #print(B) N=int(input()) for i in range(N): n=int(input()) for h in range(3): for w in range(3): if L[h][w]==n: B[h][w]=1 F=0 for h in range(3): cnt=0 for w in range(3): cnt+=B[h][w] if cnt==3: F=1 for w in range(3): cnt=0 for h in range(3): cnt+=B[h][w] if cnt==3: F=1 if B[0][0]+B[1][1]+B[2][2]==3: F=1 if B[2][0]+B[1][1]+B[0][2]==3: F=1 if F==1: print("Yes") else: print("No")
8:23 AC
ABCのB問題史上最長コードを書いたかもしれません。
C - Guess The Number
3桁以内の整数で、1桁目の0は認めない。
各桁の情報が与えられるので、
情報に矛盾がなければ矛盾しない最小値を出力。
矛盾していれば-1を出力せよ。
長さNの空のリストを用意し、
情報通りの位置に情報通りの数字を入れる。
1桁目が0の場合は-1
ただし、すでに数字が入っていた場合、同じ数字ならOK。
違えば-1
最後に、空のリストに対し、1桁目であれば1、そうでなければ0を入れて出力。
これはB問題より簡単なのでは？
はいWA！
問題文を良く読みましょう。
00は認めないけど、0は認めるんですね。
修正してさっさと通しましょう。
またWA！
Nが1の場合、1桁目の0も認められますね。
N,M=map(int,input().split()) L=["" for i in range(N)] #print(L) if N==1 and M==0: print(0) exit() for i in range(M): a,b=map(int,input().split()) if N>=2 and a==1 and b==0: print(-1) exit() if L[a-1]=="": L[a-1]=b else: if L[a-1]==b: continue else: print(-1) exit() for i in range(N): if i==0: if L[i]=="": L[i]=1 else: if L[i]=="": L[i]=0 if N==1: if L[0]==0: print(0) exit() ans=0 for i in range(N): ans+=L[i]*10**(N-1-i) print(ans)
26:16 AC 2WA
注意力のない私にはなかなか難しい問題でした。
D - Friend Suggestions
・・・
・・
・
問題文が複雑すぎて理解できません。
順位表を確認して、DとEのどちらを解くか考えましょう。
・・
Dのほうが解かれています。
3回問題文を読んでも、何をもとめられているのかわかりません。
テストケースから考えましょう。
やっとわかりました！
友人の友人の・・とつながっており、
直接の友人でなく、ブロックしている人でもない人を友人候補と呼ぶ。
各人の友人候補を出力せよ。
友人の友人の・・とつながる人はUnionFindで求められますね。
各人が所属するグループの人数から、直接の友人の人数を引き・・
ブロックの扱いに困りました。
ブロックしている人を1人ずつ数えていては間に合いません。
間に合いません。間に合いません？間に合います。
ブロックは最大2x10**5しかありません。
よって、
①UnionFindにより、友人の友人の・・とつながるグループ内の人数を調べる
②グループ内の人数から、直接の友人数を引く
③ブロックしている人がグループ内にいるか否かを判断し、いればその人数を引く
でこたえが求まります。
ですが、
①pythonで提出してしまいTLE
②pypyに修正するもTLE
③入力の高速化
import sys
input=sys.stdin.readline
を忘れていてTLE
④コードの無駄を解消し、再提出もTLE
⑤UnionFindの「サイズの大きいほうに足す」の部分のコードが抜けており、
非常に効率の悪いUnionFindになっていたことに気づきやっとAC
そもそも、①、②、③、④はしなくてもACできたかもしれません。
import sys sys.setrecursionlimit(1000000) input=sys.stdin.readline N,M,K=map(int,input().split()) P=[i for i in range(N+1)] size=[1 for i in range(N+1)] def find(a): if a==P[a]: return a else: return find(P[a]) def union(b,c): B=find(b) C=find(c) if size[C]>size[B]: P[B]=P[C] size[C]+=size[B] else: P[C]=P[B] size[B]+=size[C] G=[0 for i in range(N+1)] for i in range(M): a,b=map(int,input().split()) G[a]+=1 G[b]+=1 union(a,b) #print(P) PP=[] for i in range(N+1): PP.append(find(P[i])) #print(PP) PPP=[0 for i in range(N+1)] for i in range(1,N+1): PPP[PP[i]]+=1 #print(PPP) B=[[]for i in range(N+1)] for i in range(K): c,d=map(int,input().split()) B[c].append(d) B[d].append(c) #print(G) #print(B) ans=[] for i in range(1,N+1): ANS=PPP[PP[i]]-1-G[i] for j in B[i]: if PP[j]==PP[i]: ANS-=1 ans.append(ANS) print(*ans)
76:20 AC 4WA
コンテスト中に4WAってはじめてかもしれない。
E - Simple String Queries
長さNの文字列が与えられる。
クエリがQ個与えられ、クエリは
1 i文字目をcに変更
2 l文字目からr文字目までの文字の種類数を出力
のどちらかである。
クエリを処理せよ。
思いついたのは、下のように2次元リストを用意し、
各アルファベットの出現位置をリストに入れておく。
1 のクエリがきたら(例えば1 2 e)
eの列に2を加えてソート
bの列にあった2は一つ前の数字(ここでは1)に変えてしまう。
2 のクエリがきたら、
a～zまでをbisect_leftとbisect_rigntの間の数字の有無を判断。
あれば種類＋１
１のソートが心配ではあったが、ほとんどソートされた状態の所への追加なので大丈夫なのでは？
と思いましたがダメでした。
どうやって高速化しようか？
と、ここまでで時間切れ。
この問題はあとでゆっくり解説を見て勉強します。
結局
76:20 4完 6WA 1248位でパフォ1215 レートは-5で1264
6WAはダメです。
しかもUnionFindを作り損ねて4WAって。
その場で書けるアルゴリズムも、コンテスト中はライブラリを使ってミスを減らすべきかもしれません。
ABC101(バーチャル):水色競プロerの復習
これまで、ABCの100からだんだん過去の問題に遡って復習してきたのですが、
これでは最近の問題にたどりつかないことに気づき、方針変更。
これからはだんだん新しい問題に進むことにします。
というわけで今回はABC101にチャレンジしました。
〇コンテスト名：ABC101
〇配点：不明
〇制限時間100分(A～Dまでの4問の時代のコンテスト)
〇今回の方針
3/1にABCが生えることを祈りながら、実戦のつもりで行きましょう。
コンテスト開始！
A - Eating Symbols Easy
- と-でできた4文字が与えらえる。
最初は０で、＋が出たら＋１、－がでたらー１。
いくつになるか？
すぐ思いつく方針は下の2つでしょうか。
①countで＋の数を数える。
②＋が出たら１を足し、そうでなければ(－が出たら)１を引く。
どちらでもよいのですが、②を選択しました。
S=input() ans=0 for i in range(4): if S[i]=="+": ans+=1 else: ans-=1 print(ans)
1:36 AC
B - Digit Sums
整数Nが与えらえる。
Nの各桁の和をnとする。
Nはnで割り切れるか？
この手の問題はintとstrの変換を思いつけば難易度がぐっと下がります。
問題文の通りに実装しましょう。
N=int(input()) SN=str(N) sn=0 for i in range(len(SN)): sn+=int(SN[i]) if N%sn==0: print("Yes") else: print("No")
4:21 AC
C - Minimization
1からNを並べ替えた数列がある。
連続するK個をその中の最小値にする操作を行う。
すべて同じ数にするために必要な操作の回数の最小値を求めよ。
どう考えても、最後はすべて1になるはず。
そして、左端を１にする最善手は下の図のようになるはずで、結局左端からK-1を足していくのと同じことになりますね。
そのまま右端まで１になるようにするには・・・
あれ？数列Aはいらない？
import math N,K=map(int,input().split()) print(math.ceil((N-1)/(K-1)))
8:33 AC
D - Snuke Numbers
整数NをNの各桁の数字を足した数S(N)で割り、N
K=int(input()) D={} for i in range(1,10**4): for j in range(12): Sunuke=str(i)+("9"*j) if len(Sunuke)<=15 and Sunuke not in D: S=0 for k in range(len(Sunuke)): S+=int(Sunuke[k]) D[int(Sunuke)]=S D=list(D.items()) D.sort() import bisect d=[10**16 for i in range(len(D))] d[0]=0 ans=[0 for i in range(len(D))] for i in range(len(D)): ans[bisect.bisect_right(d,D[i][0]/D[i][1])]=D[i][0] d[bisect.bisect_right(d,D[i][0]/D[i][1])]=D[i][0]/D[i][1] ANS=[] MAX=0 for i in range(len(ans)): if ans[i]>MAX: ANS.append(ans[i]) MAX=ans[i] for i in range(K): print(ANS[i])
29:29 AC
実験って大切ですね。
今回はプレッシャーのかからない状態だったので実験ができましたが、
いつかコンテスト中のギリギリの状態で実験から答えを導き出してみたいものですね。
結局29:29で全完(4完)ノーペナ
すばらしい結果でした。
ABC092(バーチャル):水色競プロerの復習
3連休最終日、今日も朝から過去ABCで復習です。
〇コンテスト名：ABC092
〇配点：不明
〇制限時間100分(A～Dまでの4問の時代のコンテスト)
〇今回の方針
休みの朝なのでコーヒー片手に気楽にいきましょう。
コンテスト開始！
A - Traveling Budget
バスと電車で旅行する。
バスはA円orB円
電車はC円orD円
最安値を求めよ。
AとBの安いほうとCとDの安いほうを足せばよいですね。
適当にやってしまい、効率の悪いコードになってしまいました。
リストに入れてソートして・・
Bus=[] Train=[] for i in range(2): b=int(input()) Bus.append(b) for i in range(2): t=int(input()) Train.append(t) Bus.sort() Train.sort() print(Bus[0] + Train[0])
2:32 AC
普通にA,B,C,Dをintで受けて、min(A,B)+min(C,D)を出力すべきでしょう。
B - Chocolate
N人がいて、D日間の間にそれぞれ1+Ai日目にチョコレートを食べる。
最後にX個のチョコレートが残っていた。
最初にチョコレートはいくつあったか。
100人で100日まで。最大でも10^4オーダーなので全探索決定。
ansを用意して、２重ループ。
1+A日ごとにans+=1
1+A>Dになったら終了。
これをN人分繰り返し、最後にansにXを足しましょう。
N = int(input()) D,X = map(int,input().split()) ans=0 for i in range(N): cnt=0 A=int(input()) for j in range(101): if 1+A*j>D: break else: cnt+=1 ans += cnt print(ans + X)
6:29 AC
C - Traveling Plan
x座標上のN個の点を順に訪れる。
移動コストは|a-b|円
各点を訪れなかった場合の合計移動コストを求めよ。
全部の点を訪れるコストを最初に求めておき、
各点(A)を訪れなかった場合は、
全点コスト-|Ai-A(i-1)|-|A(i+1)-Ai|+|A(i+1)-A(i-1)|ですね。
N=int(input()) X = [0]+list(map(int,input().split()))+[0] SUMX = 0 for i in range(1,len(X)): SUMX += abs(X[i-1] - X[i]) for i in range(1,N+1): print(SUMX + abs(X[i-1] - X[i+1]) - abs(X[i] - X[i-1]) - abs(X[i+1] - X[i]))
14:04 AC
D - Grid Components
100x100のグリッド内で白連結成分A個、黒連結成分B個を作成せよ。
白２個、黒３個ならこんな感じで良いですね。
最初に上は全部白マス、下は全部黒マス。これで白黒1つずつの連結成分。
次に、白連結成分をつくりたければ、黒マスの中に1x1の白マスを埋めていく。
黒連結成分も同様に。
A,B = map(int,input().split()) print(100,100) L=[] for i in range(50): L.append(["#" for j in range(100)]) for i in range(50): L.append(["." for j in range(100)]) A-=1 for i in range(50): for j in range(25): if A>0: L[i*2][j*2] = "." A -=1 B-=1 for i in range(50): for j in range(25): if B>0: L[51 + i*2][j*2] = "#" B-=1 for i in range(100): print("".join(L[i]))
30:52 AC
白の大きな連結成分にくっつく形で白1x1マスを作って1WA
出力形式のミス(グリッド間に空白をいれてしまった)で1WA
実際のコンテストだったら発狂ものですね。
ABC093(バーチャル):水色競プロerの復習
昨日のABC156のDが解けずに爆死して一晩。やっと気力が戻ってきたので精進しました。それにしても久々にレート40以上削られました。
今日はABC093の復習です。
〇コンテスト名：ABC093
〇配点：不明
〇制限時間100分(A～Dまでの4問の時代のコンテスト)
〇今回の方針
心のリハビリがてら気楽にいきましょう。
コンテスト開始！
A - abc of ABC
"a","b","c"からなる3文字の文字列が与えられる。並べ替えて"abc"にできるか判定せよ。
入力をリストで受け取ってソートしてリストが["a","b","c"]と一致すれば"Yes"そうでなければ"No"
S=list(input()) S.sort() if S==["a","b","c"]: print("Yes") else: print("No")
1:33 AC
B - Small and Large Integers
A以上B以下の整数で、A+K以下、B-K以上の数字を昇順に出力せよ。
これは地味に難しいですね。
①A+K以下でB-K以上の数字を2度数えないように注意
②A+K以下だけどBより大きい、B-K以上だけどAより小さいものに注意
ですから。
pythonなら、dictで①を回避し、②はmax,minを使って回避しました。
A,B,K=map(int,input().split()) D={} for i in range(A,min(A+K,B)): D[i]=1 for i in range(max(B+1-K,A),B+1): D[i]=1 L=list(D) L.sort() for i in range(len(L)): print(L[i])
dictを使い、たとえば5を入れる場合、既にdictの中に5があろうがなかろうがdictの5には1を入れる。
後でdictをlistに変換し、listをソートして出力。
setを使っても良かったかもしれません。(setのほうが自然かも？)
6:32 AC
C - Same Integers
整数A,B,Cが与えられる。
①それらのうち2つに対して+1
②どれか1つに対して+2
①と②の操作を行い、A,B,Cを同じにする。
必要な最小の操作回数を求めよ。
A,B,Cの大きさの順がバラバラだと扱いにくいので、
A,B,Cはlistで受けて、ソートして大きい順に並べてしまいましょう。
これでlist[0]が最大、list[2]が最小です。
list[1]とlist[2]に対し、list[0] - list[1]だけ①を行う。
これでlist[0] == list[1] >= list[2]です。
次に、(list[0] - list[2]) % 2 == 0 であれば、list[2]に②を繰り返すだけでlist[0] == list[2]にできます。
(list[0] - list[2]) % 2 == 1であれば、list[2] == list[0] +1になるまで②を繰り返し、
最後にlist[0] とlist[1]に対して①の操作をする必要があります。
L=list(map(int,input().split())) L.sort(reverse=True) #print(L) ans=0 SA=L[0]-L[1] ans+=SA L[2]+=SA L[1]+=SA #print(L) if (L[0]-L[2])%2==0: ans+=(L[0]-L[2])//2 print(ans) else: ans+=(L[0]-L[2])//2+1 ans+=1 print(ans)
11:28 AC
D - Worst Case
高橋君は2回のコンテストに参加し、結果はA位、B位であった。
スコアをA*Bで定義したとき、高橋君よりスコアの小さい参加者は最大何人か？
これは難しい。
過去に解説を見て考え方を知ってるので何とかなりますが、初見で解いた方々の頭の中はどうなってるんでしょう？
基本的にA*B>=X＊Xとなる最大のXを探します。
aを1以上の整数とすれば、
(X-a)*(X+a)はX*Xより小さいので、(X*X=X^2, (X-a)*(X+a)=X^2-a^2,です)
このaを数える方針です。
後で考える際に楽にするため、AとBの小さい方をA、大きい方をBとします。
・A=3,B=6とすればX=4となり、X+1とX-1を掛けたものは必ずX^2より小さくなります。
・A=3の場合は3を飛ばして2に行っても、必ずX^2より小さくなります。
・手元でテストしてOKだったので証明せずに通しましたが、
AとBとXの関係は|X-A|<=|B-X|になるようなので、
先に(X-a-1)*(X;a)となり、その後(X-a-1)*(X+a+1)となり
結局X^2よりは小さくなります。
これを基本にして、例外を弾いていきましょう。
例外１．A=Bの場合
上図ので上段も下段も3にすると、
A*B>X*X を満たす最大のXは2ですが、X=3として、(X-a)*(X+a) a>=1としたほうが基本より1つ多くの組ができますね。
例外２．A+1=Bの場合
上図で上段を3、下段を4にすると、
A*B>X*X を満たす最大のXは3ですが、上段も下段も3のケースが作れません。
なので、基本より1つ少ない組しかできません。
例外３．A*B>X*(X+1)を満たす場合
上図で上段を3、下段を7とすると、
A*B>X^2を満たす最大のXは4ですが、XとX+1の組でも(ここでは4と5）A*Bより小さければ、
上段も下段もXｋら始める基本より、上段X、下段X+1、上段X+1、下段Xからはじめられるこちらのほうが、
1つ多くの組が作れます。
例外４． A!=BかつA*B=X*XとなるXが存在する場合
上図で上段を2、下段を8とすると、
A*B=X*Xを満たすX=4が存在します。が、問題文の条件がA*B>X*Xなので、X*Xを除く、基本より1つ少ない組が作れます。
基本にこれらの例外を加えればOKです。
Q=int(input()) for i in range(Q): A,B=map(int,input().split()) if A>B: A,B=B,A if A==B: print((A-1)*2) elif A+1==B: print((A-1)*2) else: SQ=int(pow(A*B,0.5)) if SQ**2==A*B: print((SQ-1)*2-1) elif SQ*(SQ+1)<A*B: print((SQ-1)*2+1) else: print((SQ-1)*2)
35:53 AC
もちろん初見では手も足もでません。
過去に色々な解説を見て、考え方を既に知っていたから解けた問題です。
でもいつかはこれを初見で解けるようになりたいですね。
ABC094(バーチャル):水色競プロerの復習
今日はABC094のバーチャルコンテストで復習です。
明日のABC156に向けて早解きの練習です。
〇コンテスト名：ABC094
〇配点：不明
〇制限時間100分(A～Dまでの4問の時代のコンテスト)
〇今回の方針
本番のコンテストのつもりで解く
明日への景気付に、気分良くノーミス早解きを決めましょう。
コンテスト開始！
A - Cats and Dogs
猫がA匹、猫か犬かわからない生き物がB匹いる？？
猫がX匹いる可能性があるか判定せよ。
A<=X<=A+Bが満たせれば”YES”、満たせなければ”NO”ですね。
A,B,X=map(int,input().split()) if A<=X<=A+B: print("YES") else: print("NO")
1:28 AC
Pythonだと、A<=X<=A+Bの書き方ができるんですよね。
もちろんA<=X and X<=A+Bと書いてもOKです。
B - Toll Gates
最初Xにいて、0かNを目指す。
Aには料金所があり、通るには1円が必要。
0かNへたどり着ける最小金額を求めよ。
Aのうち、Xより小さいもの、Xより大きいものを数えて、小さい方を出力すれば良いですね。
N,M,X=map(int,input().split()) A=list(map(int,input().split())) Low=0 High=0 for i in range(M): if A[i]<X: Low+=1 else: High+=1 print(min(Low,High))
5:42 AC
C - Many Medians
偶数個のNの数列がある。
それぞれを取り除いた後の数列の中央値を求めよ。
まず、N個の状態の中央2つ(小さい方をA、大きい方をBとする)のどちらかが1つ取り除いた後の中央値になります。
A以前を取り除けば、Bが、B以降を取り除けばAが中央値となります。
N=int(input()) X=list(map(int,input().split())) import copy x=copy.deepcopy(X) x.sort() A=x[N//2-1] B=x[N//2] for i in range(N): if X[i]<=A: print(B) else: print(A)
14:15 AC
D - Binomial Coefficients
n個のものから順番を無視してr個選ぶ。
aの中から2つ選び、ai個のものからaj個選ぶ方法が最大となるai,ajの組み合わせを求めよ。
aiは最も大きい数字となるのは良いとして、
ajはaiの半分に最も近いものであることは大丈夫でしょうか？
組み合わせの計算の際にある程度慣れれば自然に考察できるようになると思いますが、
そうでなければこれに気づくのは大変そうです。
はいAC！あれ？？
最後の最後でWAってテストケース。
何をやっているのでしょう。
aiとajに同じ数字を当てはめていました。
n=int(input()) a=list(map(int,input().split())) MAX=max(a) Harf=MAX/2 cnt=10**20 ans=0 for i in range(n): if MAX==a[i]: continue elif abs(Harf-a[i])<cnt: ans=a[i] cnt=abs(Harf-a[i]) print(MAX,ans)
20:54 AC 1ペナ
結局20:54全完(4完) １WA
明日への景気付け失敗。
WA自体はある程度仕方がないですが、テストケースで通らない答えを投げてはいけません。
