ABC104 :2018-08-05(日) 21:00 ~ 2018-08-05(日) 22:40
AtCoder Beginner Contest 104 - AtCoder
全体120位，Rated内22位，perf1600(inner2036) f:id:awaawa4423:20180806112035p:plain 全完77分0WA ABC初参加で初全完できたのは嬉しい…

A - Rated for Me

if elifで場合分け
閾値が1200未満なので=<ではなく＜
(サンプルケースになかったら危うくWA出すところだった)

B - AcCepted

丁寧に一つずつ条件をチェック
AとCの二文字以外小文字の判定は
PythonならS.isupper()でSが全て小文字の時のみTrueを返すので、これで一文字ずつ見ていって大文字の数が二個ジャストになっているか見る

C - All Green

考えたこと

貪欲かと思ったけどボーナスが邪魔，一瞬フリーズしかける
制約を眺めるとD<=10なのでこれをつつけば許されそうだがp<=100なので単純に全探索は許されなさそう
→ボーナスがあるから貪欲できない=ボーナスを固定できれば貪欲できる
→ボーナスの取り方は高々2^D=10³、これなら余裕で間に合う
中途半端な解き方(全完しないが1問以上解く)をする問題は複数存在しえない(貪欲できるので)
ため，全完してない中で一番点数が高いものだけを見ればいい

実装

2^Dを全探索するためにFlagをまとめて待つ配列が欲しいがitertoolsで作ろうとしてできなくて少し悩む (例えばD=2なら[[0,0],[0,1],[1,0],[1,1]])
よく見たら上の配列は二進数表記で00～11が並んでるので 0～2^D-1を二進数表記で各桁の0or1を見れば全パターン網羅できる
こンな感じで部分集合の列挙するのBIT全探索っていうらしい(無知)…常識なんですかね？こういうどうでも良いところで手が止まるのは無くしたい

追記 itertoolsでもできた

for flags in itertools.product([0,1], repeat=3):
    print(flags)

'''
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
'''

あとは各点数帯を全完したときの点数をSUMとして
・SUM >=G ならansを更新して終わり
・SUM < G なら全完してない問題のうち一番点数の高い問題(kとおく)を解く
G-SUM > (100 * k) * pkなら届かないので終わり(他パターンで網羅できるのでこれ以上調べなくてよい)
G-SUM <= (100 * k) * pkなら ((G-SUM)-1)//(100*k)+1を足してansを更新して終わり

コンテスト中に通した駄コード Submission #2956270 - AtCoder Beginner Contest 104

D - We Love ABC

考えたこと

三文字→真ん中固定して左右をみる典型パターン(だと思ってた)
左にAが何個，?が何個とかいうのは累積和を使えばO(1)で求まるのでO(|S|)で計算できる

実装

とりあえず各文字で累積和を取る
もう一度左から見ていって'B'か'?'があればそこを'B'としてつかうABC数を数え上げる
そこより左側の'A'をLq，'?'をLq，右側の'C'をRc，'?'をRqとおくと
左からA，右からCをとるのは(La * Rc) * 3^Lq+Rq
左から?，右からCをとるのは(Lq * Rc) * 3^Lq+Rq-1
左からA，右から?をとるのは(La * Rc) * 3^Lq+Rq-1
左から?，右から?をとるのは(La * Rc) * 3^Lq+Rq-2
3^x乗の係数は固定した箇所以外の?のとりかた(何でも良い)
あとは%modを忘れずに全部足していくだけ

ここで3^x乗部分について
そもそもLq+Rqは選ぶのがBなら?の総数，?なら?の総数-1なので四種類しか出てこないため
全体を通して最初に計算しておけば全部に使いまわせる
C++なら考えなくていいんだろうけどPythonだと定数倍抑えるの割と大切だと思ってたり

コンテスト中に通した駄コード (1432ms)
Submission #2957759 - AtCoder Beginner Contest 104
上の3^x乗の使いまわしを採用して書き直したコード (261ms)
Submission #2961898 - AtCoder Beginner Contest 104

f:id:awaawa4423:20180806122910p:plain
結構実行時間変わってびびる