デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

5完3WA。いろいろやらかしてしまいました。

各問題

A - Horizon

与えられた式を計算するだけです。

B - Integer Division

与えられた式を計算するだけです2。

言語によって対応が変わりますが、c++なら負数のときは切り上げ除算的なことをする必要があります。具体的には(X - 9) / 10とします。

C - Knight Fork

親切にも図を用意してくれている通り、ある格子点から距離√5の格子点は8つしかないので、両方の点についてその8つの点の座標を求めて一致するものがあるかどうか全探索します。

D - Prime Sum Game

あらかじめ200までの数字が素数であるかどうかをエラトステネスのふるいなどを使って求めておきます。

すると全探索可能になります。

D問題のわりにはゆるすぎて提出を躊躇してしまいました...。

E - Subtree K-th Max

DFSで、帰りがけにDの値を積んでいくと、いい感じに部分木についてのDの値の配列が作れます。

一見計算量がたらなさそうに見えますが、Kが20以下なので都度20までに長さをカットしていけば大丈夫です。

各頂点について配列が作れさえすれば、クエリ一つにつきO(1)で、全体でO(Q)で答えることができます。

F - Construct Highway

制約より、木を作る問題であることがわかり、閉路ができてはいけないことがわかります。

しかし、構築方法は最後までわかりませんでした。

まとめ

EでK<=20の制約を見落として、無理と判断してFを先に考えて結局解けずにEに戻ったため結構なロスをしてしまいました。

まあEを考え続けていても水パフォあったかどうかは微妙なので、今日はダメでした。

AtCoder Regular Contest 135

1完1WA。

各問題

A - Floor, Ceil - Decomposition

Writerがmaspyさんなので、メモ化再帰を投げれば通ると信じて投げると通ります。

まあどんどん半分にしていく過程で黒板に書かれる数字はとても多くなりますが、種類は多くないので。

実は最初に愚直解を投げて1WAもらっていてダメ。投げる前に10¹⁸でテストしろとあれほど・・・。

B - Sum of Three Terms

S_{i} - S_{i+1} = A_{i} - A_{i+3} にはたどり着くも、そこからがわからず・・・。

C - XOR to All

前から決めていけばいいのかと思いきや、後ろに波及するためどうしていいかわからず・・・。

終了後のTwitterにたかだか1回とかたくさん流れてきて、うそーと思いながら公式解説2回読み直してようやく理解・・・。

まとめ

大体負荷コンテストのせい。（うそ

数学ですね。

deprecatedとobsoleteの違い

毎回ググってるような気がするのでここに書き記しておくシリーズその4。

原義

引用は Longman Dictionary of Contemporary English | LDOCE より

deprecate

to strongly disapprove of or criticize something

強く不承認だったり批判するという意味。

obsolete

no longer useful, because something newer and better has been invented → out-of-date

より新しいものやよりよいものがあるのですでに使われない、つまり期限切れという意味。

つまり

obsoleteの方はまさに期限切れという意味なのに対して、deprecateの方には期限切れだからという意味合いは特になさそう。

モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）

4完2WA。

各問題

A - Exponential or Quadratic

n=2, 3, 4では2ⁿの方が小さいですが、2ⁿが指数関数ですぐ爆発するのでnが5以上では常に2ⁿの方が大きくなります。

ところで、n=1のときは2¹=2と1*1=1なので2ⁿの方が大きいです。

見事に引っかかり1WAと、慌てて条件を追加したためandとorを間違えてさらに1WA・・・。ここでペナ込み18分を費やしています。大ピンチ。

（追記：よく見たらBを先に通していたのでそれほどでもなかった・・・）

B - Pizza

0、360およびA_i%360を昇順にならべると、隣接する項の差分が欲しい角度なので、全部チェックすればよいです。

C - digitnum

1桁の合計はf(1)=1からf(9)=9までの和、2桁の合計はf(10)=1からf(99)=90までの和、3桁の合計はf(100)=1からf(999)=900までの和、という具合になってます。

最上位の桁以外は上記の計算をして、最上位の桁はいくつあるか計算（例えば例2の238なら238-99で139個ある）して、そこまでの和を求めればよいです。

D - AND and SUM

まず、ANDを作るためにはaで立っているビットがx, yともに立っている必要があるため、少なくとも和はa2以上です。s < a2ならこの時点で"No"とわかります。

s >= a*2の場合、残りのs - a*2で立っているビットを、xかyの「いずれか片方」に振り分ける必要があります。両方に振ってしまうとANDが変わるのでだめですし、振り分けない場合sが作れなくなるのでそれもだめです。

ここで、s - a*2で立っているビットがすでにaで立っていた場合、振り分けられないので"No"です。すべてを振り分けることができれば"Yes"です。

E - Range Sums

そもそもどういう条件でうまく行くのかが証明できずじまいで、適当に再帰を書いて投げるももちろんだめでした。

まとめ

A問題でめちゃくちゃはまってしまい、今日はもうだめかと思いましたが、C、Dでかなり挽回できたようでなんとか水パフォ中位をキープとなりました。

D. Make Them Equal (Educational Codeforces Round 122 Div. 2)

問題

https://codeforces.com/contest/1633/problem/D

問題概要

長さnですべての要素が1の配列 a が与えられる。配列aの要素に対して、a_i = a_i + a_i / x (x > 0) という操作が最大 k 回実行可能である。

長さnの配列bとcがあり、上記の操作で a_i == b_i とできた場合、c_i枚のコインを獲得することができる。

最大何枚のコインを獲得できるか答えよ。

考察

1から各bまでの距離がわかれば、その距離を重さ、コインを価値としたナップサック問題とみなすことができます。

ここで

• bまでの距離をどうやって効率良く求めるか？
• kが10⁶なので間に合わない？

の2点が問題となります。

bまでの距離をどうやって効率良く求めるか？

bはたかだか1000なので、BFSなりメモ化再帰なりで求めることが可能です。これを事前に計算しておけばよいです。

このパートだけ切り取れば、AtCoder Beginner ContestのCかD問題で出てきそうなレベルの問題かと思います。

kが10⁶なので間に合わない？

前計算の結果を確認すると、1000までのいずれかに対する距離はたかだか12であることがわかります。nは10³なので、距離の合計の最大値は最悪でも12000です。よって、ナップサックDPで解くことが可能です。

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

const int INF = 1001001001;

int main() {

    // 先に1000までの距離を求める
    vector<int> a(1001, INF);

    function<void(int, int)> rec = [&](int m, int u) {
        if (m > 1000) return;
        if (a[m] <= u) return;
        a[m] = u;

        for (int x = 1; x <= m; x++) {
            rec(m + m / x, u + 1);
        }
    };

    rec(1, 0);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> b(n);
        vector<int> c(n);
        int mx = 0;
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            mx += a[b[i]];
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> c[i];
            sum += c[i];
        }

        // 距離の合計が k 以下なら全てのコインが取得可能
        if (mx <= k) {
            cout << sum << endl;
            continue;
        }

        vector<vector<int>> dp(n + 1, vector<int>(k + 1, -INF));
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                if (dp[i][j] == -INF) continue;
                if (dp[i + 1][j] < dp[i][j]) dp[i + 1][j] = dp[i][j];
                if (j + a[b[i]] <= k) {
                    if (dp[i + 1][j + a[b[i]]] < dp[i][j] + c[i]) dp[i + 1][j + a[b[i]]] = dp[i][j] + c[i];
                }
            }
        }
        int ans = 0;
        for (int j = 0; j <= k; j++) {
            if (ans < dp[n][j]) ans = dp[n][j];
        }
        cout << ans << endl;
    }
    return 0;
}

AtCoder Beginner Contest 237

4完2WA。

各問題

A - Not Overflow

書いてあるとおりに比較しましょう。入力が32bitで収まらないことに注意。

B - Matrix Transposition

vector<vector<int>> v(h, vector<int>(w));
for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        cin >> v[i][j];
    }
}

とするところを

vector<vector<int>> v(w, vector<int>(h));
for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        cin >> v[j][i];
    }
}

とします。

C - kasaka

まずそのものが回文かどうかをチェックします。回文ならもちろん"Yes"でおわりです。

回分でなければ、両端のaを数えて先頭のaの数が末尾のaの数より多ければ構築不可能なので"No"です。そうでなければ、両端のaを除去した後の文字列が回分になっているかを調べます。

無駄な処理をしまくって2WA・・・。

D - LR insertion

dequeにNを置き、文字列は後ろから見て、Lなら末尾（右）にRなら先頭（左）に数字をN - 1から順に0までおいていけばOKです。

E - Skiing

負の辺が生まれるので、げたを履かせてダイクストラをやったんですが、3割ほどWAが出て修正できず終了。

というか混乱しててダイクストラ法の使い方を間違っていたような気がします・・・。

まとめ

うーん、ダイクストラってわかってるのに通しきれないの厳しいですね・・・。

AtCoder Regular Contest 134

2完1WA。

各問題

A - Bridge and Sheets

愚直にシミュレートするだけです。切り上げ除算に気をつけるくらいでしょうか。

B - Reserve or Reverse

'a'から順に貪欲に変換していくだけです。すでに変換した範囲の外側は考慮対象外になることだけ注意。

初手は見当違いの考察をして1WA。そこから軌道修正できたのはえらかった。

C - The Majority

見当もつかない数え上げだったので、すぐにパス。

Twitterで流れてきた解法を見ましたが、天才かと思いました。（1を1つずつ敷き詰め -> 1と1以外をペアにして任意の場所に置く方法を数える -> 余った1を置く方法を数える）

D - Concatenate Subsequences

こちらに特攻しましたが、ACが80/95までしか取れずあえなく玉砕。

前半の値 -> 後半の値でソートして前から置けるものを置く、としましたがだめでした。

まとめ

惨敗かと思いましたが、レートはほぼ横ばいで済んだ・・・。増分0と+1は2回ずつありますが、-1は初でした。