ABC169参加記 - reborn18の競プロ日記

色変記事のためにブログを開設したので、そのまま参加記も書いてみようと思います。

入力A,Bを受け取ってその積A*Bを出力する問題でした。

入力 $A_{1}$ から $A_{N}$ をかけた値が $10^{18}$ 以下であればその値を、そうでなければ-1を出力する問題でした。

$A_{i}\geq0$ であるため0が含まれている場合に注意が必要でした。

まずソートして0を前に持ってきてから、前から積を計算していき $10^{18}$ を超えたら-1を出力して打ち切る実装にしました。

入力Aが整数、Bが小数で小数第二桁まで与えられ、これらの積A*Bの小数点以下を切り捨てた整数を出力する問題でした。

今回のコンテストで一番苦労した問題で11ペナでした。

浮動小数点数の理解が足りていなかったです。Bをfloatで受け取った時点で誤差が生じてしまうということだったようです。

最後のほうでdecimalを思い出し、あまり良くわかっていないながらも使ってみたことが功を奏しました。

Cが解けていなかったので問題文の理解に時間がかかりましたが、素因数分解すれば良いことに気づきました。

入力Nが $10^{12}$ であり素因数分解の計算量が $O(\sqrt{N})$ であることから方針として問題なさそうであることを確認しました。

とり得る中央値の個数を出力する問題でした。

まともに証明はしなかったですが、取りうる中央値の最小値と最大値がわかればその間の値も中央値になれるだろうと考えました。

提出コードでははじめに全ての数を2倍にして中央値として小数が出ないようにしたのですが、奇数の場合は中央値は整数にしかなり得ないことに気づき結局また2で割っています。

問題が読み取りづらかったですが、制約を見るとdpの感じがしたのでその方針で考えていました。

まず、
dp[i][j]:=i番目の数まで見た時に総和がjとなる組み合わせの個数
というのが思いつきましたが、ほしくなるのは何個足すとjになるかという情報であり、このままではうまくいかないなと思いました。

絶対NとSの2重ループで解けると信じて考えていると $2^{N}$ から初めてどんどん2で割ったものを足していく更新方法ならそれっぽいのかと思い、試すとサンプルと合ったので提出しました。
更新の途中でmodを計算するのを忘れており何回かTLEになりましたが、なんとかACを得ました。

コンテスト参加中のことを思い出して書いてみましたが、適当に考えてしまっているなと思いました。
また、途中からやけになってペナを気にしなくなってしまったのですが、かなり良くなかったのでもっと落ち着いてやっていきたいです。