AtCoder ABC212
ABC212参加しました。
A - Alloy
解説 - AtCoder Beginner Contest 212
A,Bの値によって、そのままifを書き下せばok。
B - Weak Password
解説 - AtCoder Beginner Contest 212
提出 #24656509 - AtCoder Beginner Contest 212
要素は２つ。これら２つのうちどちらか片方を満たしていればWeakです。
- 数字がすべて同じ
- 数字が連番である
1.はそのまますべての桁が同じかどうかでみればよいです。
2.も(9の場合だけ気をつければ)そのまま書き下します。
各桁の数字は10で割ったあまりを見ていけば、下の桁から取り出すことができます。
詳しくは自分の提出コードをどうぞ。
C - Min Difference
解説 - AtCoder Beginner Contest 212
提出 #24663995 - AtCoder Beginner Contest 212
平たくいえば、数列A,Bそれぞれから数字を一つ選んだときに、その差が最小になるときの値を求める、ということになります。
ほぼ解答はユーザー解答と同じになりました。
そのままやると、A,Bから要素を全探索することになります。これはTLE。
なので、Aから抜き出した数字$A_i$に対して、Bの中で最も差が小さくなる数字$B_k$を選び出します。この差が小さくなるということは、$A_i$に近い数を探し出せばいいということです。
これを効率よくやるために、まずBをソートします。 (自分はAもやっちゃいましたが、Bだけでいいはず) 後の2分探索の準備でもあり、この問題ではソートしても答えは変わりません。
ソート後、C++なら、LowerBoundを使えばいいです。他の言語にない場合は、似たものを実装してライブラリ化しておくといいでしょう。
LowerBoundをソートされたBに使えば、Bの中にある最も$A_i$に近い値のインデックス$k$をとってこれます。 ただしこれで取れるのは、$A_i$以上の値です。
実際は、Bの中の$A_i$に近い値は、$A_i$より小さい場合もありえます。
例えばB=(1,10000)で$A_i$が10だったら、LowerBoundすると10000を指しますが、近いのは1です。
これを解決するため、LowerBoundで取れた$k$から一つ小さい$k - 1$も、$A_i$に近い値の候補として取ってくればいいです。
詳細はコードを見てください。
D - Querying Multiset
解説 - AtCoder Beginner Contest 212
提出 #24704348 - AtCoder Beginner Contest 212
PriorityQueueを使います。
ネックになっているのは次の２つの操作です
操作2 : 袋の中の玉の値にXを足す
操作3 : 袋の中の玉の最小値を取り出す
どちらもすべての玉を見ないといけないため、計算量は$O(Q)$であるように思えます。これがクエリ数Q回あるので、総計算量$O(Q2)$でTLEです。
これらの操作を高速化します。
まず操作3ですが、これはPriorityQueueを使えば解決します。
内部でツリー上に要素を管理し、要素の追加が$O(logN)$、取り出し時に(PriorityQueueの実装にもよりますが)常に最小の値を取り出す操作$O(logN)$が可能です。実装によるというのは、PriorityQueueがMax-heapかMin-Heap実装のどちらかによるということで、どちらの場合でも計算量は変わりません。また言語によっては標準でついてないかも知れません。今回は前から準備してあったPriorityQueue(C#版)を使用してます。これを使う以上、操作1の玉の追加もただ追加するよりは少し時間を取りますが、$O(logN)$なので許容範囲でしょう。
次に問題の操作2ですが、これはそもそも操作2が来るたびに値を足し込むことが問題です。答えに直結するのは、操作3で値を取り出したときに値をメモしておくことなので、
- 操作2が来る度に足し込む値deltaを覚えておく(何度も操作2が来たら、deltaにさらに足し込む)
- 操作3が来たら、袋から最小値を取り出し、値をメモする前にdeltaを足し込む
ことで、操作2の全玉の探索をなくすことができます。
ただし、これだと、以下の場合に問題になります
| 操作 | X | ※ |
|---|---|---|
| 1 | 1 | |
| 1 | 2 | |
| 2 | 100 | ※1 |
| 1 | 3 | ※2 |
| 3 | なし | ※3 |
※1の実行後の状態は以下です。
玉=(1,2)
ただしdelta=100
※2の実行後の状態は以下です。
玉=(1,2,3)
ただしdelta=100
このまま※3を実行すると、最小値として欲しいのは3ですが、これにdeltaが足されるために、実際にメモされる値は103となります。操作2の後に玉3が入ったので、本来deltaは足される必要はないはずです。また、deltaを足すことで、操作3の目的である「最小値を取り出す」を達成できていません。
よって※2の操作1実行時に予め3からdeltaを引いておけば、次の※3の段階で再びdeltaが足されるため、+-0で帳尻が合います。
後は提出したコードを御覧ください。
まとめ
DはPriorityQueueだという事はわかってもその後の工夫ができなかった... せっかく以前ググりまくって用意したのに～
