htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 099

B - Stone Monument

https://beta.atcoder.jp/contests/abc099/submissions/2645570

問題文が!よくわからない!!塔の上には積もらず、上の方を覆い隠すようにだけ積もったってこと??よくわからないのでサンプルから雰囲気で和の公式でアレした。わたしにほんごちょっとわからない。

C - Strange Bank

https://beta.atcoder.jp/contests/abc099/submissions/2646783

Nを超えない範囲の1, 6の累乗, 9の累乗のリストを作って、Nからそれらの数を引いた答えを全てsetで持って、0が出たらそこまでかかったターン数を出力というよくわからん解き方をした。答えはあまり大きな数にならんだろうと、いかにもsetの要素数が増えてループ数が爆発しそうなことに目を瞑ってぶん投げたら1.4秒かかってやっぱりアレだった。

丁寧にDPで書き直したらクソ遅くなった件 https://beta.atcoder.jp/contests/abc099/submissions/2652056

D - Good Grid

https://beta.atcoder.jp/contests/abc099/submissions/2648980

500*500の全てのグリッドを毎回走査しなくても、最初から(i+j)%3ごとに色情報をまとめておけば、色を変える時の総コスト計算は高々150回の計算で済む(C=50, (i+j)%3=0〜2)。そのように下準備をして、色1〜Cから3色を選ぶ順列をitertools.permutationsで作って、総コストを計算し最小を更新する。

最悪計算量は50*49*48*150=17640000で107の桁になるので、pythonでは絶対に通らないし最初っからpypyで提出しようかと思ったけど普通にpython3で734msで通ってしまった。何故通ったのかわからない。