AtCoder ABC197

ABC197参加しました。

atcoder.jp

A - Rotate

文字列sを読み込んで、s[1] + s[2] +s[0]するだけ

解説 - AtCoder Beginner Contest 197

B - Visibility

以下のような入力を例にして考えてみます。 二重丸の位置が(X,Y)の位置とします。空白に'.'があると思ってください。 そこから上下左右に'.'のマスを、#に当たるまで数えます。 開始位置を重複して数えたりしないようにしましょう。

ABC197B

解説 - AtCoder Beginner Contest 197

C - ORXOR

bit全探索問題です。 bit全探索はビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita が詳しかったです。

今回の場合は、$ A_i $を横一列に並べて、各$ A_i $ の間にしきいを入れて区間を作ります。

ABC197C

上の図で、^が書かれている部分に敷居（0か1)を入れます。1は敷居が立っています。 なお、端は必ず敷居が入るので1です。

例えば以下の場合は、区間は[$ A_0, A_1$ ],[$A_2$]になります

ABC197C-例

この敷居が立つか立たないかをbit全探索します。探索の最大回数は、敷居の数になりますが、今回だと、両端が1で固定なので、最大でも $ 2^{19} = 524288 $ となり、十分間に合います。

bit全探索はなれるまでちょっとコードを書くのが大変です。 決まった区間のORの値は配列に入れておきます。

for (int bit = 0; bit < (1 << n - 1); ++bit)
{
    //今のしきいの位置
    int th = 0;//初期値は現在の右端。初期値は最右端(A0の右)
    for (int i = 0; i <= n - 1; ++i)
    {
        //iはA[i-1], A[i]の間の敷居
        if ((bit & (1 << i)) != 0)
        {
             //[th, i+1]までが区間なので、この区間の数値のORを取る

              //区間の右端を更新
              th = i + 1;
        }
    }
    //最後の区間[th, 最左端]の計算

    //各区間のXORを取る

    ans = Math.Min(ans, /*XOR結果*/);//答えをメモ
}

解説 - AtCoder Beginner Contest 197

D - Opposite

CGを勉強していたり、高校数学で行列の勉強をしていたら、回転行列について習ったかもしれませんが、今回はそれの練習問題みたいな感じでした。

各点は$ p_0, p_{N/2}$を結ぶ直線の中心位置$ p_c$を円の原点とした円周上に存在します。 また、点は正$N$角形なので、等間隔に配置されているため、$ \angle p_i p_c p_{i+1}$の値はすべて等しいです。

よって、$ p_0$ から一定角度($ 360/ N$ )だけ、$ p_c $を中心に回転させることで、$ p_1 $が出てきます。

回転行列はそのままだと原点(0,0)中心の回転なので、$ p_0 $が乗る円を原点まで並行移動(=$ p_c $を原点まで移動)して、回転を適用、最後に原点への平行移動分を取り消すように移動させないといけません。

以下がわかりやすかったです。
Opposite [AtCoder Beginner Contest 197（Sponsored by Panasonic） D] - はまやんはまやんはまやん

解説 - AtCoder Beginner Contest 197

まとめ

実装がめんどくさかった問題が多いですね。幾何のライブラリを作るべきか悩みます。