AtCoder Beginner Contest 255 参加記録
コンテスト中AC:A
惨敗でした。コンテスト後ですが、自力でEまでは解けました。
2022/07/14 E問題の赤字部分がになっていたので、
に修正
B - Light It Up
半径の2乗
を二分探索します。
2乗しているのは、long doubleなどの実数だと誤差が怖いためです。
二分探索では、以下を判定基準にします。
- 全ての人が
のいずれかの人が持つ明かりに照らされる
これはで全探索できますが、コンテスト中はこの判定の実装が間違っていました。
の上限として、
を見積もっても、十分余裕がありました(厳密には
くらい?)。
最後に2乗根をとって答えとします。
https://atcoder.jp/contests/abc255/submissions/32422863
C - ±1 Operation 1
等差数列とします。
は、
の最も近い要素にするのが最適です。
値の大小順にを
に挿入すると以下の3通りが考えられます。
それぞれのケースの答えは、
です。
1,3のケースは簡単に求められます。問題は2のケースですが、これは二分探索により求められます。
コンテスト中はのケースが抜けていました。
Submission #32422643 - Aising Programming Contest 2022(AtCoder Beginner Contest 255)
D - ±1 Operation 2
例えば、の
未満の要素が
であったとします。
これをにしたい時にかかる操作回数は、
式変形すると、
となり、とすると、
となります。
同様に、より大きい
の要素を
とすると、必要な操作回数は、
となります。
余談ですが、式は説明のために書きましたが、コンテスト中は棒グラフを書いて、で線を引く感じをイメージしました。
解法ですが、未満と
より大きい要素の和を効率よく得られればよいです。
の順序は無視できるため、
を昇順ソートして、累積和を計算しておくと、二分探索して和を得られます。
具体的には以下のようになります。
を昇順ソートする
の累積和
を得る
- 各クエリについて、以下を行う
- 二分探索で、ソート済みの
の要素の内
未満の最大値
と、
より大きい要素の最小値
を得る。
を出力する
なお、が存在しない場合の例外処理が必要です。
コンテスト中はクエリの処理部分を以下のようにしていました。
以上の最小値
を二分探索で得る(lower_bound)。
を出力する
と
に分けるような方法です。
この実装は、に
が存在すれば、おそらく問題なく動作すると思うのですが、そうで無い場合、例えば以下のようなケースで答えがおかしくなります。
1,5を3にするのにそれぞれ2回の操作が必要なので、計4回となるはずです。しかし、上記の実装だと、となり、
となってしまいます。
おそらくを大きい方の和に入れておけばよかったです。つまり、
と
という風に分けておけばよかったものと思います。
Submission #32420079 - Aising Programming Contest 2022(AtCoder Beginner Contest 255)
E - Lucky Numbers
コンテスト後に解きましたが、思わぬところでTLEになり解決に時間がかかりました。
は
と
で表現できます(便宜上、
とします)。具体例を示すと、
という感じです。
ここで、定数部分をとします。
そうすると、は以下のように表現できます。
が偶数の時、
が奇数の時、
また、は、以下の漸化式で計算できます。
ここまでで前準備が終了です。
少なくとも1つはラッキーナンバーにしないと損をするので、がそれぞれ、
である時のラッキーナンバーの数を全探索します。
である時を考えます。
は以下のように計算できます。
が偶数の時
が奇数の時
が求まると、
がラッキーナンバー
となるための
が満たすべき条件がわかります。すなわち、
が偶数の時
が奇数の時
従って、予めについて、偶奇を分けてハッシュマップに個数をカウントしておけば、上記を満たすようなものの個数を
で得られます。
のときに、
となるものがあるかを
で調べられるので、時間計算量は
となり、問題ないと思われました。
しかし、実装時C++のunoredered_mapでこれを実装するとTLEになりました。
結局、とその個数をpairにしたvectorを昇順ソートし、lower_boundすることでACしました。
Submission #32478157 - Aising Programming Contest 2022(AtCoder Beginner Contest 255)