naoya_t@hatenablog

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

AtCoder Grand Contest 025

6/3 21:00-23:10 (130分)
配点200-700-700-800- って…

残り2分11秒で2問目を通して2完900点、497位。(1739→1741(+2); パフォ1755)
f:id:n4_t:20180604004536p:plain:w400

A - Digits Sum

面倒くさいからpythonで文字列処理

n = int(raw_input())
a = 1
best = 999999999999999
def score(a, b):
    return sum([int(c) for c in str(a) + str(b)])
while a <= n/2:
    b = n - a
    best = min(best, score(a, b))
    a += 1
print best

→AC (4'55'')
https://agc025.contest.atcoder.jp/submissions/2607298

B - RGB Coloring

998244353と来たら畳み込み問題、という話はこないだ離散フーリエ変換まわりで見かけていたのだけれど…
最初の1時間ぐらい、必ずしも色を塗らなくてもよいという事を考慮せず問題を難しくしてた…


A,Bが何回加算されるかだけ考えてみる。
0段目:(0,0) の1通り
1段目:赤(+1, +0), 緑(+1, +1), 青(+0, +1), 塗らない(+0, +0) だから、(0,0) (1,0) (1,1) (0,1) それぞれ1通りずつ

1 1
1 1

2段目:同様に増殖して (0〜2,0〜2) の9パターンに分裂するのだけれど、それぞれ

1 2 1
2 4 2
1 2 1

通りになる。二項係数数列 (2C0, 2C1, 2C2) = (1 2 1) を2つ掛け合わせたというか畳み込んだものである。

・・・

n段目:二項係数数列 (nC0, nC1, ... nCn) を2つ掛け合わせたというか畳み込んだものになる。

この2次元マトリクスから分かるのは、Aをi回 Bをj回足すことになるパターンは nCi x nCj 通りある、ということ。この時点ではKは絡んでいない。

赤でr回、緑でg回、青でb回塗る(無色がa=N-r-g-b回)とき

  • r + g + b + a = N
  • Ar + (A+B)g + Bb + 0a = K

を満たす。2番目の式を変形して A(r+g) + B(g+b) = K が得られる。i=r+g, j=g+b である。
とすると、Ai + Bj = K を満たす i, j の組すべてについて、上述のように nCi x nCj 通りのパターンがあるので、Ai + Bj = K の非負整数解を列挙しながら足しこんで行けばよさそう。

→TLE
https://agc025.contest.atcoder.jp/submissions/2612535

ああ(あと8分しかないのに)
nCr のnはNだけだから1次元配列を用意しておけば…準備に多分O(NlogN)、ルックアップに毎回O(1)で行けるしそうしよう
あれ?ルックアップテーブルが全部0だ...(cinからNを読み込む前にやってたYO)
そこだけ直して
→AC (残り2'11'')
https://agc025.contest.atcoder.jp/submissions/2612868
ふぅ...

〜〜

Ai + Bj = K の非負整数解、0≦i,j≦Nだから高々N通りの全探索でよくて、それぞれがO(1)の演算で解けるならO(N)で行けるじゃん…
dotorya氏の最速解 https://beta.atcoder.jp/contests/agc025/submissions/2607182 を見て納得。(とてもシンプル)

C - Interval Game

問題は読んだ
最善手問題無理
パス

D以降

読んでない