AtCoder Beginner Contest 246に参加しました。
結果
A,Cの2問正解でした。
B問題は解説を読めばただの数学だったけど大学卒業して久しくこういった数学らしい数学の問題に触れていなかったので解き方が思いつかなかった…2分探索の力技で解いてみたけどwaが取れなかった…
A - Four Points
長方形のうち3点が与えられるので4点目の座標を答える問題。
４点目は与えられた３点のうちx座標とｙ座標それぞれ１回しか出てきていない値の組み合わせになるので、どうにかして仲間はずれの座標をxとyに関してそれぞれ探してあげればいい。言い換えればx1,x2,x3とy1,y2,y3それぞれで値が同じ になる組み合わせを探して、余り物を答えとして採用する。
B - Get Closer
傾きA/Bの原点を通る直線上で原点からの距離が１となる座標を答える問題。と解釈して考えてみた。
x座標がわかればy座標はA/B*xになるのでx座標を求めれば良い→２分探索でx座標を求めて、y座標は算出しよう。と考えて２分探索で解こうとした。
結局何かが悪くてずっと3WAだった。コンテストが終わるまでずっと解決できなかった…
C++だと小数の精度には限界があって、その限界のせいで正解と微妙に誤差があるのかもしれないと考えて、割りと大きな桁数でも扱えるpythonで書き直してみたけど今度はランタイムエラーだった。
次にyの値を計算するときにA/B*xと割り算をしているのでそこで誤差が出来ている可能性を考えて、から割り算を使わないよう変形した式で評価するようにしてみたりもした。ダメだったけど。
後は、原点からの距離が１という点から答えの座標は中心が原点、半径が１の円周上の点と考えてx座標は、y座標は
になるからどうにかして
がわかれば答えられそうと考えた。
結局
を求める方法がわからなかったのでその方針で解くのは諦めた。よくよく考えたら
だから
なのか…
C - Coupon
似たような問題が過去問にあった気がする。（定額割引じゃなくて、半額になるって問題が）
クーポン１枚を使えば商品の値段をX円割引ける（最小は０円）としてクーポンK枚で最小の支払い金額を答える問題。
愚直に解くなら、金額の高い商品から優先的にクーポンを使っていけば良い。しかしKの最大値がなので愚直に解くとTLEする。
じゃあどうすれば処理を省略できるかなと考えると、どの商品にクーポンを使ったとしてもX円引きなのでまとめて値引きすればかなり処理を省略できると考えた。
具体的には、０円にならない範囲で各商品にクーポンを何枚使えるのか（）とそれだけクーポンを使ったら残りはいくらになるのか（
mod X）を計算する。
の合計がK枚以上ならクーポンを全部使っても0円になる商品はない（X円引きれずに無駄になるクーポンが無い）ので
の合計からXKを引いた値が答えになる。
の合計がK枚以下なら一部の商品は0円になる。
mod Xが大きいものから順番に0円にすれば支払う金額は最小にできるので
mod Xの大きいものK-(
)個を除いて
mod Xの合計を計算すれば答えが求まる。
