はまやんはまやんはまやん

hamayanhamayan's blog

Number of Amidakuji [AtCoder Beginner Contest 113 D]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_d

解説

https://beta.atcoder.jp/contests/abc113/submissions/3558659

dpで解く。
1,2,3,...,W本目ではなく、0,1,2,...,W-1本目と考えて解く。
dp[h][k] := 高さhまであみだくじを構築していて、0本目の縦棒がk本目に遷移する組み合わせ
0本目がどこに遷移したかだけが関係あるので、他の縦棒の遷移先については抽象化できる。
dpの遷移が難しいポイントであるが、高さhの地点で作れるあみだくじについて全列挙していこう。

まず、W本あるなら、間はW-1本ある。
この間について線を引く、線を引かないの2通りがあり、2^(W-1)通りがある。
これを全列挙するのに、rep(msk, 0, 1 << (W - 1))のようにして書く。
これで0,1の全列挙ができた。
これで大体の条件は満たせているが、「どの2つの横棒も端点を共有しない」という条件を満たせてないため、
check関数で満たしているかチェックしよう。
 
これでvalidな線引ができたため、0本目がk本目に遷移している場合なら、

  • k番目に線がある→k本目からk+1本目へ
  • k-1番目に線がある→k本目からk-1本目へ
  • どちらも無い→k本目からk本目へ

遷移するので、これで遷移式を書く。

int H, W, K;
mint dp[101][8];
//---------------------------------------------------------------------------------------------------
int check(int msk) {
    rep(i, 0, W - 2) {
        int a = (msk >> i) & 1;
        int b = (msk >> (i + 1)) & 1;
        if (a and b) return 0;
    }
    return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    K--;
 
    dp[0][0] = 1;
    rep(h, 0, H) rep(k, 0, W) rep(msk, 0, 1 << (W - 1)) if (check(msk)) {
        if (msk & (1 << k)) dp[h + 1][k + 1] += dp[h][k];
        else if (0 < k and msk & (1 << (k - 1))) dp[h + 1][k - 1] += dp[h][k];
        else dp[h + 1][k] += dp[h][k];
    }
 
    cout << dp[H][K] << endl;
}

ID [AtCoder Beginner Contest 113 C]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_c

解説

https://beta.atcoder.jp/contests/abc113/submissions/3558586

流れは以下の通り。
1. 県ごとに市を分ける
2. 県ごとに市の誕生年でソートし、順番に認識番号を作る
3. 最後に順番に答えていく
 
流れ1
E[i] := 県iに属する市 (誕生年, 市の番号)
を作る。
 
流れ2
iについて全探索する。
まず、E[i]でソートすると、pairの一番目でまずはソートされるので、誕生年でソートされる。
あとは、順番に市の番号について、認識番号を作って、ans配列に格納していく
 
流れ3
ans配列を順番に答える

int N, M;
vector<pair<int,int>> E[101010];
string ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int p, y; cin >> p >> y;
        E[p].push_back({ y, i });
    }
    rep(i, 1, N + 1) {
        sort(all(E[i]));
        int n = E[i].size();
        rep(j, 0, n) {
            char buf[13];
            sprintf(buf, "%06d%06d", i, j + 1);
            ans[E[i][j].second] = string(buf);
        }
    }
    rep(i, 0, M) printf("%s\n", ans[i].c_str());
}

Palace [AtCoder Beginner Contest 113 B]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_b

解説

https://beta.atcoder.jp/contests/abc113/submissions/3558578

温度がT-H[i]*0.006であり、小数になる可能性があるので、doubleで計算していこう。
全ての高さについて全探索しよう。
温度差はabs(A-t)で求められる。
これまでの温度差の最小値dminを保持しておき、その時の添字も保持しておくと、答えが出せる。

int N, T, A, H[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> T >> A;
    rep(i, 0, N) cin >> H[i];
 
    double dmin = 1e9, ans = -1;
    rep(i, 0, N) {
        double t = T - H[i] * 0.006;
        double d = abs(A - t);
        if (d < dmin) {
            dmin = d;
            ans = i;
        }
    }
    cout << (ans + 1) << endl;
}

Discount Fare [AtCoder Beginner Contest 113 A]

https://beta.atcoder.jp/contests/abc113/tasks/abc113_a

解説

https://beta.atcoder.jp/contests/abc113/submissions/3558553

答えはX+Y/2になる。
計算して求めよう。
今回の問題では大丈夫だが、整数の割り算をするときは小数点以下切り捨てになることを頭に入れておこう。

int X, Y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y;
    int ans = X + Y / 2;
    cout << ans << endl;
}

Align [Tenka1 Programmer Contest C]

https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_c

解説

https://beta.atcoder.jp/contests/tenka1-2018/submissions/3509652

構築問題。
最適な構築を考えてみる。
今回は400点問題なので、なるべく簡単に構築できるように考える。
 
絶対値というのは扱いづらいので、大きい方-小さい方として考える。
すると、ある要素は、大きい方として2回使われるか、大きい方・小さい方として1回ずつか、小さい方として2回使われるかの三択になる。
よって、大きい方なら+2, 1回ずつなら0, 小さい方なら-2となる。
端は+1か-1になる。
 
これで考えると+2になるのはなるべく大きい数にしたい。

  • 2になるのはなるべく小さい数にしたい。

よって、方針として、半分にして、小さいグループと大きいグループを交互に配置していくのがいい。
Nが偶数なら、大小…大小の一択。
Nが奇数なら、大小…大小大か小大…小大小の二択の良い方が答え。
どちらも、端が+1,-1になるので、大+1の部分はなるべく小さい数を採用し、小-1はなるべく大きい値を採用する。

int N, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
ll get() {
    ll sm = 0;
    rep(i, 0, N - 1) sm += abs(B[i + 1] - B[i]);
    return sm;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
 
    ll ans = -1;
    if (N % 2 == 0) {
        rep(i, 0, N / 2) B[i * 2 + 1] = A[i];
        rep(i, 0, N / 2) B[i * 2] = A[i + N / 2];
        ans = get();
    } else {
        rep(i, 0, N / 2) B[i * 2 + 1] = A[i];
        B[N-1] = A[N/2];
        rep(i, 0, N / 2) B[i * 2] = A[i + N / 2 + 1];
        chmax(ans, get());
 
        B[0] = A[N / 2];
        rep(i, 0, N / 2) B[i * 2 + 2] = A[i];
        rep(i, 0, N / 2) B[i * 2 + 1] = A[i + N / 2 + 1];
        chmax(ans, get());
    }
    
    cout << ans << endl;
}

Exchange [Tenka1 Programmer Beginner Contest B]

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b

解説

https://beta.atcoder.jp/contests/tenka1-2018-beginner/submissions/3509545

シミュレートしよう。

int A, B, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> K;
    rep(i, 0, K) {
        if (i % 2 == 0) {
            if (A % 2 == 1) A--;
            B += A / 2;
            A /= 2;
        } else {
            if (B % 2 == 1) B--;
            A += B / 2;
            B /= 2;
        }
    }
    cout << A << " " << B << endl;
}

Measure [Tenka1 Programmer Beginner Contest A]

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_a

解説

https://beta.atcoder.jp/contests/tenka1-2018-beginner/submissions/3509515

S =3のときの最初と最後をスワップ処理を書いて、Sを出力しよう。

C++であればswap関数を使えばだいたいのものは高速にswapできる。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    if (S.length() == 3) swap(S[0], S[2]);
    cout << S << endl;
}