AtCoder ABC201

ABC201参加しました。

atcoder.jp

 

A - Tiny Arithmetic Sequence

以下と同じになったので、解説は省略。 式変形が鍵でした。

blog.hamayanhamayan.com

解説 - AtCoder Beginner Contest 201

B - Do you know the second highest mountain?

「sort()して、上から2番目」が楽なんですが、今回は公式解答の別解に沿った方法。

    for(int i=0; i<N; i++){
        cin >> S[i] >> T[i];
        auto p = make_pair(T[i],S[i]);
        if(top < p){//最大値topよりも大きい場合
            sec = top;
            top = p;
        }
        else if(sec < p){//sec < p < topなので、secだけを更新する。
            sec = p;
        }
    }

ちょっとややこしいかも。ソートすればO(logN)ですが、上だとO(N)なので、ソートしたほうが速そう
解説 - AtCoder Beginner Contest 201

C - Secret Number

Submission #22639726 - Mynavi Programming Contest 2021(AtCoder Beginner Contest 201)

意外に手強かった。
自分用に説明は残しておきますが、やっぱりごちゃごちゃ感が拭えないので、公式解説動画のほうがすっきりしてる気がします。

0~9999までの暗証番号を全部試していく方法を取りました。

  1. xが書かれた数字が暗証番号にあったら、絶対に正解とは違う暗証番号であるため、こういう数字は0~9999のパターンから除外します。
    これを弾くことで、「正解となる暗証番号かもしれない4桁の数字の集合$ P $ (probabily)を作成します

  2. oが書かれた数字と?が書かれた数字について、全部「使う」場合の暗証番号の総数$ N $を求めます(最大10000)。これは(oの数字の総数 + ?の数字の総数) の4乗となります。
    4桁それぞれの場所について、当てはまる数を(oと?の数)の中から選ぶため、こういう式になります。

  3. この総数$ N $では、不要な暗証番号のパターンが含まれているので、大きすぎる値になります。 「oにかかれている数は、絶対に暗証番号に含まれる」必要があるという条件から、$ P $に含まれている数の中から、「oのついた数が、一つも含まれてない」ものを除外していきます。例えば、oのついた数が{1,2,3}の場合、暗証番号1234は問題ありませんが、1245は3が含まれていないので、除外できます。

$P$を求める手順は、最後の不要なものを除外する手順の中で、「0~9999回して、xの数字が入っていたら、抜く+oの数字が入ってないものも抜く」とすれば、不要な手順かもしれません。

解説 - AtCoder Beginner Contest 201

D - Game in Momotetsu World

Submission #22657120 - Mynavi Programming Contest 2021(AtCoder Beginner Contest 201)

ゲーム系の問題は、最終状態から逆算していくのがコツらしいです(公式解説動画から)。だいぶ難しいですが、理解した部分で説明してみます。

なお、この解説がわかりやすかったので、概ねここに沿っています。
Game in Momotetsu World [マイナビプログラミングコンテスト2021(AtCoder Beginner Contest 201) D] - はまやんはまやんはまやん

逆算して考えると、今回なら最後のマスにいったときの互いの点数差を考えたとき、その直前のマスで、取るべき行動を考えていくことになります。

  • 最後のマスが高橋の行動(最後のマスでは動けないので、そのままゲーム終了)なら、直前のマスで青木は右、下どちらに動けばゲーム展開が有利になるかを考えます。
  • 最後のマスが青木の行動(最後のマスでは動けないので、そのままゲーム終了)なら、直前のマスで高橋は右、下どちらに動けばゲーム展開が有利になるかを考えます。

より一般化して、「次のマスが青木/高橋の行動なら、直前のマスで、高橋/青木は右、下どちらに動けばゲーム展開が有利になるかを考える」ことになり、これを繰り返して、最初のマスで取るべき行動が決定します。

また、i+jの値が偶数なら、マス(i,j)は高橋の行動, 奇数なら青木の行動となります。偶奇でマスの状態が知れるのはよくある手口ですね。

上記はミニマックス法を使ってDPするという方法で実装できるようです。
つまり以下の配列を使います。

opt[i,j] : (i,j)から始めたときの高橋の点数-青木の点数の最適値

opt[i,j]を更新するときは、高橋なら上の点数差を最大化しようとし、青木なら最小化することで、自分にとってゲーム展開が有利になるようにしていきます。

ゲーム展開が有利になる(=optが自分にとって都合が良くなる方向に変化する)には、具体的には

  • 高橋のターンでは、opt[i,j] = max( opt[i+1, j] + A[i+1, j], opt[i, j+1] + A[i, j+1])としていく
  • 青木のターンでは、opt[i,j] = min( opt[i+1, j] - A[i+1, j], opt[i, j+1] - A[i, j+1])としていく

ことを意味します。Aは青マスなら+1, 赤マスなら-1が入っている配列です。もう少し書くと、

  • opt[次のマス] : 次のマスから仮にゲームを始めたとして、双方が自分の利を最大化するように動いたときの、高橋-青木の点差
  • A[次のマス] : 次のマスで自分に入る得点

なので、右と下どちらかに動いたとき、高橋なら点差が大きくなる動き方(maxをとる),青木なら小さくなる動き方(minをとる)を選ぶことを繰り返します。

もっと言い換えると、2つの移動先のマスでのoptの値から、今のマスでのoptの値をできる限り高橋なら大きく、青木なら小さくしていく方向に動けば、自分にとってゲーム展開が有利になっていくという寸法らしいです。

最終的には、opt[0,0]に「スタートから開始して、双方が自分の利を最大にする行動をとり続けたときの高橋-青木の点差」が入っているので、この正負で答えが出力されることになります。

うまく説明できた気がしない...

上に貼り付けたACのコードでは、dp(0,0)から始めるので、opt[i,j]は左上からコールして、上の更新式を求めるとき、どんどん右下に進んでいき、右下(opt(H-1, W-1)はopt=0(ここから開始してもどちらも動けない)で、そこからdp()を戻っていくような挙動を取ります。 つまり、二次元配列optは右下から左上に求まっていきます。

解説 - AtCoder Beginner Contest 201

まとめ

全然スコアが上がらなくなってきた。あとDPはやっぱり難しい。 D問題は、最初貪欲に、2手先を見たとき、+マスがたくさんある方向に今は動く、としていったんですが、手詰まりになりました。 これは類似問題を知らないとできないと思いました。