C問題が解けなくて気分は最悪です。そんな自分に幻滅です。
A – Biscuit Generator
問題文
ビスケット生産装置を起動すると、起動してから A 秒後、2A 秒後、3A 秒後、… (A の倍数秒後) に B 枚ずつビスケットを生産します。
ビスケット生産装置を起動してから T + 0.5 秒後までに生産されるビスケットの合計枚数を求めてください。
制約
- 入力は全て整数である。
- 1 <= A, B, T <=20
考えたこと
T秒後に作られるビスケットはカウントしていいので素直に B * (T / A) でいいです。
B – Resale
問題文
N 個の宝石があり、i 番目の宝石の価値は V_i です。
あなたはこれらの宝石の中からいくつかを選んで手に入れます。
このとき、1 つも選ばなくとも、全て選んでも構いません。
ただし、i 番目の宝石を手に入れる場合コスト C_i を支払わなければいけません。
手に入れた宝石の価値の合計を X、支払ったコストの合計を Y とします。
X-Y の最大値を求めてください。
制約
- 入力は全て整数である。
- 1 <= N <= 20
- 1 \<= C_i, V_i <= 50
考えたこと
V_i – C_i が正になれば買い得なので買いましょう。逆に負なら買い損です。やめておきましょう。
C – GCD on Blackboard
問題文
N 個の整数 A_1, A_2, …, A_N が黒板に書かれています。
あなたはこの中から整数を 1 つ選んで、1 以上 10^9 以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。
書き換えた後の N 個の整数の最大公約数の最大値を求めてください。
制約
- 入力は全て整数である。
- 2 <= N <= 10^5
- 1 <= A_i <= 10^9
考えたこと
C問題は全探索、ということでたぶんなんらかの前処理をして各数字を実際に消してみてgcdを計算するんだろうなーと思いました。A_iを変えたときのgcdがO(1)とかO(n)で求まれば良さそうです。
そしてそのような前処理をうんうん考えましたがわかりませんでした。DPテーブルっぽいのを埋めていくのとか各数字の約数を数えてその個数がnかn-1で最大の約数を探すとか、色々試してみたつもりでしたが全て計算量を落としきることができませんでした。
正解
答えは前からのgcdと後ろからのgcdをどっちも計算しておいて、A_iを変えたときはgcd(front[i-1], back[i+1])を計算するというものでした。
なぜ思いつけなかったのか……本当に悔しいし悲しいし虚しいです。
とてもつらいです。
後ろから処理しておくという発想が全くなく、本当に頭の片隅にもなかったです。ちゃんと論理的に考えればわかりそうなものなのにどうしてできなかったのか……
ゴールデンウィーク中は引っ張ると思います。
D – Flipping Signs
問題文
N 個の整数が並んでおり、順に A_1, A_2, …, A_N です。
あなたはこの整数列に対して次の操作を好きなだけ行うことができます。
操作: 1 <= i <= N-1 を満たす整数 i を選ぶ。A_i と A_{i+1} に -1 を乗算する。
操作終了後の整数列を B_1, B_2, …, B_N とします。
B_1 + B_2 + … + B_N の最大値を求めてください。
制約
- 入力は全て整数である。
- 2 <= N <= 10^5
- -10^9 <= A_i <=10^9
考えたこと
先ほどのC問題とは打って変わって易しい問題。完全に配点が逆。
2個選んでそれの正負を逆転させられるらしいので要するに偶数個だったら自由に逆転させられますよ、ということ。
数列の中で負の数が偶数だったらそれらを全部正にすればよく、奇数だったら正の数字で一番小さいものと負の数字で一番大きいものの絶対値を比べて大きいものを正にすればいいです。
感想
結局パフォーマンスは1073、レートは1089->1086と真面目にAtCoderをやり始めてから初めて下がりました。
最近ずっとパフォは1500くらい出せていたのでかなりショックです。
まあC問題を100%完璧に解けるほど強いわけではないですし、これからも精進していきます……となるべきなのですが院試勉強で疲れていることもあってちょっと精進は休憩するかもしれません。
はあ……
