AtcCoder Beginner Contest 169 - saika

ABC169に参加しました。

ACDの三完でした。自分の弱いところがもろに出たという感じで、大変勉強になりました。しかもCはコンテスト後に追加されたアフターケースでしっかりWAになるコードだったので実質二完というありさまでした。

AtCoder Beginner Contest 169 - AtCoder

All Submissions - AtCoder Beginner Contest 169

A-Multiplication1

かけて出力します。

B-Multiplication2

地獄を見ました。解けなかったのはもう最悪仕方ないとして、特に原因もわかっていないまま適当にいじったコードをデバッグ代わりに提出するのは止めないといけないです。普段から考察を詰め切らないで出すことがあるので、そこから改善していきたいです。

散々ほかの人が解説してくれていますが、自分で試したことを一応書いておきます。

元の数Aと、これから掛け合わせたい数Xがあったとして、A*Xをした時点でオーバーフローしているかが判定できればいいと考えたので、A*X/X＝Aにならなかったときは-1を出力するようにしてみました。コンテスト中は完全に混乱していたのでこのシンプルなコードすら正確に書けていませんでした。ただ、コンテストが終わってから書き直したところ、テストケースのhand_01.txtのみWAになっており、原因が分かりません。4294967296を二つ受け取り、かけて10の18乗以上になるので-1を出力するはずなのですが、二つ目の4294967296をかけるとオーバーフローするという判定が機能していないようです。頭の片隅に残しておいていずれ解決したいと思います。

コンテスト後に出したACコードは、これまでの積で10の18乗を割った商が、次にかける数より小さい場合には-1、さらに実際にかけて10の18乗よりも大きければ-1を出力するようにしました。こうすることで、64bit整数は9*10の18乗程度なので、10の18乗を超えてもオーバーフローしないようにして大小比較できるようにしました。

C-Multiplication3

シンプルにlong double型で処理したところあっさりACしたのでコンテスト中は何も考えませんでした。コンテスト後に解説などを見ながら挙動を確認したところ、double型で受け取ったときは990と出力されていた数値型をlong long型にキャストして出力してみたところ989と出力されたときは心底感心しました。また、同じdouble型の変数に入力と同じ数を直に代入するとキャストしても990のままでした。これはよくわかりませんでしたが、入力の時に誤差が発生している、というのをツイッターで見たので何か違うのかもしれません。

最終的には0.001を足してから100倍してキャストしたものを掛け算して、最後に100で割ることでACしました。

少数以下は出力と内部で保持している2進数の数が微小に違うこと、特にキャストする際は切り捨てに気を付けないといけないことは理解したつもりですが、また誤差に気を付けないといけない問題が出たときにはかなり慎重に調べてから解くことになりそうです。

D-Div Game

とりあえず解くことが出来たので、今回のコンテストの救世主になりました。

素数の指数表現ということを見て、素因数分解すればいいということがすぐに分かりました。ここまではよかったのですが、素因数分解をするコードを空で書くことにかなり手間取り、目も当てられない汚いコードをなんとか書いてACしました。ここも冷静に素因数分解のアルゴリズムについて解説したブログなりを参照すればよかったものの、もう少しでできそう、という気持ちで書き始めたコードにこだわって時間を浪費してしまいました。そもそも練習量が十分であれば素因数分解に気が付いたのはすぐだったのであっさり解けたことと思います。次はすぐに書けるようにしておきたいです。ライブラリの整備については少し考えたのですが、空で書くことができるように練習する方が当面はプラスが大きいかなと思ったので見送ることにしました。

素因数分解ができたら、素数pの累乗数のうち、小さいほうからいくつ作ることができるかを数えていくことで答えにたどり着きました。

E-Count Median

問題文を見てすぐに方針が立ったので、時間さえあればここも解けていたと思います。めちゃくちゃもったいなかったです。

まず、中央値として考えられる最小値はXすべてがAのときで、最大値は同様にBの時です。いずれかのXを大きくしたのに中央値が小さくなったり、Xを小さくしたのに中央値が大きくなることはあり得ません。さらに、XがすべてAの状態から、Xを一つ選んで1だけ大きくする、という操作を考えました。この時、中央値はたかだか1(Nが奇数)か0.5(Nが偶数)しか変化しません。なので、この操作を繰り返すことで、中央値の最小値から最大値までのあいだの1(0.5)刻みのすべての値を取ることができます。

ここまではすぐに分かったので、大慌てでコードを書いて終了20秒前に提出したのですが、添え字やカウントの式などが雑でWAとなりました。コンテスト後、それらを修正した後にもう一度提出したところhandmade03のみWAになりました。Nが偶数の時、中央値をきっちり2で割って求めて最大値と最小値の差を取って2倍していたのですが、おそらくここで誤差が生じていたのかと思います。2で割らずにそのまま差を取って1を足して出力したところACとなりました。

今回は以上です。普段の適当さの悪いところが遺憾なく発揮されることとなりました。毎回以後気を付けなければ…というところが出てくるのでしっかり活かしたいと思います。