ABC153:水色競プロerのムーブ備忘録(バグったら書き直しましょう。一から……いいえ、ゼロから！)
〇コンテスト名：ABC153
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
いつも通りのABC
〇コンテスト開始時のsyunsukeのレート 1367
〇今回の方針
いつも通り。
基本前から順番に解く。
Cまではテストケースも程々に速度重視で。
(Dが難しく、Cまでのペナで死にたくないので。)
はまったら順位表をチェック。
・今見てる問題を飛ばす？
・何か簡単な解法がある？
の判断材料に
コンテスト開始！
A:Hの体力をもつモンスターに一回でAの体力を削る。何回で体力を0以下にできるか？
pythonなら、mathのceilを使えば良いですね。
import math H,A=map(int,input().split()) print(math.ceil(H/A))
1:43 AC
B:Hの体力をもつモンスターに一回でAiの体力を削る必殺技を食らわせる。必殺技は一種につき一回。N種の必殺技でモンスターの体力を0以下にできるか？
Aをリストで受けて、リストの合計(sum(A))とHの大きさを比較すれば良いですね。
H,N=map(int,input().split()) A=list(map(int,input().split())) if H-(sum(A))<=0: print("Yes") else: print("No")
3:57 AC
C:N体のモンスターがいる。体力はそれぞれHiで与えられる。1劇でモンスターを仕留められる必殺技をK回放てる。それ以外は1ずつ体力を削る。最低何回でモンスターを全滅させられるか？
自然に考えて、体力の大きいモンスターから順に必殺技を放ち、残りは1ずつ削る。
ではどうやって体力の大きいモンスターを探すか？
Hをリストで受けて、降順で並べ替える。
H.sort(reverse=True)を使えば、大きい方から順に並びます。
並べたら、最初からK体のモンスターの体力を０にして、あとはモンスターの体力の合計(sum(H))を出力すればOK
!!制約にKはNより小さいとは書いていません。
KがNより大きい場合、K体のモンスターの体力を０にしようとしたらバグりそうですね。
危ない
N,K=map(int,input().split()) H=list(map(int,input().split())) H.sort(reverse=True) for i in range(min(K,N)): H[i]=0 print(sum(H))
6:32 AC
D:体力Hのモンスターがいる。H=1のときに攻撃すればモンスターは死ぬ。H>1なら体力H//2のモンスター2体に分裂する。何回の攻撃で倒せる(全滅させられる)か？
攻撃して、倒せなければ、モンスターの数は倍になって、それぞれのモンスターの体力は半分(小数点以下切り捨て)になる。
難しいことは考えずに、そのままコードに落としましょう。
答えはans
モンスターの数をNumとしてます。
H=int(input()) ans=0 Num=1 for i in range(100): if H==0: break else: ans+=Num H//=2 Num*=2 print(ans)
ループの回数を100回にしていますが、
1回モンスターに攻撃するとモンスターの体力は2**1分の1に
10回攻撃すると2**10分の1に
ここで2**10>10**3は覚えておくと便利です。
制約からHは10**12以下
10回の攻撃で10**3分の1以下まで体力を削れるので
40回攻撃すれば、10**12分の1以下に削れます。
それを考えれば50回のループでも良いですね。
H=0となった時点で６行目のbreakでループを止めて
答えを出力
11:35 AC
E:Hの体力を持つモンスターにN種類の魔法を食らわせる。各魔法はAiのダメージを与え、魔力をBi消費する。モンスターの体力を0にするために必要な最小の魔力の消費はいくらか？
どう見てもDPですね。
しかも、テストケースを見ると、魔力の消費の上限はかなり高い。でも制約を読むと体力の上限は10**4。
ここまでわかればあとはコードに落とすだけ。さっさと解きましょう。
・・
・・
・・
あれ？テストケース3が通りません。
途中で割り算を使ったから誤差が出ているのでしょうか？
割り算してmath.ceilで切り上げて・・
いや。それなら誤差はないでしょう。
一旦離脱してFを見てみましょう。
区間更新のライブラリがあれば解けそうですね。持ってませんけど。
こんな時は究極奥義。
全部消して
「ここからはじめましょう、一から……いいえ、ゼロから！」
あっさりテストケース通ります。
アルゴリズムが間違っていない自信があるのにテストケースに通らない場合は早めにやり直すべきですね。
今回はその判断が遅すぎました。
H,N=map(int,input().split()) L=[] for i in range(N): a,b=map(int,input().split()) L.append([a,b]) L.sort() import math X=math.ceil(H/L[i][0]*L[i][1]) dp=[10**20 for i in range(10**4+100)] dp[0]=0 for i in range(N): for j in range(len(dp)): if j%L[i][0]==0: Y=j//L[i][0] else: Y=j//L[i][0]+1 if j-L[i][0]>=0: dp[j]=min(dp[j],Y*L[i][1],dp[j-L[i][0]]+L[i][1]) else: dp[j]=min(dp[j],Y*L[i][1]) print(dp[H])
汚いコードですが通りました。
10分で書けるコードを40分もバグがとれずに悩んでいてはコンテストで勝てません。
おまけにdpのリストの数を10**4にしてしまうミス(0から10**4まで欲しいので、10**4+1個もしくはN+1個のリストにしなければなりません)で1ペナ
60::09 AC 1ペナ
F:N体のモンスターがいる。各モンスターの位置はXi体力はHi。攻撃は指定座標±Dに届く。何回で全滅させられるか？
区間の値を更新するライブラリが欲しいですね。
Google先生に期待しましょう。
それっぽいライブラリはすぐ見つかりますが、使い方がわかりません。
残り10分を切った頃
あれ？左端から攻撃して、攻撃の届く右の端と、その時与えるダメージの値をリストにしておいて、しゃくとり法を使えばライブラリいらない？
遅すぎました。
10分未満ではコードにできません。
Eで時間をロスしすぎなければあるいは・・
結局60:09で1ペナ5完
1587位でパフォ1137 レートは-21で1346になりました。
アルゴリズムに自信があるのにバグが取れないなら潔く書き直す。
次回以降の反省です！
ABC152:水色競プロerのムーブ備忘録(やけくそ解法でEを通す)
〇コンテスト名：ABC152
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
いつも通りのABC
〇コンテスト開始時のsyunsukeのレート 1339
〇今回の方針
いつも通り、前から順番に解く。
Cまではテストケースも程々に速度重視で。
Dが難しく、Cまでのペナで死にたくないので。
はまったら順位表をチェック。
・今見てる問題を飛ばす？
・何か簡単な解法がある？
の判断材料に
コンテスト開始！
A:NとMが与えられる。N=MならYes、違えばNoを出力。
昨日のARC級とは違いますね。
これがABC級のA問題でしょう。
N,M=map(int,input().split()) if N==M: print("Yes") else: print("No")
1:09 AC
B:aとbが与えられて、aをb個並べたものとbをa個並べたものの内、辞書順で早い方を出力
aとbを数字でなく、文字列として受け取っておいて("a","b")、"a"をb個並べたものと"b"をa個並べたものを実際に作ってリストに入れて、ソートして前にきているものを出力。
型変換の理解を問う、地味だけど良い問題ですね。
a,b=list(input().split()) X=a*int(b) Y=b*int(a) List=[X,Y] List.sort() print(List[0])
4:11 AC ちょっともたついた？どんどんいきましょう。
C:N個の整数が並んでいる。左から順に見ていき、見ている数字が今までの最小値以下なら答えを1増やして最小値を更新する。
最小値の初期値は2x10**5より大きい数値を入れておけば良いですね。
N=int(input()) P=list(map(int,input().split())) MIN=10**9 ans=0 for i in range(N): if P[i]<=MIN: ans+=1 MIN=P[i] print(ans)
6:48 AC 急げ急げ！
D:N以下の数値A,Bがあって、Aの先頭の数字とBの最後の数字が一緒、Bの先頭の数字とAの最後の数字が一緒。そんな組み合わせはいくつあるか？
考察の1手目が思いつきません。
一旦パスしてEを見に行きましょう。
Eはmodの割り算。逆元使うやつ？それは無理。
やっぱりこれを解きましょう。
とりあえずNは2x10**5以下なので、全数探索できる？
たとえば1と1〇〇〇1は条件を満たす。で、この〇の中は何でもOK。
いやそんな問題解けない。
！！
降りてきた！
例えば、数字がA〇〇Bなら、B＊Aとなら条件を満たす。
これを辞書に入れておいて・・説明は難しいのでコードをどうぞ
N=int(input()) D={} for i in range(1,N+1): I=str(i) if (I[-1],I[0]) not in D: D[(I[-1],I[0])]=1 else: D[(I[-1],I[0])]+=1 ans=0 for j in range(1,N+1): J=str(j) if (J[0],J[-1]) in D: ans+=D[(J[0],J[-1])] print(ans)
よく閃きました。
19:13 AC なんと300番台！
E:N個の整数Aiが与えられる。それらの最小公倍数を求め、最小公倍数をBiで割った値の合計を求めよ。
はいmodの割り算できません。
ただ、時間はたっぷりあるので、ググりましょう。けんちょん先生の記事がすぐにヒットしますね。
でも、私はPythonしか使えないので、Pythonでコードを書いている記事を探しましょう。
・・
ペタッと貼っておわりなものがあれば良いのですが、見つかりませんね。
さすがに記事を読んですぐに理解してコードに起こす。なんてことはできませんし、困りました。
・・
順位表確認。
あれ？結構多くの人が解いてる？
何か見落としてる？
逆元いらない？
とりあえず、Pythonは巨大な数字も扱えるんです。
ダメ元で下のコードをぶん投げてみましょう。
n=int(input()) A=list(map(int,input().split())) mod=10**9+7 def lcm(X,Y): x=X y=Y if y>x: x,y=y,x while x%y!=0: x,y=y,x%y return X*Y//y cnt=0 ans=0 LCM=1 for i in range(n): Q=lcm(LCM,A[i]) cnt*=Q//LCM LCM=Q cnt+=Q//A[i] print(cnt%mod)
あれ？通ってしまった・・
78:37 AC いやこれダメでしょ？ こんなの投げちゃだめ？ もっと早くに投げとけば良かった？
F:無理
結局 78:37 A,B,C,D,E 5完0ペナ
パフォ1594,レート+28で1367(Highest更新)になりました。
Highest更新はうれしいのですが、このEの解法はダメでしょう。
キーエンス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)
ABC151:水色競プロerのムーブ備忘録(ループは「ここからはじめましょう、一から……いいえ、ゼロから！」？)
ABC149でパフォ1800オーバーを叩き出し、一気にHighest更新！！
テンションMAXからのunratedでテンションminで年末を迎え、
私にとって今年初ratedの参加記録です。
〇コンテスト名：ABC148
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
配点も時間もいつも通りのABCです。
〇コンテスト開始時のsyunsukeのレート 1269
〇今回の方針
基本的に前から解く。
ハマってしまったら、飛ばして次の問題に進むが、順位表を時々チェック。
そして、解いた人が多い問題を解くいつも通りの基本戦略
コンテスト開始！
A:アルファベットのｚ以外の小文字が与えられるので、辞書順で次の文字を出力する。
ライブラリを使いましょう。
とは言っても、alpha=["a","b",・・"y","z"]を事前にメモ帳にでも作っておいて、問題文を読んだらコピペ。
でもこれはとても重要。速さを競う中で、一からアルファベットを入力していたら結構ミスります。しかも気づきにくく、テストケースは通ってしまいやすいのでWAを食らいます。コンテスト開始前にライブラリのメモ帳は開いておきましょう。
それさえ済めば後は簡単
s=input()
alpha=["a","b",・・"y","z"]
for i in range(26):
if alpha[i] == s:
print(alpha[i+1])
一応テストケースを確認して、テストケースが通るのを確認できたので提出
1:52 AC
B:N問あって、満点はK点で、平均M点以上にしたい。N-1問目までの点数はAiとして与えられる。
このBいつもより難しくないですか？
言い換えれば合計NｘM点以上にしたい。N-1問目までの点数の合計をsumAとすれば
NxM - sumAが
・Kより大きければ不可能なので‐1を出力
・0より小さければ０を出力
・0～Kの間ならNxM - sumAを出力
N,K,M = map(int,input().split())
A = list(map(int,input().split())
sumA = sum(A)
if N*M - sumA > K:
print(-1)
elif N*M -sumA < 0:
print(0)
else:
print(N*M - sumA)
6:26 AC なんで皆さんそんなに速いんですか？
C:ACするまでに出したWAの数を数えよ。ACできなければノーカウント。AC後のWAもノーカウント。同じ問題で複数回ACしても最初のACのみ有効。で良いのでしょうか。
それにしても、先日のno sub撤退がtwitterを賑わしている中でこの問題ですか。
no sub肯定派も否定派も、no subがどうこう考える時間があったら精進しましょう。
それは置いといて、これはリストを2つ持つと良さそうですね。
N,M = map(int,input().split())
AC = [0] * (N+1)
WA = [0] * (N+1)
ここで、リストの長さをN+1にしています。問題数はN問なのですが、リストの最初は0番目なので、必要な長さより1つ多いリストを作成すれば、入力された値をそのままリストに入れられますね。
例えば、N=3でリストの長さが3で、入力値が3だった場合、リストの3番目に入れようとしてもエラーになります。でもリストの長さを1つ長くしておけば大丈夫。
あとは、ACが出たらACリストの該当する番号を1にする（1を足すではなくて、「1にする」です。もともと0だった場合も1だった場合も関係なく、「1にする」です）。
WAが出たら、ACリストの該当番号が0ならWAのリストの該当箇所に1を足す。
for i in range(M):
p,s = input().split()
if s == "AC":
AC[int(p)] = 1
else:
if AC[int(P)] == 0:
WA[int(P)] += 1
ans=0
for i in range(1,N+1):
if AC[i] == 1:
ans += WA[i]
print(ans)
入力値は何もしなければ(int型に変換しなければ)str型。1行の入力の中に、int型とstr型で受け取りたいものがある場合に良い方法はないですかね？上みたいにできないことはないですが、面倒です。
13:48AC
D:最大20x20の迷路の最長距離を求めよ。
えらく小さな入力ですね。どう見てもこれがヒント。
マス目は最大で20x20=400しかない。ある点(出発点)からの距離は400手で探索可能。
出発点も400通りしか選べない。
400 x 400 = 16,000 よって全探索確定！
そして、迷路みたいな問題では、端の処理が面倒なので
L = []
kabe=["#"] * (W+2)
L.append(kabe)
for i in range(H):
S = ["#"] + list(input()) +["#"]
L.append(S)
L.append(kabe)
として、上下左右の端を"#"で囲ってから、縦はrange(1,H+1) 横はrange(1,W+1)の範囲で探索すれば端の処理(リスト外）を気にせずに済みます。
あとはコードに落とすだけ。
・・
・・
バグが取れません。
・・
何で？・・！！
ループは
「ここからはじめましょう、一から……いいえ、ゼロから！」
いやいや、ゼロから始めたらリスト外の処理が面倒だから一からはじめられるようにしたんでしょう？それを忘れてバグらせて何やってんの？
バグをとって
27:47AC 情けないバグのせいで時間をロスりました。
E:これは難しい！ よっしゃ！！
一応Fも開きましょう
F:2次元で3分探索でもすれば良いのか？ それとも３点に接する円を全探索？でもその場合、2点が直径になる場合はどうする？
よくわかりません これも難しい！ よっしゃ！！！
なぜ難しくてよっしゃ！かというと、この時点で400番台。EもFも難しいので、あまり解かれないでしょう。ということは、悪くても600番台で終了！そしてレートアップ！！ごちそうさまでした！
あとは、たっぷり残った時間でもしもEが解ければ、200番台も夢じゃない？
開始50分後 あれ？何でみなさんEが解けてるの？大きなレートアップは期待できないかな？
開始70分後 もしかしてE解かないとレートダウンありえる？
開始90分後 ヤバイヤバイヤバイ
終了
結局27:47 4完0ペナ
パフォ1240でレート-3で1266になりました。
いや、なんで1100人以上もこのEを解いてるの？
どんな精進をすればこの手の問題を解けるようになるんでしょう。
ABC148:水色競プロerのムーブ備忘録(今回は参考になるムーブ)
前回(ABC147)で水色に復帰したので、タイトルは水色競プロerの・・に戻ってます。
〇コンテスト名：ABC148
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
配点も時間もいつも通りのABCです。
〇コンテスト開始時のsyunsukeのレート 1217
〇今回の方針
基本的に前から解く。
ハマってしまったら、飛ばして次の問題に進むが、順位表を時々チェック。
そして、解いた人が多い問題を解く。
コンテスト開始！
A:1～3までループを回し、A,Bが含まれていなければ出力、強制終了
A,B=map(int,input().split())
for i in range(1,4):
if A!=i and B!=i:
print(i)
exit()
一応テストケースを確認して、テストケースが通るのを確認できたので提出
2:21 AC
B:空白の文字列を用意しておいて、あとは指示通りSとTから順番にくっつければ良いですね。
N=int(input())
S,T=input().split()
ANS=""
for i in range(N):
ANS+=S[i]
ANS+=T[i]
print(ANS)
5:01 AC
C:最小公倍数の定義そのままですね。
「gcdのライブラリは極力使わない」
です。
Pythonのgcdは古バージョンと新しいバージョンでは、入っている場所が違い、それを知らないと手元の環境でACなのに、いざ提出するとRE！なんてことになりかねません。また、どこかのタイミングでAtCoderのPythonもバージョンが上がるでしょう。その時また困ったことにならないよう、gcdは自分で用意しておくか、その都度作るのがおすすめです。
それと、A,Bの最小公倍数は、A*B//gcd(A,B)を知っていれば、やるだけ。
A,B=map(int,input().split())
def lcm(X,Y):
if Y>X:
X,Y=Y,X
while X%Y!=0:
X,Y=Y,X%Y
return Y
print(A*B//lcm(A,B))
8:41 AC
D:左から順に1を探す、見つかればその場所からつぎは2を、3をと繰り返し、見つけた数をカウント。
もし1が見つからなければ-1。みつかれば、N-カウント数+1を出力
13:23 AC
E:強いテストケースがあって助かりました。
①まずは、テストケースの通り、奇数の時は0
偶数の時、10が出れば0が1個増える
余裕ですね。
テストケースで確認して・・合いません。
100までシミュレートして・・
50の時にずれますね。
②50の数も数えれば良いんですね。
余裕です。
Nを50で割って小数点以下切り捨て
それと①を足せば良いんですね。
テストケースで確認して・・合いません。
500までシミュレートして・・
250の時にずれますね。
なぜ250？
50ｘ5！
なるほど、10x5の〇乗のときも数えないといけませんんね。
③②を踏まえて10ｘ5^1,10 x 5^2,10 x 5^3 の数も足せば、
テストケースに通りますね。
41:49 AC
しかし、コンテストが終わって考えてみれば、
N//10とN//50,N//250,N//1250,N//6250・・・を足したら答えになるんでしょう？
後でゆっくり考えましょう。
F:①高橋くんの最初の位置を根とした木を作成し、根から各頂点までの距離を求める。ただし、青木くんの位置より先は除外
②青木くんの最初の位置を根とした木を作成し、根から各頂点までの距離を求める。ただし、①で除外した点は使用しない。
③①で求めた距離＜②で求めた距離 を満たす中で、②で求めた距離が最も長くなる点を選択
④③で求めた点の距離-1が答え
75:24 AC
ACが出た後に気づきましたが、①で青木くんの位置より先を除外する必要はなさそうですね。
結局75:24でノーペナ全完！
522位でパフォ1650 レートは+52で1269になりました。
今回は何といってもEのシミュレーションが良かったです。
とっさに、0が増えるときだけ出力するコードを書いて走らせる。
どこで増えたか見て、考える。
良いムーブで良い結果が出たコンテストでした。
良いムーブを忘れないように記録して、今回の記事は終わりです。
三井住友信託銀行プログラミングコンテスト2019:元水色競プロerのムーブ備忘録(脅威のトラブル対応力)
今回のタイトルは良く見ると、元水色・・となっています。
前回の競プロ記事ABC144:水色競プロerのムーブ備忘録(爆死) - 競プロ弱者の解答の後にさらに2回爆死して緑に落ち、ついでにもう一回レートを下げて開始時点のレートは1182。
一回で水色復帰が狙えるレートではあるのですが、writerが競プロ界隈で有名な双子さん達。何故か彼らが作る問題と相性が悪く、毎回30以上レートを削られてしまいます。
でも、そんなことを気にしていたら、コンテストに出られません！
いつも通りpaiza.ioを開いて準備OK!
苦手意識を払拭してコンテスト参加です。
〇コンテスト名：三井住友信託銀行プログラミングコンテスト2019
〇配点 A:100 B:200 C:300 D:400 E:500 F:600
〇制限時間 100分
配点も時間もいつも通りのABCです。
〇コンテスト開始時のsyunsukeのレート 1293
〇今回の方針
基本的に前から解く。
ハマってしまったら、飛ばして次の問題に進むが、順位表を時々チェック。
解いた人が多い問題を解く。
コンテスト開始！
A:M1とM2を比べれば良いですね。
M1,D1=map(int,input().split())
M2,D2=map(int,input().split())
if M1==M2:
print(0)
else:
print(1)
一応テストケースを確認して、、、あれ？ちょっとpaiza.io重い？
テストケースが通るのを確認できたので提出
2:01 AC
B:Nを1.08で割って、切り捨てて、その数字に1.08を掛けて切り捨てて・・
これは整数にする部分を間違うと危ない算数問題だ・・
なんて危険なB問題だ・・
問題文をもう一度・・入力は50000まで。制約は甘め？そりゃB問題だから・・
いやこれ全探索
for ループでnを1から増やしながら50000まで試して、答えがあればそれを出力、無ければあの変な顔文字:(を出力。
それがわかれば簡単ですね。
X=int(input())
for n in range(1,X+1):
if int(n*1.08)==X:
print(n)
exit() #答えを見つけたら強制終了(2つ以上出力されてWAになったら大変)
print(":(")
間違うアルゴリズムじゃないけど、一応テストケースで確認・・あれ？paiza.ioがまた遅い？
待つ時間がもったいないので、テストケースを確認せずに提出！
9:15 AC テストケースの確認に時間取られすぎ。しかも確認できずに投げてるし。
C:金額の上限が100000円なので、100円から105円の商品は無限にあると考えて良さそうですね。
パッと思いつくのが、個数制限なしのナップサック問題。
知ってればただやるだけ。
X=int(input())
DP=[0 for i in range(X+1)]
DP[0]=1
Shohin=[100,101,102,103,104,105]
for s in range(6):
for x in range(X+1):
if DP[x]==1 and x+Shohin[s]<=X:
DP[x+Shohin[s]]=1
print(DP[X])
楽勝！ではテストケースで確認して・・・
paiza.ioが死にました
ネット回線の問題？
いえAtCoderには接続できます。
他のエディタ？
私はpythonerなのでanaconda(pythonの便利グッズ詰め合わせセット)が入ってます。
エディタ代わりになりそうなspyder君に決めた！
いや、コードは書けるけど、チェックどうするの？却下
データサイエンティストご用達Jupyter Notebook召喚！！
あれ？数字の入力どうするんだっけ？
時間がもったいない。
先に次の問題文を見て考察開始！
でも、どこかで勝負しないと・・
ペナルティ覚悟でspyderで書いたコードをノーチェックで提出！
26:30 AC
通った！けどすごいタイムロス・・
D:あーはいはい。3文字の真ん中を固定して考えるやつ。
前から見ていって、出てきた数字を記録(長さ10のﾘｽﾄを作り、最初は全部0、数字が出てきたら1にする)後ろからも見ていって、同じものを作る。
前、中、後 で、前と後を全探索。
中が3万、前と後ろがそれぞれ10だから、3x10**6これなら間に合うはず、怖いから枝刈りして提出。
したいけど、テストケースを確認できません。
paiza.io頼む。復活して！
リロードしてるうちに復活しました！
テストケースのチェックを済ませて提出！
55:14 AC えらくタイムロスが出てるが、エディタ復活してよかった。
E:DPっぽいがこの手の問題はとにかく紙に書いて試す！
書いて書いて書いて
やっぱりわからん。
いや分かった。見たい数字より1つ小さい数字がいくつあるかを見れば良い。
テストケースを通してpypyで提出！
WA、RE？？何事
WAはまだしもREってどういうこと？
よくわからないから、pypyからpythonに変えて提出！
やっぱり同じところでWA、RE
これはジャッジがおかしい？unrated？ぜひお願いします！
それなら質問に出てるはず。
できないケースがあるのかよ！
同じ数字が4回出るケースを処理して、REが出るってことは、tryとexceptを使って、エラーが出たら0で返すようにして提出！
93:48 AC 2WA
F:問題文を読んで、考え始めた時点で時間切れ
たくさんの人が解いてるから、時間をかければ解けるのかも？
結局A,B,C,D,Eの5完 93:48 で2ペナ
1204位でパフォ1185 レートは+1で1183
5完で緑パフォ？
いやこれだけのアクシデントで、冷えなかっただけ良しとしましょう。
とにかく疲れました。
今回のムーブはかなり良いですね。
特に、エディタがどうにもならないなら、先に問題文を見て考察だけ始めるあたりは、良くできたと思います。
水色復活は次回の宿題ですが、良いムーブを忘れないうちに記録して、今回の記事終わりです。
競プロerがDjangoでwebアプリを作る-8(はじめてのアプリができました)
Djangoによるwebアプリ作成です。
前回までのおさらい。
これまでに
・Python Django 超入門(掌田津耶乃先生)(以下超入門)
・Django girls Tutorial(日本語版)(以下girls)
・現場で使える Django の教科書《基礎編》(akiyoko先生)
・現場で使える Django の教科書《実践編》(akiyoko先生)
を使ってDjangoの学習を進め、本やブログ、動画を見ながら何となくコードを書いてアプリを作成しているような気分になっていました。しかし、akiyoko blog(akiyoko先生)によると、Djangoを学ぶ準備すらできていなかったようです。
たしかに基礎を理解しておらず、コードを写経して動きました！ではいつまで経っても力はつかないでしょう。(Djangoの雰囲気をつかむには良かったのかもしれません)
そこで、一旦手を止めて、現場で使える Django の教科書《基礎編》(akiyoko先生) を3周ほど学習しました。
その後、Udemy:【徹底的に解説！】Djangoの基礎をマスターして、3つのアプリを作ろう！でも学習を進め、ついに最初のアプリができました。
そして、調子に乗ってGitHubにアップしました。
https://github.com/syunsuke1024/Portfolio-1-competitive-programming
このアプリ、競技プログラミングの復習(復讐)用ツールです。
AtCoderという競技プログラミングサイトで問題を解いて、解いたら(解けなくても)このアプリに入力すれば、最後にいつチャレンジしてその結果がどうだたかがわかるツールです。
正直なところ、Excleで十分なのですが、Djangoの練習としてあえてWebアプリにしました。
「新しいコンテストを登録」で新しいコンテストの登録ができ、
また、AC,MISS等の結果を入力すれば、入力に応じてメインページの問題番号の色が変わります。
また、データの削除も可能です。
簡単ではありますが、CRUDのうちCRUを備えたアプリになりました。
こんなものでも、できあがると楽しいですね。
作った理由は土曜日の競プロのコンテストに負けてしまい、負けた理由は過去問の復習が不足していたことでした。競プロで勝ちたければ、アプリを作るよりは競プロの練習をすべきなのでしょうけど。
もう少し座学もすすめながら学習を進め、次はもう少し難易度の高いものを作成したいと思います。
