AOJ 1161 Verbal Arithmetic (ICPC Domestic 2009 C)
ABCの問題は実装練習として進めていくとして、問題としては少し簡単なので問題を解く力が鈍らないようにICPCの問題もたまに解き進めていこうと思う。
10種類のアルファベットを全探索しても通りで、式中のアルファベットの個数は100個以下なので単純に全探索したら通るんだろうと思ったのだが、どうも時間が足りなかった。正直あまり原因は分かっていないが、定数倍高速化でいける気もする。
いずせにせよ正攻法としては各アルファベットごとに先に係数を計算した上で、枝刈りをするというものらしい。しかし僕のアプローチの方が実装がかなり楽なので、おそらく本番でこの問題が出ていたら最初の方法を試して泣いていたと思う。
全て書き直さないといけないので、結局ACできていない。ダメですね。
CD問題あたりで、こういうほぼ全探索みたいな問題が良く出るようだ。考えることはあまりないが、実装が僕にとっては割と面倒だったり、枝刈りが必要だったりするので練習しないといけない。
