トップ > AtCoder > AtCoder ABC190

AtCoder ABC190

AtCoder

ABC190参加しました。

atcoder.jp

 

A - Very Very Primitive Game

いつものAにしてはややこしかった気がする。条件をしっかり場合分けして解く必要があります。
詳しくは公式の解説をどうぞ。

Editorial - AtCoder Beginner Contest 190

B - Magic 3

ゲームみたいですね。与えられた条件からして、それぞれの呪文をfor文で回して

  • 詠唱時間S以下
  • 威力Dより上

のものが存在すればダメージが与えられます。それを実装するだけ。

 

C - Bowls and Dishes

絵に書いて考えてみると、お皿の上にボールを載せていって、条件に当てはまるものの数を数えていく必要があります。

このときボールを乗せるK人の人は、それぞれの人が2枚の皿のうちどちらかを選んで載せていきます。

与えられた数値の上限が小さいので、K人の人がボールをさらに乗せる組み合わせは,

1 \le K \le 16なので、最大でも $2^{16} = 65536 $ です。

bit全探索で、まずボールの組み合わせを決定し、ボールをお皿においたら、そのとき満たされる条件がいくつあるかを調べればいいです。
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita  

D - Staircase Sequences

問題文が短くてきれいですね。こういうのは難問な気がする。 与えられた入力例を見てみると、どうも約数が決め手になる気がしてきます。入力例1の12とか、(3,4,5)はまさにそれですね。

公式回答や、その他いろんなブログを見ていったりした結果を解説してみます。

まず、等差数列で公差1の場合を考えてみると、初項$a$, 項数$L$ とすると、総和$ N $は

$$ N = \frac{L(2a+L - 1 ) }{2} $$

となります。式変形して、

$$ L(2a+L - 1 )＝2N $$ です。このことから、$2N$の約数の中に、答えとなる数列の項数$L$の情報が入っていることがわかります。

つまり、この$L$に対応する初項$a$を決定すれば、答えの数列が一つ決定することになります。実際に上の式を$a$について求めてみると

$$ a=\frac{ \frac{2N}{L}-L+1}{2} $$

となります。このとき重要なこととして

  1. $\frac{2N}{L}-L+1$は偶数である
  2. $\frac{2N}{L}$は割り切れる

という条件があります。
1.は$a$は整数という性質があるためです。となると1.の分子は偶数でないといけません。
2.は、$\frac{2N}{L}$が割り切れない場合は、そもそも$L$は$2N$の約数ではないですね。
なので、2は$2N$の約数として$L$を算出すると明らかに満たされています。

つまり、求めた$2N$の約数の中(これは$L$の候補)に、条件1を満たすものがあれば、初項$a$も自動的に決定される(初項$a$が何なのかは知る必要がなく、決定されたことが大事です)ため、答えの数列が1つ決定されます。

大雑把には以下のような感じ? 約数列挙のメソッドがあると早いです。

long n2 = 2 * n;
Action<long> check = (l) =>
{
    //条件1の判定
    long t = n2 / l - l + 1;
    if(Math.Abs(t) % 2 == 0){ ans++; }
};
var ls = calcDivisor(n2);//約数列挙メソッド
foreach(var x in ls) { 
    check(x);//xが回答候補の数列の長さ
}

まとめ

全般的に難しかった気がします。