Fは嘘と思いつつ書いたら通ってしまって驚いた。悪あがきでもしてみるものですね。
コンテストへのリンク
B. Kuroni and Simple Strings
Bにしては難しいと思う。
左から"("の個数を、右から")"の個数を数えたとき、二つの個数の最小値が最大になるところで区切る。そして、その個数ずつ、一番右から")"を、一番左から"("を削る。
この一回で操作は終了する。
この削り方だと、「最大になるところ」という性質から、その区切り目の「右側にある")"」か「左側にある"("」は全て消されている。
それでももう一回操作が行えるとすると、残った片側に"("と")"のペアが存在している場合だけど、これは最大になるときをとったので、あり得ない（その間が区切り目になるはず）。
C. Kuroni and Impossible Calculation
mが小さいところに注目。
mod mで同じ数が二つあれば答えは0。そうでなければ、要素の個数はm未満なので、愚直に計算できる。
D. Kuroni and the Celebration
直径を入力して候補を減らしていったが、実は葉を二つならどれでも良かった。確かに。
E. Kuroni and the Score Distribution
A=1, 2, 3, ... , nという数列のとき、$A_i+A_j=A_k$というi, j, k (i<j<k)の個数は最大になる。それ以下のmは全て構成可能。
1, 2, 3, ... とギリギリまで並べ、もう一個をmに合うように調整。残りを適当に大きい数にすればOK。
調整する数は5000を超えているので、「残りを適当に大きい数にする」というのを適当にやってしまった（自分は、$10^9$から5001ずつ減らした）ためHack caseができてしまっていました。
まあでもこれは、解法はほぼあっていたので……。
F. Kuroni and the Punishment
はまやんはまやんさんの解説記事が分かりやすい。
・素数が与えられたら、各数字をその素数の倍数にするのに何回かかるか調べられる
なので乱択を考えるのは良いとして、
・素数「2」の場合を考えたときを考えると答えは高々N
ということから、「操作回数が1以下である要素を選ぶ確率が1/2より大きい」と気付けば、乱択する素数の候補が絞れる。
コンテスト中は、小さい素数たちと、小さいA[i]の素因数のみを考慮したらACしてしまった。
「+1、-1の候補を考慮する」というのはこの問題の胆なので、A[i]達だけの素因数で通ってしまったのはまずいはずだけど、小さい素数を列挙したり、AではなくソートしたAを使ったりしたのがシステムテストを通った原因かもしれない。
なお、Aの候補を絞るために、set(A)について乱択すると、「操作回数が1以下である要素を選ぶ確率が1/2より大きい」の根拠が崩れるため乱択が上手くいかなくなることに注意。
このケースはシステムテストに入っています。コンテスト後解きなおしたとき、なんで通らないかが分からず苦労してしまった。
0 件のコメント:
コメントを投稿