ARC006 A, B, C 考察

ARC006 A 宝くじ

一致する個数を数えて各条件に照らして出力する。 E と L がそれぞれ 6 個で E * L。 B の分で B * L 。時間は問題ない。

https://atcoder.jp/contests/arc006/submissions/15401952

ARC006 B あみだくじ

最終行の o から順に上へとたどって答えを出力する。 N <= 10 L <= 20 なので時間は問題ない。入力が空白を含むため proconio が機能しないので面倒くさい。

https://atcoder.jp/contests/arc006/submissions/15402356

ARC006 C 積み重ね

どう証明していいのか分からないまま雰囲気で解いた。

荷物を運ぶ順番は決まっている。運ぶ荷物 w_i に対して取れる行動は 2 つ。

• 既にある山の上に置く
• 新しい山として置く

どちらを選んでも w_i を置いた山の上にはその重さ以下のものしか置けなくなる。

既にある山の場合は山の一番上の重さ以下のものしか置けないが新しい山の場合は何でも置ける。山の数を減らすことが目標であることとそれ以降に置けるものを考えると新しい山を避けて既にある山に乗せると良い。

入力例 1 。

4 3 1 2 1 …… 入力
4 3   2 1 …… 1 つ目の山
    1     …… 2 つ目の山

入力例 5 。

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 …… 入力
3 1   1                       …… 1 つ目の山
    4       2                 …… 2 つ目の山
        5       5 3           …… 3 つ目の山
          9   6     5         …… 4 つ目の山
                      8   7   …… 5 つ目の山
                        9   9 …… 6 つ目の山

既にある山から選択するのが面倒そうなので荷物ではなく山単位に走査することにした。山の一番上以下の値が来たら自身に積む操作を繰り返すようにした。すべての荷物をいずれかの山に配置したらその時点の山の数を出力する。すべての荷物が別の山になるときが最悪の状態で O(N^2) になる。

なんとなくフリーセル的な動きだ。

https://atcoder.jp/contests/arc006/submissions/15402481

M-SOLUTIONS プロコンオープン 2020 に参加した。 D まで解いた。

https://atcoder.jp/contests/m-solutions2020

リングフィットアドベンチャーを続けている。