ABC178を解いてみる(B問題まで)
色々あって3か月プログラミングできていなかった。だいぶ衰えている気もする。
ABCにもしばらく参加していないためリハビリも兼ねて解いてみる。
B - Product Max
正負で色々と条件分岐しないといけないか？ と思ったが、よくよく考えなくとも候補はせいぜい4通り。xは最小値か最大値のどちらかしか可能性が無く、yも同じである。あえて中途半端な値を取る理由もない。
というわけで4通り列挙してソートするのが楽。
read a b c d echo $((a*c)) $((a*d)) $((b*c)) $((b*d)) | tr ' ' '\n' | sort -nr | head -1
C - Ubiquity
解き方自体はそこまで難しくない。要は全パターンが10^n通り、うち0を1つも含まないのが9^n通り、9を1つも含まないのが同じく9^n通り。全パターンからこの2つを引くと0も9も含まない組合せを余分に引いてしまっているので、その分8^nをもう1回足して帳尻を合わせる。
ただ10^1000000とかTLEせずに解けるわけないだろ！ と半ば諦め。TLEコードは下の通り。bcでもダメ。
readonly m=1000000007
read n
a=1
b=1
c=1
for i in `seq $n`
do
a=$((a*10%m))
b=$((b*9%m))
c=$((c*8%m))
done
echo $((((a-2*b+c)%m+m)%m))というわけで放棄しかけたのだが、ここで「ループを何個かまとめて回せばいいのでは？」という発想に至る。その結果がこれ。
readonly m=1000000007
read n
a=1
b=1
c=1
for i in `seq $((n/5))`
do
a=$((a*100000%m))
b=$((b*59049%m))
c=$((c*32768%m))
done
for i in `seq $((n%5))`
do
a=$((a*10%m))
b=$((b*9%m))
c=$((c*8%m))
done
echo $((((a-2*b+c)%m+m)%m))5で割った回数だけ先にループし、端数は最後にカバーするといったもの。なんとこれでギリギリAC。やっぱ諦めるものじゃないな。
ただ最後の式はもっといい書き方があるんじゃないかと考えている。mが多すぎ。どれか減らせそうな気はするが…
a-2*b+cが-mより大きい確証がない以上、どうしても1回mで割った余りを求めて範囲を-(m-1)からm-1に絞り、mを足してもう1回余りを求めるしかないような気もする。たぶん根底から勘違いしているんだろうがどうなのだろう。
