情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Regular Contest 094

AtCoder Regular Contest 094に参加しました!
ABC093 旧版:
abc093.contest.atcoder.jp
ABC093 beta:
https://beta.atcoder.jp/contests/abc093/beta.atcoder.jp
ARC094 旧版:
arc094.contest.atcoder.jp
ARC094 beta:
https://beta.atcoder.jp/contests/arc094/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 093 / Regular Contest 094
rated 1200 / 2800
4/7(土) 21:00 ~ 22:40 (100分)
100-200-300-700-700-700 (6問)
ペナルティ: 5分

方針

C問題を最速で解き、残った時間でD~Fのうち簡単なものを解きたいと思います。
全部700点ならどれか1個解ければレート維持、2個解ければレートは上がるはず

A - abc of ABC

問題文を言い換えると、'a'~'c'までの文字列は全て出てきているか?という問題になります。
これはバケットソートのような手法を用いることで、O(|S|)で解くことができます。

B - Small and Large Integers

まず、AからBまでの間に数は何個ありますか?
これは、植木算よりB-A+1個であるということができます。
次に、表示する数は小さい順K個、大きい順K個なので全部で2K個表示します。
……入出力例2と3がそうなっていませんね。この時、B-A+1個を表示していることが分かります。
つまり、2K個とB-A+1個のうちより少ない方の数だけ数を表示している訳ですね。
なので、2KとB-A+1の大小比較を行い、2Kの方が大きいならばAからBまでの数を全列挙、B-A+1の方が大きいならばAからA+K-1まで、B-K+1からBまでの数を列挙すれば良いです。

C - Same Integers

まず、問題文を見るとどちらの操作も3個の数の総和が2増えることに気が付きます。
また、全ての数を等しくしたいので、操作で増やす数はより小さい数を選ぶべきです。
まず考えるのは、max(A,B,C)に全ての数を持ってこれないかということです。
ですが、総和が常に2増えることを考えると、3max(A,B,C)-sum(A,B,C)が奇数になるならこの方法は不可能であることが分かります。
ですが、3(max(A,B,C)+1)-sum(A,B,C)なら?先ほどの式が奇数ならこの答えは必ず偶数になるでしょう。
また、総和は常に2増えるので、3max(A,B,C)-sum(A,B,C)が偶数(か0)なら操作回数は(3max(A,B,C)-sum(A,B,C))/2回、
奇数ならば操作回数は(3(max(A,B,C)+1)-sum(A,B,C))/2回だということが分かります。

D - Worst Case

まず、参加者がやけに大きいので、∞人いると仮定しておきます。
また、クエリQも小さいので各クエリに対し独立に計算しても計算量は何とかなりそうです。
以下では、あるクエリについて考えます。
今、数A,Bが与えられたとします。とりあえずA≦Bとしておきます。
この時、高橋君よりスコアの小さい人はどのような人が考えられるか列挙してみましょう。
その人のコンテストの順位をx位、y位とします。
二変数ある時は変数を1個固定して考えると見通しが良くなるので、xを固定して考えていきましょう。
x=1の時、yは1~AB-1まで考えられます。
x=2の時、y=1~(AB/2)-1まで考えられます。
以下同様に、x=nのときyの値の範囲は1~(AB/n)-1まで考えられます。
この時、各参加者は同じ順位を取れないことを考えると、(1,AB-1)、(2,(AB/2)-1)……と取ることが最適です。
まず全てのx<yとなるようなx,yを列挙し、候補とします。この時の候補はx \leq \sqrt{AB}-1なので\sqrt{AB}-1個あります。
またxとyを入れ替えた解も同様に候補とします。
次に、x=yとなる解も候補にします。
この中で、実際には作れないものを外せば個数が分かりますね。
まず、min(A, B)がxの候補に入る場合、これを外す必要があります。max(A,B)は絶対に候補に入らないので考える必要はありません。
後はどうでしょう。どうやら、全て矛盾せずに成立するみたいです。
なので、これで各クエリについて解けました。\sqrt{AB}は二分探索を用いて導出できますので、O(Qlog(AB))です。

E - Tozan and Gezan

まず、色々実験してみましょう。すると、次のようなことが分かります。
A_i \leq B_iなら必ずとざん君はA_iを1減らすし、げざん君もB_iを1減らす
なので、このようなA_iB_iについてそれぞれ操作がB_i回行われます。
逆に、A_i \geq B_iならどうでしょう?これは、A_iB_i-A_i個減らしておけば同様の話に持ち込めそうです。
ですが、全てをA_i=B_iにしてしまうとそこで操作が終わってしまうので、少なくとも1個はA_i < B_iにする必要があります。
ということは、総和の関係から必ず1個はA_i>B_iとなることが言えます。
つまり、言い換えると1個を除いて全てのB_iの総和だけ操作を行うことができます。
ならば、\sum_{i=1}^{N} B_iからmin(B_i)を引けば答えになります。
なお、最初からAとBが一致しているときは操作せず0回になることに注意してください。

結果

ooox 3完(1700点) 87:31(2WA)
107位 パフォーマンス: 2294
レート: 1722 → 1796(+74) highest!

感想

700点問題を2問正解できたのは結構大きく、レートが大幅に上がりました。
ここ3回連続でパフォーマンスが2000を超えているので、黄色になる日も近いのかもしれません。
今回、F問題も動的計画法で解けることが分かっていたので、700点問題も手が出せる問題であることが分かりました。
また次回もレートを上げて、どんどん実力を伸ばしていきたいですね。