ABC 110 反省

ABDの3完.

A問題

問題

A - Maximize the Formula

解法

条件から, どれか一個だけ10倍して足すことができるのと同値になる. よって, max\{10A+B+C, A+10B+C, A+B+10C \} が答え.

提出

Submission #3249860 - AtCoder Beginner Contest 110

感想

Aにしてはちょっとむずかしい.

B問題

問題

B - 1 Dimensional World's Tale

解法

max\{x\} \leq min\{y\} \land X \leq Yならば'No War' ,そうでなければ'War'です. 本番ではmin\{y\}とmax\{x\}だけ調べてmax\{x\} \leq min\{y\}かどうかを見て, X < Z \leq Yを満たすZが存在するかどうかはそこにさらにループを回して調べました.
今考えると, 無意味ですし実装が面倒になるだけだと思います. 実際, 実装のミスで1WAしています. (リジャッジ後もWAのままでした...)

提出

Submission #3253067 - AtCoder Beginner Contest 110

感想

これもなんか問題文が読みにくく, Bにしてはちょっと面倒です.

C問題

問題

C - String Transformation

解法

コンテスト中に解けず. 考えていたのは, あるアルファベットからアルファベットへの対応を調べ, 2つ以上に対応するものがあればNo, そうでなければYes, というロジックだったのですが, 実装も考察もまずくWAを連発.
WA解答では無向グラフのように対応を双方向に一気に定めていたため, ハッシュマップがめちゃくちゃになってしまっていたようです.
書き直した解答では, 対応する文字が2つ以上あったときにNoを出力するのは同じですが, あとで対応先の文字がただ1つのアルファベットのみに対応していることを確認するようにしています.
前者がアルファベットからアルファベットへの単射であるかの確認, 後者がその対応がアルファベットへの全射であることの確認となっています.

提出

Submission #3270441 - AtCoder Beginner Contest 110

感想

えーこれ難しくないですか><.

D問題

問題

D - Factorization

解法

『素因数をいくつかの箱に入れて分割する』というのは, ARC-004D
D - 表現の自由 ( Freedom of expression )で見ていた(解いていませんでしたが)ので, 分割数やらで掛け合わせるのかなとコンテスト中は, ベル数やらスターリング数やらを調べていましたが, 結局素因数をN個の箱に分配するときの重複組み合わせでDPができることに気づき, それを実装しました.
今考えると, ARC-004Dの解答を見れば早かったですね...
DPは,
dp[i] = i番目の素因数までを使ってN個の箱に素因数を分配する場合の数
とすると,
dp[0] = 1
dp[i+1] = _{N}H_{p_{i+1}}dp[i] \space( p_i はi番目の素因数の個数. 2*3*5^2 ならば p_1 = 1, p_3 = 2)
となります.
前後のみを見ているdpなので0次元DPに落とせます.
制約の中では, 素因数の数はたいして大きくならず, コンビネーションの前処理は定数なので, この問題の計算量はMの素因数分解がネックとなり, O(\sqrt M)となります.
実は本番のコードはO(M)の素因数分解をしてしまっています...
しかし, 通ってしまいました.

提出

(コンテスト時提出したもの)
Submission #3257928 - AtCoder Beginner Contest 110
(O(\sqrt M)に改善したもの)
Submission #3270638 - AtCoder Beginner Contest 110
実に800倍の速度の差が出ています.

感想

ささっと思いつけてよかった.

総評

B問題に不備があり, 結果unratedとなりましたが, 初めて推定パフォ1600上限を出せたのでよかったです.