ABC197に参加しました - shu8Creamのブログ

ABC197に参加しましたので、復習のために解説を書いていこうと思います。今回は、初めて水パフォを達成しました。自分の得意な問題セットだったのが大きいですね。Cはここ最近のABC、ARCで気づけずに苦しめられたbit全探索で復習が生きた感じがします。E問題が本番中に通せませんでしたが、冷静に考察すれば気づけるレベルだったので反省点です。では、早速解説へ！

A - Rotate
B - Visibility
C - ORXOR
D - Opposite
感想

A - Rotate

問題概要

タイトルの通り文字列をrotateする。先頭文字を末尾へrotate

制約

文字列は3文字

解法

一番何も考えなくていいのは、s[1], s[2], s[0]の順に出力するだけ。 C++を使っている方はrotate関数があります。（他言語は各自お調べください）

rotate(先頭, 先頭に持ってきたい要素のイテレータ, 後ろ)で書けます。つまり、

rotate(s.begin(), s.begin()+1, s.end())

こう書けます。僕もrotateの存在を知ったのは結構遅かったので知っておくと良いかもしれません。 stringだけでなく、vectorなどでも使えます。

B - Visibility

問題概要

$H*W$ のグリッドマスで位置 $(X,Y)$ から見えるのは何マス？

制約

$H, W \leq 100$

解法

今いる位置 $(X,Y)$ から上下左右を壁にぶつかるか、障害物#にぶつかるまで数える。制約が緩いので各方向にfor文を回せば終了です。

この問題自体は簡単ですが、似たようなシチュエーションで難しい問題がたくさん出題されています。この機会に復習、解いたことのない人はチャレンジしましょう。（diffは緑以上、難易度順です）

atcoder.jp

C - ORXOR

問題概要

長さ $N$ の数列 $A$ をいくつかの区間にわけ、区間内でORを取り、ORを取った区間値をXORを取る。上手く分けてできるだけ最終値を小さくする。

制約

$1 \leq N \leq 20$

解法

制約から見て数列の間に仕切りを入れるか入れないかをbitで管理できそうというのが思いつきます。 bit列の長さは、植木算的に考えて19です。 $2^{19}$ が全探索できるか不安な方はpythonとかをサッと立ち上げて計算すると十分間に合うことがわかります。全探索中に数列を一回舐めるので計算量は $O(2^{N-1}N)$ 。意外と実装でミスるところが多かったのかもしれません。（僕はintにしてWAをもらいました...）

ll ans = 5e18;
rep(s,1<<(n-1)){
    vector<ll> tmp;
    ll c = a[0];
    rep(i,n-1){
        if(s>>i&1){
            tmp.push_back(c);
            c = a[i+1];
        }else{
            c|=a[i+1];
        }
    }
    tmp.push_back(c); // これ忘れがち
    ll res = 0;
    rep(i,tmp.size()){
        res^=tmp[i];
    }
    ans=min(ans,res);
}
cout << ans << endl;

これが緑diffは意外でした。最近bit全探索の問題多いので気づいた人も多いと思うのですが。 bit演算（OR演算、XOR演算など）を初めて知った方はいい機会なので勉強しましょう。わかりやすい記事です。僕もお世話になっています。

ビット演算 (bit 演算) の使い方を総特集！〜マスクビットから bit DP まで〜 - Qiita

D - Opposite

問題概要

正N角形の頂点 $(x_0, y_0), (x_{N/2}, y_{N/2})$ （順番は反時計回り）が与えられるので $(x_1, y_1)$ の値を求める。

制約

$N$ は偶数入力値は全て整数

解法

ABCでは珍しい幾何の問題ですね。頂点 $(x_0, y_0), (x_{N/2}, y_{N/2})$ が与えられている時点でめちゃめちゃ正多角形の中心を求めたくなります。ここら辺はわからない時は図を書くことが大切です。中心から $(x_0, y_0)$ を回転すれば $(x_1, y_1)$ が求まります。回転角は $\theta = 2\pi/N$ です。回転の仕方は色々ありますが、ここら辺は完全に数学の知識なので数学苦手な人はきつかったのかもしれません。

回転１

行列の知識があれば回転行列で操作できます。

こういう式になるのですが、注意点としてこの式多角形の中心点が原点と一致する時にしか使えません。じゃあどうすんだよってなるかもしれませんが、一回中心点を原点に平行移動して回転させた後に元の位置に戻せばいいです。以下の図の通りです。

$x_0 = x_0 - x_m, y_0 = y_0 - y_m$ と事前にしておき（ $x_m, y_m$ は多角形の中心点）行列を全部展開すると $x_1 = x_0 cos\theta - y_0 sin\theta, y_1 = x_0 sin\theta + y_0 cos\theta$ これを最後元に位置に戻すために $x_1 = x_1 + x_m, y_1 = y_1 + y_m$ とすればおしまいです。

回転２ 複素数平面に多角形が載っていると考えます。複素数平面上だと回転を考えるのが楽だったり便利なことが色々あります。ただ複素数平面自体が数IIIの範囲なのでガチガチの理系じゃないと履修してないかもしれません。（昔は複素平面と呼んでいたそう）文系プログラマの方も多いと思うので知らない方は勉強するのも良いかもしれません。コードに落とし込むのはこちらの方が楽な気がします。 pythonの記法ができると断然こっちが楽ですね

こちらの解説は気が向けば追加します。

感想

今回の問題セットは得意不得意が人によってはっきり出てしまう回だったみたいです。不得意部分がはっきり見えた方は今後対策しやすいかもしれません。個人的には爆速35分で4完できて満足です。関係ないですが、段々とはてなブログのtex記法もコツを掴んできました。また、解説を書くのでよろしくお願いします。