ABC197 振り返りメモ(D問題まで)

#結果
ABDの3完で, レート変化は704→729(+25)

#A問題 ( Rotate )
###概要

3文字の文字列Sの, 先頭の文字を末尾に持っていったときにできる文字列を出力せよ.

###方針
問題の通りにやる.
汎用的な解法として, rotate関数を使うものもある.

C++ での実装例は以下のようになる.

a.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    cout << S[1] << S[2] << S[0] << endl;
    return 0;
} 

#B問題 ( Visibility )
###概要

障害物ありの二次元平面で, 与えられた位置の上下左右方向にある障害物 ( または壁 )までの距離の合計を求める.

方針

上下左右, 全ての方向に対して障害物までの距離を数えていけば良い.
似たような操作を4回行わなくても良いように工夫すると, 下のような実装になる.

b.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

ll dx[] = {-1, 0, 1, 0};
ll dy[] = {0, -1, 0, 1};

int main() {
    ll H, W, X, Y;
    cin >> H >> W >> X >> Y;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    X--; Y--;
    ll ans = 1;
    rep(i, 4) {
        ll x = X;
        ll y = Y;
        while (1) {
            x += dx[i];
            y += dy[i];
            if (x >= H || y >= W || x < 0 || y < 0) break;
            if (S[x][y] == '#') break;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
} 

#C問題 ( ORXOR )
###概要

略

方針

N 個の要素間の間に仕切りを置くか置かないかを全通り探索する.
N 個の要素間は N - 1 個あるので, 全部で 2 ^ ( N - 1 ) 通り探索しないといけない.
2の累乗数通り探索する場合, bit全探索をすると良い.
そして, 仕切りを置くタイミングで, XOR を更新する.
最後に XOR を更新するのも忘れないようにする.

C++ での実装例は以下のようになる.

c.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (long long i = 0; i < (n); i++)
using ll = long long;

const ll LINF = (1LL << 60) - 1;

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll ans = LINF;
    for (ll bit = 0; bit < (1 << n-1); bit++) {
        ll now = 0;
        ll o = 0;
        for (ll i = 0; i < n; i++) {
            o |= a[i];
            if (bit & (1 << i)) {
                now ^= o;
                o = 0;
            }
        }
        now ^= o;
        ans = min(ans, now);
    }
    cout << ans << endl;
    return 0;
} 

#D問題 ( Opposite )
###概要

正n角形の頂点の1つ(p.0)の座標と, その反対側にある頂点(p.2/n)の座標が与えられるので, p1 の座標を計算する.

方針

複素数を用いて計算すると簡単である.
以下の図のようになるので, 中点に当たる複素数を mid とすると, mid + (p0 - mid) * ( cos(2π/n), sin(2π/n) )　を計算すれば良いことが分かる.

C++ での実装例は以下のようになる.

d.dpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

using C = complex<double>; // 追加
const double PI = acos(-1);

int main() {
    ll n; cin >> n;
    double x, y, x_, y_;
    cin >> x >> y >> x_ >> y_;
    C s = C(x, y);
    C t = C(x_, y_);
    C mid = (s + t) / 2.0;
    double rad = 2 * PI / n;
    C r(cos(rad), sin(rad));
    C ans = mid + (s - mid) * r;
    cout << fixed << std::setprecision(15) << ans.real() << endl;
    cout << fixed << std::setprecision(15) << ans.imag() << endl;
    return 0;
}