ABC121
ABC121 感想
初の全完で嬉しいｖ＾＾ｖ
時間的にはこんな感じ!!
AGCが延期のため急遽用意された為か全体的に優しいイメージ
A - White Cells
最初見て震えた
何も思いつかなかった死んだと思った
とりあえず方針としては全体の個数から黒くした個数を引くことにする
全体はH×W個ある
まず行から黒くすると、h×W個黒くなる
次に列を黒くするが重複を防がなければならない
1列に白いマスはまだH-h個残っていることから、(H-h)×w個黒くすることになる
よってH×W-h×W-(H-h)×w個が残った白いマスである
H,W = map(int, input().split()) h,w = map(int, input().split()) p = H*W q = h*W+w*(H-h) print(p-q)
B - Can you solve this?
特に思いつかなかったから工夫ゼロ
ただの全探索
N,M,C = [int(i) for i in input().split()] B = [int(i) for i in input().split()] ans = 0 for _ in range(N): A = [int(j) for j in input().split()] p = C for i in range(M): p += A[i]*B[i] if p > 0: ans += 1 print(ans)
C - Energy Drink Collector
2×N配列を用意して値段と個数を入れる
その配列を値段でソートした後にM個を超えないように買っていくだけ
Bと同様にコードに起こせるかどうかの問題な気がする
N,M = [int(i) for i in input().split()] li = [] for _ in range(N): a = [int(i) for i in input().split()] li.append(a) li.sort() p = 0 ans = 0 for i in range(N): if M > li[i][1]: M -= li[i][1] ans += li[i][0]*li[i][1] else: ans += li[i][0]*M print(ans) exit()
D - XOR World
解けたからというのもあると思うがDとは思えない簡単さだった
2 XOR 3や4 XOR 5の様にN(偶数) XOR N+1の場合は必ず1になる
後はそれが偶数回あるのかどうかを調べればいい
Aが偶数でかつBも偶数で間が偶数回1が出るなら出力はB
1が奇数回なら出力はB XOR 1となる
Aが偶数でBが奇数なら間の1が偶数回の時、出力は0で奇数回の時1となる
Aが奇数でかつBも奇数なら間の1が偶数回の時、出力はAで奇数回の時A XOR 1となる
Aが奇数でBが偶数なら間の1が偶数回の時、出力はA XOR Bで奇数回の時 A XOR B XOR 1となる
長く書いてしまったが実際にノートに実際に書いてみると分かりやすいと思う
自分は解けると思った興奮で、1が偶数回の時を考慮し忘れてしまい1WAを出してしまった
書き忘れたがA=Bの時はAを出力すればいい
コードが冗長になっているので終わったら他の人のを参考にして短くしたい
A,B = [int(i) for i in input().split()] if A == B: print(A) exit() p = B-A+1 q = p //2 if A%2 == 0: if p%2 == 0: if q%2 != 0: print(1) else: print(0) else: if q%2 != 0: print(B^1) else: print(B) else: if p%2 == 0: if q%2 != 0: print(A^B) else: print(A^B^1) else: if q%2 != 0: print(A^1) else: print(A)
ABC120
ABC120 感想
3完
パフォーマンス:1204
rate:+42
とここ最近ではなかなかいいできだった
A - Favorite Sound
単純にBをAで割りCより多いかそうでないか判定する問題
コードはこちら
A,B,C = [int(i) for i in input().split()] if B//A >= C: print(C) else: print(B//A)
B - K-th Common Divisor
A,Bの約数のうち大きいほうからK番目を見つける問題
正直うまいやり方が全然見つからなかった
約数の探し方も何も工夫せずに1からmin(A,B)まで全部探してリストに追加するごり押し
TLEにならなかったので良しとしたがひどい．．．
A,B,K = [int(i) for i in input().split()] count = 0 p = 1 l = [] while p<=A and p<=B: if A%p == 0 and B%p == 0: l.append(p) if count == K: break p+=1 print(l[-K])
C - Unification
問題文が複雑で一見もの凄い難しそうに見える
実際に自分で何個かテストケースで試してみると意外と単純なのに気付ける
というのも操作が終わった後残る数字は全部0or1の1種類に決まるからだ
2値でやってるので当たり前だが意外と盲点だった
なので実際のコードは非常にシンプル
S = list(input()) a = S.count('1') b = S.count('0') print(min(a,b)*2)
0or1数が少ないほうが全部消えるため、少ないほうに2倍かけた値が消えた個数になる
D - Decayed Bridges
問題がかなり複雑でもの凄い難しかく解けなかった
ただ他のABCのD問題に比べると手が付けやすいほうだったのかとは思う
N個町があり、道がすべてない場合の不便さは1~Nまですべて足し合わせた数値になる
そこから橋が架かっていくにつれ不便さがどれだけ解消していくかの方向で考えていくと解けそうな感じはした
実際には感じがしただけだった；；
AGC015 A. A+...+B Problem
概要
AGCの過去問を解き、どういった思考で解いたのかをできるだけそのまま書いてみた
問題
問題文 すぬけ君は、整数を N 個持っています。このうち最小のものは A、最大のものは B です。 すぬけ君が持っている整数の総和としてありうる値は何通りあるでしょうか。 制約1≦N,A,B≦10^9 A,B は整数である
解法
入力例1を用いて実際に考えてみる。
4 4 6
最小値 4で最大値 6ということで間に入る数値は{4, 5, 6}(種類はB-A+1種類) 最小値と最大値が決まっていることから間の文字は2個(N-2個)
問題では整数の総和としてありうる値なので、最小値と最大値を無視し、間の値にのみ注目すればいいことが分かる
よって全組み合わせは{4-4, 4-5, 4-6, 5-5, 5-6, 6-6}の6通り この際に総和が等しくなってしまう組み合わせは{4-6 & 5-5}である
以上の事から出力は 5となる
なるほど、分からん…
109ということで全探索はあきらめる
他の入力例をみるも特殊なケースしかないので、自分で考える必要がありそうだ
4 4 7
の入力の時を考えてみることにする
間に入る数値は{4, 5, 6, 7}の4種類
間の文字の個数は2個
全組み合わせは{4-4, 4-5, 4-6, 4-7, 5-5, 5-6, 5-7, 6-6, 6-7, 7-7}の10種類
この際に総和が等しくなってしまう組み合わせは{4-6 & 5-5, 5-7 & 6-6, 4-7 & 5-6}である
仮説をたててみる
仮説: 左側の数値を iとすると i+2以上の数と組み合わせてしまうと被ってしまうので i - i+1 で組み合わせを作る。
i - i+2 の組み合わせは i+1 - i+1 と等しい i - i+3でも i+1 - i+2 と等しい
この仮説をもとに再度入力例1のケースで考えると
4 4 6
仮説をもとにした組み合わせ{4-4, 4-5, 5-5, 5-6, 6-6}の5種類となり上手くいく
4 4 7
の際も{4-4, 4-5, 5-5, 5-6, 6-6, 6-7, 7-7}の7種類で上手くいく
B-A+1種類の数値の中で最大値以外は2個組み合わせを持てるので
(B-A)*2+1
が答えになりそうだ
後はイレギュラーな A>Bまたは N=1だったりとあてはまらないケースを外してコードにすると
N,A,B = [int(i) for i in input().split()] hanni = B-A+1 N -= 2 if A == B: print(1) exit() if hanni <= 0 or N <= 0: print(0) else: ans = (hanni-1)*2+1 print(ans)
あっ．．． N = 4のケースしか考えていなかった．．．
N = 5のテストケースを自分で考えてみた結果
(B-A)*(N-2)+1
で良さそうなことが分かる
よって
N,A,B = [int(i) for i in input().split()] hanni = B-A+1 N -= 2 if A == B: print(1) exit() if hanni <= 0 or N <= 0: print(0) else: ans = (hanni-1)*N+1 print(ans)
というわけでAC
結果:18分と1WAで解けた
1WA がとても勿体ない形だったのでサンプルケースがしっかりと揃ってないときは自分でいったん落ち着いて吟味することが必要そう
一番短いコード
N,A,B = map(int,input().split()) print(max((B-A)*(N-2)+1,0))
なるほど．．．の一言につきる
