AtCoder Beginner Contest 174に参加しました
ABC174に参加しました。
CとFでハマって結局ABDの三完でした。
つれえ～～～～～～～～～。
A-Air Conditioner
何もいう事がないです。
B-Distance
NとDが先に与えられているので、各点の値を受け取るたびに逐一計算していくのが楽かと思います。
sqrtで平方根を計算してもいいですが、単純に二乗した状態で比較すればいいだけです。制約が2*10^5なのでオーバーフローしないように整数型には気を付けます。
C-Repsept
ドツボポイント1。かなり混乱してまともに考察できませんでした。7の数列の中で、最初にKで割り切れる数がどこにあるかを答えるという問題です。
冷静に考えると、Kで割るので余りの種類はK通りしかありません。さらに、項が1大きくなるごとに桁数が1増えていき、新しい桁には7が入ります。一般化すると、(前の項をKで割った商*K)*10+(前の項をKで割った余り)*10+7ということになります。つまり、ある項が割り切れるということは、(前の項をKで割った余り)*10+7がKで割り切れるということです。ひっ算をイメージするとわかりやすいです。ここで、Kで割った余りの種類に関心を戻すと、K種類しかないということはK+1桁目まで確認すれば必ず重複する余りが出てくることになります。余りが重複した場合、余りを10倍して7を足しても当然先の結果を繰り返すことになり、ループすることになります。こうなった場合は割り切れる数が数列に登場することはあり得ないので、-1を出力します。
コンテスト中は、Kが7と互いに素かどうか、11...1を割り切れるかどうか、などに注目して考察を進めてしまった結果、さっぱりわからなくなってしまいました。
D-Alter Altar
左から順にすべての赤い石を並べ、その後に白い石を並べるようにしたいということです。
操作が二種類ありますが、石の色を変える操作は使わなくてもいいです。というのも、操作を行わなければならない時というのは、どこかで赤い石の左に白い石があるときです。この時に、一番左側にある白い石と一番右側にある赤い石を入れ替えると、条件を確実に満たして、二か所の石の色を変更することができます。一つしか選べない操作をする必要はないことが分かります。
コンテスト中は、右からどこまで見ていったかを保持する変数を用意して左から順に確認していきました。白い石が出てきたら、右端から順に確認していき、赤い石が出てきたらカウントして、また左から見ていくようにします。左右から見ていっており、災いを招く置き方になっているところは逐次入れ替えているので、右側から一度見たところを左側からチェックする必要はありません。
E-logs
コンテスト中はよく分からなかったので飛ばしました。
貪欲的に考えようとしましたが、毎回なるべく半分になるように切ると最適ではないので(ex.貪欲に10を一回切ると5,5、もう一回切ると5,3,2になるが、二回切るのであれば当然4,3,3となるように切る方がよい)、この辺りまで考えて無理っぽいと判断しました。
解説を見て、二分探索は知っていたので、「こういう時に使うのか～」と感心しながらコードを書きました。関数を作ってコードをすっきりさせようと意識してみたら、かなり見やすく書けたような気がします。加えて、変数名に統一感を持たせたりした方がいいんだろうなと思いながらも問題ごとに適当に考えて使っているのを、やめたほうがいいような気がしました。
実装の方針としては、出力の最小値は、切る回数が十分多い時に、1になり(切り上げのため)、出力の最大値は、切る回数が0回である時に、Aの最大値になります。Aを小さい順にソートしておくことで、二分探索を使うことができます。ある値が条件を満たすかどうかはO(N)で判定できるので、O(N*longN)で時間制限をクリアできます。
二分探索と、条件判定を別々の関数に分けて書くとかなりすっきりしてよかったと思います。
F-Range Set Query
ドツボポイント2。
ある位置までに出てきた石の種類とその個数をmapで管理して、クエリごとに差分を計算してみる、という単純な方法を思いつきました。時間が間に合うか微妙な気がすると思いながら投げたところ、2270msほどでした。270msなら何とか高速化できないかなあと思って粘ったのが失敗でした。順位表を見たら結構ACしている人が多かったので、方針はあっていて何か見落としているだけかもしれないと思ったからです。グーグル先生に聞くという発想も出てきませんでした。
解説は見たので、Seg TreeやFenwick Treeについて勉強してからACしておこうと思います。
今回は以上です。
せめてCは落ち着いて解いておきたかったです。珍しくFまで分かるような回だったので復習しておきたいですね。
