AGC018 参加記録
Nafmoさん決めました(嘘です
AGCが、直近過去二回ゼロ完太陽の私が！！！
23分で！！！解けた！！！(ただし2WA)
汚い解法書いて終わらせます。(嘘でした)
AtCoder Grand Contest 018
A問題：
概要
- ボールがN個ある。値が書いてある
- ただ、ボールを増やすことができて、
- 条件は、2つ選んで取り出したものの絶対値の値が書いてあるボールを作れる
- 選んだ2つと作り出したボールを箱に戻す(ココ重要)
- それでKという数字が書いてあるボールを作れるかどうかの判定
解法(嘘解法でした)
- sortします。
- 一番大きいものが、Kより小さいときはできません。
もしこれがKと同じであればできて終わり。 - Aの集団の中にKがあったらそれもできる。(探し方は後ほど)
- それ以外のときなんですが、0を除く一番小さい差を見つけます。
(i=0~N-2)A[i+1]-A[i]でminを探す。
このときにA[i]==Kでないかも同時チェック - 出てきた最小の差とA[0](Aの最小値)を比べます。
- それで出てきたものをXとします。
- A[i]=K+X*n(このnは任意の整数)で表せれば良い。
理由はXをA[i]から何度も引けるから。 - これを移項して(A[i]-K)%X==0 の条件を満たす物を探す。
- あればできる。無ければできない。
これ理由として
でかい数から1を引き続ければその数になるでしょって言う考え方なのね。
1が作れなければ2、2が作れなければ...
0がだめな理由は0割りが起こるからです。あと引いても意味ないし...
若干正しいか怪しかったんだけど通ったので良し。
感想
こういう問題セット大好きです!!!!!
さすがですね....maroonrkさん。
B以降解ける気がしないので書きました
お疲れ様でした
おまけ。レート
1000突破
