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

hamayanhamayan's blog

箱と鍵 (Boxes and Keys) [JOI 2021/2022 一次予選 (第1回) 過去問 D]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_d

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26486427

宝箱を中心に考えてみよう。
とある宝箱を開錠するためには書かれている番号と同じ番号が書かれた鍵が存在する必要がある。
よって、すべての宝箱についてループを書いて、その中で対応する鍵があるかどうかを確認しよう。
これも同様にすべての鍵についてループを書いて、存在するものがあるかどうかを探せばいい。

発展課題

今回は宝箱のループで100回のループ、鍵のループで100回のループを行ったので、全体で最大10000回のループを
行っていることになる。
鍵のループの部分はsetなどのデータ構造を使うことで、ループの回数を減らしてより高速に計算することが可能になる。
他にもソートを使ってうまくやる方法などもあるので、高速化の方法も考えてみるといいと思う。

より詳しく書くと今回の解法は計算量O(N2)であるが、O(NlogN)、O(N)まで改善ができる。
考えてみるといい。

int N, M, A[101], B[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        bool ok = false;
        for (int j = 0; j < M; j++) {
            if (A[i] == B[j]) ok = true;
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}

複雑な文字列 (Complex String) [JOI 2021/2022 一次予選 (第1回) 過去問 C]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_c

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26485238

文字種を数える問題なので、C++であればsetを使うのがオススメ。
setは同じ要素が入った場合でも1つにまとめてくれるので、全要素を入れても最終的には重複を除いた状態で格納してくれる。
なので、すべての文字をsetに入れて、中身の個数を持ってくると種類数が得られる。
これを3以上とそれ以外で答え分けをすればACできる。

int N;
string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    set<char> chars;
    for (auto c : S)
    {
        chars.insert(c);
    }

    if (3 <= chars.size()) cout << "Yes" << endl;
    else cout << "No" << endl;
}

移動 (Moving) [JOI 2021/2022 一次予選 (第1回) 過去問 B]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_b

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26485022

A地点からB地点を経由してC地点に移動するにはX+Y時間だけかかる。
判定したいのはZ時間30分以内に移動できるかということである。
ここで注意点があり、問題文をより正確に判定するのであれば、気持ちとしては「X+Y≦Z + 1/2」を判定したくなる。
コンピュータ上では小数を正確に扱うというのはやや難しく、条件判定をする際にもなるべく小数をなくす方がいい。
今回はX,Yはどちらも整数なので、X+Yも同様に整数となる。
よって、小数の1/2を考える必要はなく、「X+Y≦Z」と判定してしまって問題ない。

int X, Y, Z;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y >> Z;

    if (X + Y <= Z) cout << 1 << endl;
    else cout << 0 << endl;
}

余り (Remainder) [JOI 2021/2022 一次予選 (第1回) 過去問 A]

https://atcoder.jp/contests/joi2022yo1a/tasks/joi2022_yo1a_a

解説

https://atcoder.jp/contests/joi2022yo1a/submissions/26484859

C++では何かで割った余りを計算する場合に%という演算子を使う。
21で割った余りを求めたいなら% 21だし、10で割った余りなら% 10である。
C++以外でもこのような演算子はあるはずだ。「剰余」と言語名でgoogle検索してみよう。

もしこの問題が難しい場合は入門問題を一通りこなすのがいいと思う。
https://qiita.com/drken/items/fd4e5e3630d0f5859067#3-hello-world-----practice-contest-a-%E5%95%8F%E9%A1%8C%E3%81%AE%E3%81%BF
もし使っている言語が違う場合はこっちを参照してみよう。
https://qiita.com/drken/items/fd4e5e3630d0f5859067#c-%E4%BB%A5%E5%A4%96%E3%81%AE%E8%A8%80%E8%AA%9E%E3%81%A7

int X;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X;
    int ans = X % 21;
    cout << ans << endl;
}

Strange Lunchbox [サイシードプログラミングコンテスト2021(AtCoder Beginner Contest 219) D]

https://atcoder.jp/contests/abc219/tasks/abc219_d

前提知識

解説

https://atcoder.jp/contests/abc219/submissions/26483767

あまりピンとこないかもしれないがDPで解ける。
初手でDPが思いついて試すとできたので、DPに至る過程は説明できない…

DP

dp[i][tako][tai] := i番目の弁当まで買うかが確定していて、これまでのたい焼きの個数がtaiで、たこ焼きの個数がtakoである最小弁当個数

これで解く。重要な部分が、X,Y≦300であるという部分である。
状態として、たい焼き・たこ焼きの個数はX,Yより大きくなりうるが、X以上である個数は条件としてはすべて同一視しても問題ない。
よって、Xより大きい個数はすべてXであると丸めてしまうことにすると、たい焼き、たこ焼きの個数は0~X/Yということになる。
この前提を考えると、DPの状態数は300×300×300通りくらいになるので、状態数的にはメモリ/計算量に収まる。
これは、上限を適切に指定して丸めることで間に合うというテクであり、DPを行う上で状態を丸める良い手法である。

あとは?

後は頑張って実装するだけ。
上限を指定する場合は更新時にminを使って超えたら最大値に置き換えるという感じにすると分岐が減って見栄えがいい。

int N, X, Y;
int A[301], B[301];
int dp[301][301][301];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X >> Y;
    rep(i, 0, N) cin >> A[i] >> B[i];

    rep(i, 0, N + 1) rep(tako, 0, 301) rep(tai, 0, 301) dp[i][tako][tai] = inf;
    dp[0][0][0] = 0;
    rep(i, 0, N) rep(tako, 0, X + 1) rep(tai, 0, Y + 1) if (dp[i][tako][tai] < inf) {
        chmin(dp[i + 1][tako][tai], dp[i][tako][tai]);
        chmin(dp[i + 1][min(tako + A[i], X)][min(tai + B[i], Y)], dp[i][tako][tai] + 1);
    }

    int ans = dp[N][X][Y] < inf ? dp[N][X][Y] : -1;
    cout << ans << endl;
}

Neo-lexicographic Ordering [サイシードプログラミングコンテスト2021(AtCoder Beginner Contest 219) C]

https://atcoder.jp/contests/abc219/tasks/abc219_c

解説

https://atcoder.jp/contests/abc219/submissions/26483284

実装問題。
C++であれば、特殊なソートは、比較関数を独自に作ることで実装が可能である。

比較関数

2つの文字列が与えられたときに大小関係を判定するような比較関数を用意しよう。
通常であれば、charのまま大小比較すればそれがそのまま使えるのだが、今回は文字(文字コード)の順番と実際の順番が一致しないので、
文字を実際の順番に変換する必要がある。
自分はこれにはmapをつかって、mapping配列というのを用意した。
charを入れるとそれに対応した実際の順番が出てくるようになっている。
これを使って文字の先頭から大小比較をしていこう。

文字列のprefixがどちらも同じだった場合は文字数が少ない方が辞書順では早くなるので、
決まらなかったら文字数の昇順を条件として返してやればいい。

string X;
int N;
string S[50101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> N;
    rep(i, 0, N) cin >> S[i];
    map<char, int> mapping;
    rep(i, 0, 26) mapping[X[i]] = i;

    sort(S, S + N, [&](string a, string b) {
        int len = min(a.length(), b.length());

        rep(i, 0, len) {
            int x = mapping[a[i]];
            int y = mapping[b[i]];

            if (x != y) return x < y;
        }

        return a.length() < b.length();
    });

    rep(i, 0, N) printf("%s\n", S[i].c_str());
}

Red and Blue Tree [エクサウィザーズプログラミングコンテスト2021(AtCoder Beginner Contest 222) E]

https://atcoder.jp/contests/abc222/tasks/abc222_e

解説

https://atcoder.jp/contests/abc222/submissions/26482282

恐らく初見だとかなり難しい問題に見えると思う。

問題を簡単化する

辺の塗り方を求める問題であるが、操作によってとある辺について何回通過するかという回数については
どうなっても変化しないことが分かる。
これはとても便利な性質で、通る回数が分かれば、もともとの操作・木構造はそれほど重要でない。
よって、各辺によって、操作によって通る回数を先に求めておけば、それを赤に塗ればRがその分増えるし、
青に塗ればBが増えるという単純な事象に落とし込める。

なので、木上で通った回数分RBが増減するのではなく、単に辺について着色をした場合にRBが増減すると
もう少し問題を簡単化することにしよう。
このためには、辺を通る回数を数える必要がある。

より簡単な問題にするために辺を通る回数を数える

色々工面するかと思うが、実はDFSで比較的簡単に書ける。
DFSとだけ言われてもあまりピンとこないかもしれないが、AからBへの最短経路を求める場合にDFSを使った場合、
DFSの探索時は関係ない所への再帰で移動していくが、最終的には目的のBへ到達することができる。
到達した後に遷移元を順にたどっていくと、それがちょうど最短経路になっている。
これを利用して辺を数え上げることにする。
多分これだけ聞いてもちょっとわかりにくい。実装を見てもらうといいと思う。

エッセンスだけ再掲しておくと、AからBへの最短経路を求めたいときにDFSを使う場合、
行きに注目すると最短経路は求められないが、Bに到達した後に再帰から戻ってくる帰りの部分は丁度最短経路のみ通ってくることになる。
このようなある種のバックトラックを利用することで比較的少ない実装量で最短経路上に対して計算を行うことができる。
今回は計算量に余裕があるので、この方法でカウントしてしまおう。

残った問題は?

これで辺について何回通るかのcnt配列が計算できたことになる。
各辺について赤か青に適切に塗ることでR-B=Kを満たすような組合せを求める問題に帰着した。
mod 998244353ということもあるが、DPで解いてみよう。

dp[i][tot] := i番目の辺まで着色が終わっていてR-B=totであるような組合せ

これを解ければ、dp[N-1][K]が答えになる。
これも…実は難しい…

DPを解く

難しい点は2点ある。

  1. dp[1000][100000]で配列を取るとMLEするかも
  2. tot部分が負の数になる可能性がある

1. dp[1000][100000]で配列を取るとMLEするかも

メモリの圧縮テクを使う。今回はdp[i+1][?]の更新はdp[i][?]だけが必要でそれ以前は必要ないので、
1つ前だけを保持してDPしていくようなメモリ削減を行ったこれで、第一添え字部分が1000ではなく2で十分になるので
大幅にメモリ削減ができてMLEを回避できる。
なお、同じような実装であればメモリ使用量が少ない方が高速になる傾向がある(要出典)。
自分の実装を見てもらえば何となく何をしているかは分かると思うがもう少し細かい説明が必要な場合は
https://qiita.com/drken/items/68b8503ad4ffb469624c#%E6%B3%A8%E6%84%8F%E7%82%B92-%E3%82%88%E3%82%8A%E6%B1%8E%E7%94%A8%E7%9A%84%E3%81%AB%E4%BD%BF%E3%81%88%E3%82%8B%E3%83%A1%E3%83%A2%E3%83%AA%E7%AF%80%E7%B4%84%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF
とやってることは同じなので、見てみてるといいと思う(ここに書かれている他のテクは汎用テクで必見です)

2. tot部分が負の数になる可能性がある

C言語の配列は添え字に負の数が来ると(動くけど)めちゃくちゃになっちゃうので中心をずらして全部非負にする必要がある。
自分はいつもBASE変数として中央の数を指定して入れている。
0はdp[BASE]だし、-5はdp[-5 + BASE]だし、100はdp[100 + BASE]だしといった感じ。
なので、初期値もdp[0][BASE] = 1で、答えもdp[N-1][K + BASE]である。

int N, M, K, A[101];
vector<pair<int, int>> E[1010];
int cnt[1010];
mint dp[2][201010];
const int BASE = 100005;
//---------------------------------------------------------------------------------------------------
bool dfs(int cu, int pa, int goal) {
    if (cu == goal) return true;

    fore(p, E[cu]) if (p.first != pa) {
        bool res = dfs(p.first, cu, goal);
        if (res) {
            cnt[p.second]++;
            return true;
        }
    }

    return false;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, M) cin >> A[i];
    rep(i, 0, N - 1) {
        int u, v; cin >> u >> v;
        E[u].push_back({ v, i });
        E[v].push_back({ u, i });
    }

    rep(i, 0, M - 1) dfs(A[i], -1, A[i + 1]);

    dp[0][BASE] = 1;
    rep(i, 0, N - 1) {
        int cu = i % 2;
        int nxt = 1 - cu;
        rep(tot, 0, 201010) dp[nxt][tot] = 0;
        rep(tot, 0, 201010) if (0 < dp[cu][tot].get()) {
            dp[nxt][tot - cnt[i]] += dp[cu][tot];
            dp[nxt][tot + cnt[i]] += dp[cu][tot];
        }
    }
    cout << dp[(N - 1) % 2][K + BASE] << endl;
}