naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉C問題集中アタック (074 - 056)

週末を溶かす(というほどの事でもない。ProjectEuler埋めのほうがよく溶ける)

C埋めで学んだこと:「オーバーキルに注意」。Cなんだから(300点問題なんだから)そんな難しい事させるはずがない、って少しは思ってもいい

6月8日

ARC 074 C - Chocolate Bar (400)

・3分割するパターン(を縦、横):O(1)
・2分割して片方を直角に2分割するパターン(を縦、横):最初の2分割の分割位置を全探索しちゃってもO(H+W)
→AC
https://beta.atcoder.jp/contests/arc074/submissions/2634326

ARC 073 C - Sentou (300)

・1人目〜(N-1)人目までについて:min(次の人が来るまでの時間, T)
・N人目:T
の合計
→AC
https://beta.atcoder.jp/contests/arc073/submissions/2634350

6月9日

ARC 072 C - Sequence (300)

・累積和の負号が + - + - ... になるケースと - + - + ... になるケースを試して小さい方
・ある地点までの累積和の負号が期待と違ったら、(期待する負号)*1になるように動かす。期待通りなら動かさない。
→AC
https://beta.atcoder.jp/contests/arc072/submissions/2636155

ARC 071 C - 怪文書 / Dubious Document (300)

・各文字列について、アルファベット各文字の使用回数を数える
・全文字列について、アルファベット各文字の最小使用回数を集計する
・それを用いて文字列(辞書順最小)をビルド
→AC
https://beta.atcoder.jp/contests/arc071/submissions/2636166
// 最初sortしてunique取ってみたいなことをしてしまってaacが出なかった

ARC 070 C - Go Home (200)

200て何だよ
1ステップずつシミュレーションしていけばt=3ぐらいで気づく
時刻tに存在できる範囲が[-t(t+1)/2, t(t+1)/2]であることを
というわけで X <= t(t+1)/2 な最小のtを求める問題なんだけど
高々√Xぐらいの回数、と思って愚直にtをインクリメントしていくループを書いた
→AC
https://beta.atcoder.jp/contests/arc070/submissions/2636175

せっかくなので2次不等式で解くやつも書いた
200納得
→AC
https://beta.atcoder.jp/contests/arc070/submissions/2636183

ARC 069 C - Scc Puzzle (300)

Sは(多分)分解できないがCは2つ合成してSにできる
1S + 2C または 4C で Sccができる
S >= 2C なら Cをあるだけ使って終わりなので C/2 が答え
S < 2C なら まずSを使い切って(Sがなくなる)、
2Cを半分SにしてSccの材料にする、ので S + (C-S)/2 が答え
→AC
https://beta.atcoder.jp/contests/arc069/submissions/2636202

ARC 068 C - X: Yet Another Die Game (300)

6-5-6-5-... で
→AC
https://beta.atcoder.jp/contests/arc068/submissions/2636223

ARC 067 C - Factors of Factorial (300)

・1からNまで素因数分解してそれを足し込んでN!の素因数分解を求める
・Π(素数p_iの出現回数+1) を剰余で求める
→AC
https://beta.atcoder.jp/contests/arc067/submissions/2636236

ARC 066 C - Lining Up (300)

出てくる数は
・Nが奇数 → 0,2,2,4,4,...(N-1)/2,(N-1)/2 を混ぜたやつ
・Nが偶数 → 1,1,3,3,5,5,...,N/2.N/2 を混ぜたやつ
になっているはずで、そうでなければ0
あとはそれぞれの数の出現回数(の階乗)を剰余をとりながら掛け合わせていく
→AC
https://beta.atcoder.jp/contests/arc066/submissions/2636245

ARC 065 C - 白昼夢 / Daydream (300)

(これ前にもやった気がする)
遷移マシーンを書いた
→AC
https://beta.atcoder.jp/contests/arc065/submissions/2636293

別の書き方もしてみた
→WA(2),AC
こういうのバグりやすい。テストケース全部書くべき。
https://beta.atcoder.jp/contests/arc065/submissions/2636361

解説より

なるほど、ひっくり返してみると一意に解ける
これならバグらない
→AC
https://beta.atcoder.jp/contests/arc065/submissions/2636388

ARC 064 C - Boxes and Candies (300)

・先頭から2つの和とxとの差分を答えに加算。可能な限り後の方から(貪欲に)引く。
・1つずつずらして最後まで。の合計
→AC
https://beta.atcoder.jp/contests/arc064/submissions/2636985

ARC 063 C - 一次元リバーシ / 1D Reversi (300)

色が変わっている箇所を数えるだけでは
→AC
https://beta.atcoder.jp/contests/arc063/submissions/2637014

解説より

解説の「最終的に区間の数を 1 にすることが目的で、石をひとつ打つことで区間数を 1 減らせる」こういう洞察がパッと思いついたらいいな

ARC 062 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report (300)

・i回目まででのTとAの可能な最小得票数(tmin,amin)を調べていく。最初は(0,0)
・TiとAiは互いに素、って問題文で言ってるからgcdを取る必要はない
・tmag = (tmin>Tiのとき:tmin≦Tiにするのに何倍すればいいか; otherwise 1)
・amag = (amin>Aiのとき:amin≦Aiにするのに何倍すればいいか; otherwise 1)
・Ti,Aiにmax(tmag,amag)を掛けたものが新しい(tmin,amin)
・N回やった後のtmin+aminが答え
→AC
https://beta.atcoder.jp/contests/arc062/submissions/2637174

ARC 061 C - たくさんの数式 / Many Formulas (300)

数式をevalできる言語だったら総当たり(最大N-1箇所の隙間に+を入れるか入れないか、なのでO(2^N)だけど高々512通り)でevalして足し算するだろう。

今回はちょっと違うアプローチで。

sのあるsubstring [i,j) が登場する回数は(その左側の組み合わせの数)×(その右側の組み合わせの数)なので、int(その区間)×その回数、の合計を求めたい。
ある長さの文字列の組み合わせの数は(分割箇所0の場合)+(1の場合)+ ... +(L-1回の場合)なので\sum_{k=0}{L-1{}_{L-1}C_k=2^{L-1}]通り。
(N+1箇所からi<jなi,jの取り方を全て試すのでN(N+1)/2でO(N^2)だけど高々60回)
→AC
https://beta.atcoder.jp/contests/arc061/submissions/2637821

ARC 060 C - 高橋君とカード / Tak and Cards (300)

(1≦N≦16のデータセットに正解すれば部分点200…というのは65535通りの総当たりをするやつか)
・m枚選んだ合計がx、というのをDPで表にしておく。50^4\simeq 10^7のループで行ける。
・m=1〜Nについて、dp[m][A*m] をルックアップして合計
→AC
https://beta.atcoder.jp/contests/arc060/submissions/2637938


ARC 058 C - こだわり者いろはちゃん / Iroha's Obsession (300)

・i=[N..999999] の範囲で総当たり
・d[] は bool[10] の配列に移し替えたほうが便利。
→AC
https://beta.atcoder.jp/contests/arc058/submissions/2638354

ARC 057 A - 2兆円

ARC 057より前は問題名がC,D,E,FじゃなくてA,B,C,Dなのね…そして配点が100点×4

・最初の所持金はa_0=A円。
・1日後にはa_0+(1+ka_0)=(k+1)a_0+1円。m=k+1とおいてma_0+1円。
・2日後にはma_0+1 + (1+k(ma_0+1)) = (k+1)(ma_0+1)+1 = m^2a_0+m+1円。
・d日後にはm^d+(m^{d-1}+m^{d-2}+...+m^2+m+1)円。
・これが2兆円以上になる日数dを二分探索で求める。探索範囲は(0,2e12]。
・kの値によってはオーバーフローするので注意。m=1(k=0)の場合と2以上の場合に分ける。
s=1+m+m^2+...+m^{d-1}で2e12に届かない場合、m≦1e6+1なのでm^d=s(m-1)+1\le2\cdot10^{18}でlong longに収まる。
m^d\cdot a_0 >= 2\cdot10^{12}-s を調べる。左辺はlong longに収まらない可能性があるので注意。(a_0で両辺を割ってみたりlogを取ったりしてみた。long doubleで精度大丈夫かな)
→AC
https://beta.atcoder.jp/contests/arc057/submissions/2638491

最速提出のtozangezan氏のコードを見て

なにこれ愚直にシミュレーションしても間に合うのかよ(k=0とそれ以外の場合分けは必要だけど)

解説より

「求める日数は高々log_2 10^{12}+1日となり、愚直にループを回しても間に合います。

はい。。。

6月13日

ARC A(=C)のAC率を50%にするために解いたやつ

ARC056 A - みんなでワイワイみかん (100)

100点×4の時代のARCだけどこれは正真正銘A問題だ
K÷L=Q...Rとしてmin(BQ+AR, B(Q+1))を返すだけ
→AC 5'01
https://beta.atcoder.jp/contests/arc056/submissions/2661251