0.はじめに
最近レギュラーでレートを上げてビギナーで下げるという
傾向に陥っていますが今回もそんな感じになりました。
ABくらいはなんとか行けそうかな感があったのですが
Aでいっぱいいっぱいでした。一応レートは+28でした。
1.A - +3 +5 +7
ぱっと見、差が2個ずつしか詰まらないくらいはわかりましたが
そこから先に展開できずに悩みました。
出力例の、”10 100 1000”をEXCELで手動で解いてみて
解法の方針を得ました。
【考え方】
1.3つの数字を昇順に並べ、小さい方からA、B、Cとする。
2.変数BA（B-A）と変数CB（C-B）を求める。
3.BAとCBの小さい方（差が少ない方（以下SA））を0にする。
3-1.SAが偶数のとき
3-1-1.SAを0にするための操作回数変数ans1=SA//2を求める
3-1-2.Aに7ans1を、Bに5ans1を、Cに3*ans1をそれぞれ加算。
→A=B＜C、もしくはA<B=Cとなる。
3-2.SAが奇数の時、差は0にならないので、-1を出力して終了
4.差を0にした2つの数字ともう一つの数字の差(以下SA2)を0にする。
※小さい方の数字に、3と5を一回ずつ、大きい方に7を一回足して
差を詰めていくことになるので、2回の操作で6の差が詰まることとなる。
→逆に6ずつしか詰められない。
4-1.SA2が6の倍数の時、
4-1-1.SA2を詰めるための操作回数変数ans2=(SA//6)*2を求める
4-2.6の倍数でない時は、差が詰まらないので、-1を出力して終了
5.ans1とans2を足した数を出力して終了
細かい実装は若干異なりますが、上の考えに基づき実装しACでした。
テストを通った後、提出したらREが出てしまい悩みましたが
よく見たら、変数名がBAのところABと書いている所がありました。
それが無ければ20分強ACまでの時間を縮められたのに・・・。
https://atcoder.jp/contests/arc158/submissions/39680223
2.B - Sum-Product Ratio
テスト時は総当たりしたら時間足りないだろうなという思いと
あと30分じゃ解けないなという思いであきらめて、解説をみて
解きました。
解説を読んで正負の組み合わせを考えても、1/Xの小さい方から３つ
大きい方から3つを組み合わせた6つを組み合わせれば
ありうる最大値と最小値が求められることを理解しました。
1/Xのソートも、解説を読んで理解できましたが、ここら辺の
考え方の気づきが出てこないとタプルで組にして～とか
遠回りな解決方法しか出てこないなーと思いました。
素直に 6つの組を20通り試してもよかったのですが
解説にあった、4パターンでmax、minを求めて
出力してACでした。
自分で解いた感は皆無ですが、解法を聞いてみればすっきりしたので
満足しました。
https://atcoder.jp/contests/arc158/submissions/39691305
以上