ABC105参加記
ABC105(Unrated) : 2018-08-11(土) 21:00 ~ 2018-08-11(土) 22:40
AtCoder Beginner Contest 105 - AtCoder
全体463位 Rated内254位 推定perf1237
43sec間に合わなくて3完でした…くっそ悔しい
C,Dで考察時間かけすぎた
A - AtCoder Crackers
N%K==0なら丁度配り切れるのでans=0
丁度配り切れなくてもN%K < Kになるので,N//K枚ずつ配って残りを一枚ずつ配ればans=1にできる
B - Cakes and Donuts
懐かしの鶴亀算的な?
N小さいのでN-=4を繰り返して
N%7==0なら'Yes'を出力してbreak
N<0になったら'No'を出力してbreak
C - Base -2 Number
想定解とは違うなんちゃって解法です
考えたこと
色々考えたけど正直ぐちゃぐちゃになって結局何を考えてたのか自分もわからん…
(-2)nなので正負が交互に繰り返されるのでとりあえず2つずつ区切ってみる
1,2桁目で表されるのは
00
= 0
01
= 1
10
= -2
11
= -1
の4通り.これを二桁分スライドさせると(-2)2加算するので4倍になる
例えば11
(=-1) -> 1100
= -4 (=-1*4)になる
これを四進数のようなノリで実装する
実装
上で書いたようなことを実装するとだいたいこんな感じ
def calc(x): global ans if x%4 == 0: ans = '00' + ans elif x%4 == 1: ans = '01' + ans x -= 1 elif x%4 == 2: ans = '10' + ans x += 2 elif x%4 == 3: ans = '11' + ans x += 1 return x//4 while N !=0: N = calc(N)
例えばN = -9 なら
Nの推移は -9 -> (-8 ->) -2 (-> 0) -> 0
ansの推移は '' -> '11' -> '1011'
って感じ.頭が0になる可能性があるのでint型に直してからprintする
コンテスト中に通した駄コード
Submission #2990276 - AtCoder Beginner Contest 105
やってることは多分想定解法の割り算するだけを二桁ずつやってる謎解法って感じ
迷走しすぎた感
D - Candy Distribution
これも想定解法とは違うなんちゃって解法です
考えたこと
全然わからん(ごんごん並感)
累積和をとったら各区間での和がO(1)で求まるのはわかるが,区間数的にO(N2)になる.
DPとか考えてもなかなか二乗から落とせない,Mもデカいし制約からとっかかりも見いだせず
めちゃくちゃ悩んで残り20分くらいで[l,r)の区間を取った残り部分に着目してみる
sum[l,r)
を区間[l,r)の和とすると
->sum[0,N) = sum[0,l) + sum[l,r) + sum[r,N)
-> sum[l,r) = sum[0,N) - sum[0,l) - sum[r,N)
sum[l,r)
%M==0より,sum[0,N)
%Mとsum[0,l)
%Mがわかればsum[r,N)
%Mは一意に定まる.
sum[0,N)
は不変,sum[0,l)
とsum[r,N)
はそれぞれ端から伸ばしていくだけなので高々N通りずつ,
なのでsum[0,l)
とsum[r,N)
が0<=l,r<Nについてそれぞれ%M=xとなる区間が何個あるかわかれば無事O(N)で計算ができる
ちなみに想定解法は
->sum[l,r) = sum[0,r) - sum[0,l)
この形に変形して解く.すごいわかりやすそう(こなみ
実装
上で書いたように左からの累積和と右からの累積和をとり
%Mした時のあまりxとなるのが何回出てくるのかdict型(連想配列(であってるのか?))で記憶する.
defaultdict(int)
で初期化すれば任意のkeyについて=0で初期化されるのでKeyErrorが起きず扱いやすい.
この時左からの累積和についてはsetとかで何の値が出てきたのかもメモしておき存在しえないものは調べないようにする.
(M=109なので全パターン愚直に調べるとTLE)
あとはこの考え方だとl=r,つまり[l,r)が空集合となるような取り方をN+1回(植木算)してしまうのでこれを除き,
l < rとなるのが正しいがl > rとなるものもカウントしてしまうので最後に//2をする.
コンテスト中に通した(コンテスト中に通したとは言ってない)駄コード
Submission #2993281 - AtCoder Beginner Contest 105
本当に時間が無さ過ぎて焦りまくってたのでやばみが深いコード書いた
まあ結局間に合ってないんですけど!!!!
感想
考察に時間かけすぎ(特にD)
解答聞くとすごい簡単そうに聞こえるしただの累積和だしなんで思いつかなかったんや…
Unratedだったけど全完できなかったの悔しすぎるので精進します