SolveMe (AOJ 2378)

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 25 日目の記事です。

問題リンク

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2378 (1200+ 点)

問題概要

集合 $S={0,1,\ldots,N-1}$ にたいして、 $S\to S$ の写像 $f,g$ を考える。 $(f,g)$ の組であって、$f ^ X g f ^Y g f ^Z$ が恒等写像となるものは何通りあるか、$1000000007$ で割ったあまりを求めよ。

制約

$1 \leq N_A,N_B \leq 1000$
$ |X|,|Y|,|Z|\leq 10 ^ {18}$
入力は全て整数

解法

$X=Y=Z=0$ のときはコーナーケースなので別途処理します。そうでない場合、$f,g$ は全単射であることが要請されます。式変形により、

$$(f ^ Y g) ^ 2 = f ^{(Y-X-Z)} $$

を満たす $(f,g)$ を数え上げればよいです。適切に置きなおし、$Y-X-Z<0$ のときは逆写像を考えることで、条件は

$$f ^ 2 = g ^{K}\ (K = |Y-X-Z|) $$

と表せます。

直接 $(f,g)$ を数え上げるのは難しいので、一工夫します。$h=f ^2 (=g ^ K)$ と置き、$h$ すべてに対して、($f ^ 2=h$ なる $f$ の個数) $\times$ ($g ^K=h$ なる $f$ の個数) を求め、足し合わせたものが答えと一致するので、そちらを数え上げます。

まずは、$h$ についてです。写像 $f$ はいくつかのサイクルに分解されますが、これを $k$ 乗すると、長さ $N$ のサイクル $1$ 個は長さ $N/\mathrm{gcd}(k,N)$ のサイクル $\mathrm{gcd}(k,N)$ 個になることがわかります。

なので、まず $h$ に含まれる長さ $i$ のサイクルの個数を決め打ち、次にそれを生成する $f,g$ の個数を掛け合わせていけばよいです。前者は単純な動的計画法で出来ます。

後者についてです。長さ $i$ のサイクルが $j$ 個あるとき、それを生成する方法を求めればよいですが、これも同様の動的計画法で出来ます。

ただし、複数のサイクルを組み合わせて一つのサイクルを作るとき、サイクルを組み合わせる順番、組み合わせる際のオフセット、などやや丁寧に考えるべき点が多いです。自分はオフセットの考慮を忘れていて無限に困っていました。

サンプルが弱いこともあり、デバッグがそのままでは大変しづらいので、愚直テストを書くのが有効な問題だと思いました。

実装例 (c++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep(i, x)    for(int i = 0; i < (x); i++)
#define rng(i, l, r) for(int i = (l); i < (r); i++)
#define sz(v)        (int)(v).size()
#define all(v)       (v).begin(), (v).end()

constexpr int mod = 1000000007;
struct mint {
    ll v;
    mint(ll x = 0) {
        v = x;
        v %= mod;
        if(v < 0) v += mod;
    }
    mint operator+(mint o) { return v + o.v; }
    mint operator-(mint o) { return v - o.v; }
    mint operator*(mint o) { return v * o.v; }
    mint pow(ll k) {
        assert(k >= 0);
        mint ret = 1, a = v;
        while(k) {
            if(k & 1) ret = ret * a;
            a = a * a;
            k >>= 1;
        }
        return ret;
    }
    mint inv() { return pow(mod - 2); }
    mint operator/(mint o) { return v * o.inv().v; }
};

vector<mint> fac, finv;

void init(int n) {
    fac.resize(n + 1);
    finv.resize(n + 1);
    fac[0] = finv[0] = 1;
    rep(i, n) fac[i + 1] = fac[i] * (i + 1);
    finv[n] = fac[n].inv();
    for(int i = n - 1; i >= 1; i--) finv[i] = finv[i + 1] * (i + 1);
}
mint binom(int n, int k) {
    if(min(n, k) < 0 or n < k) return 0;
    return fac[n] * finv[k] * finv[n - k];
}

int main() {
    int n;
    ll X, Y, Z;
    cin >> n >> X >> Y >> Z;

    if(X == 0 and Y == 0 and Z == 0) {
        vector<mint> a{1, 1};
        rng(i, 2, n + 1) a.push_back(a[i - 1] + a[i - 2] * (i - 1));
        cout << (a[n] * mint(n).pow(n)).v << endl;
        return 0;
    }

    init(1000);
    ll k = abs(Y - X - Z);

    //  (i = j / gcd(j, k)) * gcd(j, k)
    auto make_table = [&](ll x) {
        vector table(n + 1, vector(n + 1, mint(0)));
        rng(i, 1, n + 1) {
            vi tmp;
            rng(j, 1, n + 1) {
                if(j / gcd(j, x) != i) continue;
                tmp.push_back(gcd(j, x));
            }
            if(tmp.empty()) continue;
            int m = sz(tmp);
            // j個のグループを、tmp[k]以下を使って分配する個数
            vector dp(m + 1, vector(n / i + 1, mint(0)));
            dp[0][0] = 1;
            rep(id, m) {
                mint pw = mint(i).pow(tmp[id] - 1);
                rep(j, n / i + 1) {
                    mint tar = 1;
                    for(int u = 0; u * tmp[id] <= j; u++) {
                        dp[id + 1][j] = dp[id + 1][j] + dp[id][j - u * tmp[id]] * tar * finv[u];
                        tar = tar * binom(j - u * tmp[id], tmp[id]) * fac[tmp[id] - 1] * pw;
                    }
                }
            }
            rep(j, n / i + 1) table[i][j] = dp.back()[j];
        }
        return table;
    };

    auto lt = make_table(2);
    auto rt = make_table(k);


    vector dp(n + 1, vector(n + 1, mint(0)));
    dp[0][n] = 1;
    rng(i, 1, n + 1) {
        rep(j, n + 1) {
            dp[i][j] = dp[i][j] + dp[i - 1][j];
            //完成形のグループを決め打つ
            //それを適切に分配する
            mint cur = 1;
            for(int u = 1; u * i <= j; u++) {
                cur = cur * binom(j - i * (u - 1), i) * fac[i - 1];
                mint tar = cur / fac[u];
                mint lef = lt[i][u], rig = rt[i][u];
                dp[i][j - u * i] = dp[i][j - u * i] + dp[i - 1][j] * tar * lef * rig;
            }
        }
    }
    cout << dp[n][0].v << endl;
}

感想

近年の数え上げのインフレ？もあり、1200+ にしてはかなり解きやすいように感じました。ただ、正確な数え上げを要求されることもあり、中々芯のある問題で面白かったです。

2022-12-11

ねこ鍋改造計画（仮） (AOJ 2337)

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 12 日目の記事です。

問題リンク

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2337 (1000 点)

問題概要

$N_a$ 匹のオスのネコ、 $N_b$ 匹のメスのネコがいて、各猫には固有の重さとかわいさが定まっている。

重さの和が $W$ を超えないようにオスのネコを $1$ 匹以上選ぶ。メスのネコについても同様に選ぶ。このとき、$\mathrm{max}( |$選んだオスのネコの重さの和 - 選んだメスのネコの重さの和$|,$ 選んだネコの可愛さの最大値 - 選んだネコの可愛さの最小値$)$ を最小化せよ。

制約

$1 \leq N_A,N_B \leq 500$
$1 \leq W \leq 10^ 4 $
$1 \leq$ 各ネコの重さ $ \leq 10^ 4 $
$1 \leq$ 各ネコのかわいさ $ \leq 10^ 9 $

解法

まず、重さが $W$ より大きいネコが入力に含まれうる（非本質。。）のでそのようなネコを捨てます。

次に、目的関数の第二項、すなわち (選んだネコの可愛さの最大値 - 選んだネコの可愛さの最小値) の取り得る最小値を求めます。これは適当に全探索しても十分間に合いますし、ソートすればより高速です。

第二項の最小値が $W-1$ 以上のとき、第一項は $W-1$ 以下であることからそれを答えとして出力すればよいです。

以下そうでない場合を解きます。最大値の最小化なので二分探索をします。答えを $x$ 以下に出来るかという判定問題について考えます。

愚直な解法として、ネコの可愛さの最小値を決め打つと、使えるネコの集合が決まるので、部分和問題を解くことで判定問題に答えられます。しかしこの解法は $\mathrm{O}(N ^ 2 W) $ かかります。(昔の問題なので bitset 高速化でこの解法も通ってしまうようです)

ここではより計算量のよい解法で解きます。ネコをかわいさでソートしておき、尺取り法のように部分和 DP を更新することを考えます。この際、使えなくなったネコによる遷移を打ち消す（戻す DP)必要性が生じます。

「部分集合であって重さ w を達成できるか？」という bool を管理する DP は戻すことが難しいですが、 boolを持つのでなく、かわりに「部分集合であって重さ w を達成できるものは何通りか $\text{mod}$ 適当な数」という個数を管理する DP にすることで、戻す DP が可能となり尺取り法のような DP 更新が可能となります。

以上でこの問題を $\mathrm{O}(NW \log W) $ で解くことが出来ました。

実装例 (c++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, x)    for(int i = 0; i < (x); i++)
#define rng(i, l, r) for(int i = (l); i < (r); i++)
#define sz(v)        (int)(v).size()
#define all(v)       (v).begin(), (v).end()

constexpr int mod = 1000000007;
struct mint {
    ll v;
    mint(ll x = 0) {
        v = x % mod;
        if(v < 0) v += mod;
    }
    mint operator+(mint a) { return v + a.v; }
    mint operator-(mint a) { return v - a.v; }
    mint operator*(mint a) { return v * a.v; }
};

using fps = vector<mint>;

// f *= (1 + x^d)
void multiply(fps &f, int d) {
    for(int i = sz(f) - 1 - d; i >= 0; i--)
        f[i + d] = f[i + d] + f[i];
}

// f /= (1 + x^d)
void divide(fps &f, int d) {
    rep(i, sz(f) - d)
        f[i + d] = f[i + d] - f[i];
}

int main() {
    int na, nb, w;
    cin >> na >> nb >> w;

    using T = tuple<int, int, int>;
    vector<T> ctm;

    rep(i, na) {
        int m, c;
        cin >> m >> c;
        if(m > w) continue;
        ctm.push_back({c, 0, m});
    }
    rep(i, nb) {
        int m, c;
        cin >> m >> c;
        if(m > w) continue;
        ctm.push_back({c, 1, m});
    }

    sort(all(ctm));

    int term2_min = 1 << 30;
    rep(i, sz(ctm) - 1) {
        if(get<1>(ctm[i]) != get<1>(ctm[i + 1])) {
            term2_min = min(term2_min, get<0>(ctm[i + 1]) - get<0>(ctm[i]));
        }
    }
    if(term2_min >= w - 1) {
        cout << term2_min << endl;
        return 0;
    }

    auto f = [&](int x) -> bool {
        vector<fps> fs(2, fps(w + 1));
        fs[0][0] = fs[1][0] = 1;
        queue<T> que;
        for(auto [c, t, m] : ctm) {
            while(!que.empty() and c - get<0>(que.front()) > x) {
                auto [oc, ot, om] = que.front();
                que.pop();
                divide(fs[ot], om);
            }
            que.push(T{c, t, m});
            multiply(fs[t], m);
            pii bef = {-(1 << 30), 0};
            rng(i, 1, w + 1) {
                rep(j, 2) {
                    if(fs[j][i].v != 0) {
                        if(i - bef.first <= x and bef.second != j) return true;
                        bef = {i, j};
                    }
                }
            }
        }
        return false;
    };

    int ok = w, ng = -1, mid;
    while(mid = (ok + ng) >> 1, ok - ng > 1) (f(mid) ? ok : ng) = mid;

    cout << ok << endl;
}

感想

AOJ-ICPC では 1000 点が付いていますが、特に難しい考察もなく、実装も平易なので 1000 点初 AC を狙いたい人にはお勧めかもしれません。

2022-07-30

ARC 145 作りました

はじめに

AtCoder Regular Contest 145 で writer をした nok0 です！参加していただいたみなさん、どうもありがとうございました！

楽しんでいただけたら writer 冥利に尽きます。

ぼくが人の作問記を読むのが大好きなので、折角なのでセットのコンセプトや各問題の一言作問経緯などをコメントしていきます。ネタバレが盛大に含まれるので注意してください。

ARC145 セットのコンセプト

前半（A-D）を考察一発の軽実装問で固めて、考察も実装も重い EF 問題を存分に楽しんでもらおうという感じのセットでした。なんと、writer の想定解では A-D の実装の合計が 30 行しかありません。

前半の意図はある程度上手くいったとおもうのですが、後半（特に E 問題）が想定より遥かに難しかったようで、ここは反省ポイントです…

前半は本当にアルゴリズム/データ構造の知識は不要で頭だけで解けますし、後半も ACL よりむずかしい高度な知識は不要なので、是非遊んでみてください！

ARC145 問題別一言コメント

A 問題 AB Palindrome

シンプルな設定ながら自然なコーナーケースもあり、かなりお気に入りの問題です。

この問題は ARC 131-F ARC Stamp が元ネタです。（元ネタの問題はまだ通せていないのですが…）低難易度は文字列を使うと生やしやすいことを前回学んで、

文字列の問題を作ろう→そういえば Stamp 押す問題あったな→文字を二種類にしたら簡単？→回文とセットにするといい感じ！

って感じで散歩しているときに生えました。

コーナーケースが 1 種類なこともあり、こるとん式（同じテストケースを何個も入れる）やマルチテストケースにするなども考えてたのですが、邪悪すぎて admin に止められました。

300 点を主張してたのですが、maspy さんが 400 点主張していて 400 点にしました。本当に変えてよかったです。　

B 問題 AB Game

簡単なゲームを数えさせる問題です。丁寧にやる力が大切？

これは特に元ネタもなくて、適当に生えた気がします。問題セットを組み終わった後に、問題名を A 問題と似た感じにしました（ARC140 もそうですが、ぼくは問題名で遊ぶのが割と好きです）。

C 問題 Split and Maximize

簡単な数え上げ問題です。実験するとすぐにわかったり？困ったら実験するの、大事です。

元ネタは UTPC 2021 Swap and Maximize (自作問) です。問題名を適当に変えて問題を作ろうとして、S から始まる単語を探してたら Split が出てきて、設定もそこから生えていい感じだったので採用しました。

D 問題 Non Arithmetic Progression Set

割となんでも通るタイプの構築問題です。想定解みたいなきれいな感じ以外にも、貪欲、乱択、なんでもあります。

元ネタは勿論（？）chinerist さんの良問、ARC 141-D Non-divisible Set です。とても綺麗な問題だったので、適当に設定を変えて出題してみました。

E 問題 Adjacent XOR

非自明な構築問題です。設定も割ときれいだし、解法も少し非自明で面白く、かなりお気に入りの問題です。少しだけ実装が重い点が玉に傷。

難易度推定を完全にやらかしました。非自明パートが 2 つあるものの、操作回数とかからやること直ぐわかりそうだし、行けるよね？って思っちゃいました。ごめんなさい。~~（admin さんがこれは D or E と言っていたのもあります）~~ もともと D と E 逆だったんですが、maspy さんの指摘で E に移動しました（本当に移動してよかったです）。

元ネタは ARC 137-D Prefix XORs です。~~設定をめちゃくちゃパクり~~、数え上げから構築にしたら何故か解けちゃってびっくりしてました。逆から見るとより難しいことを maspy さんに指摘されて、逆から出題することにしました。

F 問題 Modulo Sum of Increasing Sequences

大ボスの数え上げ問題です。コンテスト中単独 AC の leukocyte さん、本当におめでとうございます！！（何者？）

もともとはもう少し簡単だったんですが、admin さんとの議論でどんどん難しくなり、1200 点になりました。

やばそうな見た目ですが、形式的冪級数とか怖いものは出てきません。MOD の 3 乗が間に合うことがヒントです、是非挑戦してみてください！

おわりに

初めて単独 writer を出来てとても楽しかったです！たくさんの方に問題を見てもらえて、6 問全部自分の問題なのは本当嬉しいですね。

今回の ARC で温まった方、是非作問して Rated 増やしてください！！！お願いします

2021-12-13

AtCoder橙になりました

はじめに

この記事は競プロ Advent Calendar 2021 - Adventar の11日目の記事です。遅刻してしまいごめんなさい…

本題

競プロを始めて1年と8ヶ月、ようやく橙コーダーになることができました！

f:id:tsuchinok:20211213142913p:plain

皆さん、沢山のファボ及びお祝いリプライ本当にありがとうございます！

競プロ始めてから1年8ヶ月、初の銀パフォでついに橙達成です！！！やった！！！！

nok0さんのAtCoder Regular Contest 129での成績：7位
パフォーマンス：3200相当
レーティング：2297→2427 (+130) :)
Highestを更新し、三段になりました！#AtCoder #ARC129 https://t.co/g2KwPWvoNV pic.twitter.com/BN8H51JkAP
— nok0 (@nok0_kyopro) 2021年11月21日

自己紹介は以前の記事(入緑しました！！ - つちのこの日記)で書きましたし、ポエムは恥ずかしいので赤になるまでは取っておきます。また、先人の皆さんがモチベーションの維持、コンテストの立ち回りなどの話は書いていたので、今回は別の視点から書きます。

本記事では、黄コーダーから橙コーダーになるための実力向上に役立ったことを、お薦め順に書こうと思います。

CodeForces Div.1 バチャ

効果　☆☆☆☆☆
手軽さ ☆☆
総合評価 ☆☆☆☆☆

最強です。ARC以上の難易度のセットを、緊張感を持って練習することができます。まったり精進をするのも大事ですが、やはりバチャは時間内に通し切ることが求められるため、考察と実装の精度力、速度力をバランス良く鍛えることが出来ます。 Upsolve をすることで新たな知識も身に付きます。

欠点としては、英語を読まなければいけない(これは利点かもしれません)、拘束時間が長い(最低2時間、Upsolveもするならばそれ以上)などがありますが、欠点を補って余りあるほどの利点があるので、是非やりましょう！

人のブログ・解説記事を読む

効果　☆☆☆
手軽さ ☆☆☆☆☆
総合評価 ☆☆☆☆

新しい知識や、他人の考察手順、コンテスト中の立ち回りを学べるなど、実は様々な利点があります。知識ゲーはARC以上ではあまり出ないし、効果が微妙だと考える方もいるかもしれませんが、実は高度典型はARCで何回も出ています。実際、私が橙になった回も高度典型(k値PSP)が ARC-E として出題され、maspy さんの解説ブログを読んでいたおかげでコンテスト中にその問題を解き銀パフォを得ることが出来ました。何より、コンテストに役立つ役立たない以前に、新しいことを学ぶのは人間の知識欲を満たすことが出来て非常に楽しいです！

記事を読むのは通勤・通学中等いつでも出来て、疲れている時でもやりやすいので、本当にお手軽です。貪欲に知識を仕入れていきましょう！

おすすめのブログ(HP?)は maspyのHP です。

AtCoder 橙diff埋め

効果　☆☆☆☆
手軽さ ☆☆☆
総合評価 ☆☆☆☆

AtCoderのレートは、基本的にちょっとした成功を積み重ねるよりも、一発大成功を当てた方が上がりやすい仕様となっています。そして、大成功を当てるためには異常早解きをする、もしくは自分の適正難易度以上の高難易度を解く必要があります。

高難易度を解くための練習として、橙diffを考えるのは非常に有用です。橙diffは、黄色程度の実力があれば時間をかければ大抵は苦労しつつも解けることができると思います。その経験を繰り返すことで、本番でも橙diffを通せる確率を上げていけると思います。

AtCoder 黄diff埋め

効果　☆☆☆(レートが2200以下なら☆☆☆☆くらい)
手軽さ ☆☆☆
総合評価 ☆☆☆

黄diffは、橙になるためには基本的に解けるべき難易度です。(といってもまだまだコンテスト中解けないことはあります…) 黄diffを埋めることで、抜けている典型を抑えられたり、ちょっとした ad-hoc の練習ができるので、特に黄色下位のうちはおすすめの精進方法です。

AtCoder 赤diffを考える

効果　☆☆☆-☆☆☆☆
手軽さ ☆☆
総合評価 ☆☆☆

橙diff埋めでも言及したように、高難易度を通す練習は大事です。ただ赤diffはむずかしいので、中々解けなくて大変だったり、解けなすぎてモチベが低下する危険もあります。まずは橙diffを埋めにいく方が良さそうな気がします。

作問

効果　☆☆
手軽さ ☆ (原案を考えるだけなら☆☆☆)
総合評価 ☆☆(楽しさは☆☆☆☆☆)

正直、作問で実力がすぐに向上するかと言うと微妙ですし、テストケースまで用意するとなるとやや面倒であることは事実です。ただ競プロの実力を上げたいのであれば、上に示した他の方法を行う方が効率はいいと思います。

しかし、作問は本当に楽しいです！自分が考えた面白そうな問題が解けた時は本当に気持ちいいですし、皆さんが自分の問題を解いてこの問題は面白かった、このテクニックは勉強になったなどと褒められるととても嬉しくなります。

ぜひみなさんにも作問を楽しんで頂きたいです！

おわりに

競プロを楽しんで続けることで、橙にまでなることができました。まだまだ知らないことばかりですし、これからも勉強していくことで強くなる余地は無限に残っているように感じています。長い道のりですが、赤を目指して頑張ります！

明日の記事は Rute さんの「Sushiを食べながらSushiを解く」です。

2021-10-09

Berlekamp-MasseyやBostan-Moriを使うことで殴れる問題一覧

はじめに

最近Berlekamp-MasseyやBostan-Moriで殴れる問題をよく見るので、そのような問題をメモしていこうと思います。以下の説明はお気持ちなので間違ってる可能性が大いにあります。もし間違っている点がありましたら教えていただけるとありがたいです。

この記事ではアルゴリズム自体の解説はしません。世の中にはたくさんわかりやすい記事があるので、そちらを参考にしてください。

また、殴れる問題を見つけたらコメントやtwitterなどで教えていただけるととても助かります！

Berlekamp-Massey ってなに？

線形漸化式で与えられる数列の最初の何項かがわかっている時に、その漸化式を求めるアルゴリズムです。計算量は、求める線形漸化式が $d$ 項間線型漸化式のとき $Ο(d ^ 2)$ です。

Bostan-Mori ってなに？

$d$ 項間線型漸化式を満たす数列の $N$ 項目を $Ο(M(d) \log N)$ で求めるアルゴリズムです。ここで、 $M(d)$ は $d$ 次多項式同士の積を求めるために必要な計算量です。

$\bmod$ が $998244353$ のときなどは NTT を用いることで $M(d)=d\log d$ となります。 $\bmod$ が $ 1000000007$ のときは (任意modNTT を用いない限り) $ M(d)=d ^ 2 $ となります。

使い方

以上の二つのアルゴリズムを組み合わせることで、線形漸化式の導出が容易ではない(もしくはめんどくさい)場合に、愚直な解法で数列の最初の何項かを求め、Berlekamp-Masseyで線形漸化式を求め、Bostan-Moriで数列の $N$ 項目を求めることで容易に問題を解ける場合があります。

以下ではその手法が使える問題のリストをあげます。(随時教えていただけるとありがたいです)。

殴れる問題一覧

Cube (AtCoder)

atcoder.jp

OEISを見ると漸化式が乗っているので、Bostan-Moriを使うだけです。

Tax Included Price (AtCoder)

atcoder.jp

周期性がありそうなので、線形漸化式だと思うと、上記の手法で殴れます。

この問題は、あまりを求めるわけではないので、適当に2つの $\bmod$ を選び、復元する操作が必要です。

Many Bus Stops (easy) (yukicoder)

yukicoder.me

Many Bus Stops (hard) (yukicoder)

yukicoder.me

このように、行列累乗っぽい問題は大体線形漸化式なので、上記の手法が使えます。

Tetrahedron (mojacoder)

mojacoder.app

想定解法は対称性から状態を頑張ってまとめて行列のサイズを落とすものですが、この問題も殴ることができます。愚直に最初の方を求めると、綺麗な漸化式が求まるのであとはやるだけです。

Hanjo 2 (AtCoder)

atcoder.jp

simple 門松列 problem Re:MASTER (yukicoder)

yukicoder.me

現在のFastest Codeは、これで殴ったものです。

Next Rational (yukicoder)

yukicoder.me

線形漸化式であることを信じましょう。信じるものは救われます。

Roman Digits (codeforces)

codeforces.com

周期性！(素振り)

擬二等辺三角形 (AtCoder)

atcoder.jp

頑張って計算すると $Ο(1)$ で解けますが、めちゃくちゃ大変です。

上記の手法で殴ると、とても簡単に解くことができます。 maspyさんの以下のブログが詳しいです。

maspypy.com

Good Sequence (yukicoder)

やるだけ

yukicoder.me

随時加筆します。

2021-07-25

懺悔一覧

コンテストやバチャ等での失敗を懺悔します

一般的な話

部分問題(や，制約を弱めた版)ですら，これでしか解けない → それに近いアルゴリズムを使う

例題:

atcoder.jp

区間に対する操作や区間和など -> 累積の二要素への作用or演算の言い換えを考える

例題:

atcoder.jp

swapをすることで区間を連続にする → $B_i:=A_i -i$ の置換をした上で， $B_i$ を一致させると考えると筋が良い。

例題:

atcoder.jp

bit

bit 毎に見てもよい
クエリの順番が bit 毎に独立なことがある

期待値関連

総和の期待値 -> $i$ 以上の個数の期待値を $i$ を動かして足し合わせる。　決めうち二分探索とお気持ち的には近いかも、忘れがち。

例題:

atcoder.jp

終了までの期待値などでも、ここに操作をする回数の期待値の和　という期待値の線形性が使える

期待値の線形性！（素振り）

例題:

atcoder.jp

最適化関連

実は自明な上界 or 下界が達成可能です！！！！！！！！！！ ←解けない時には一回疑う！！！

例題: atcoder.jp

gcdは，一つ決めれば候補はその約数のみ　$ 10 ^ 9 $ 以下の高度合成数の個数は $1344$ 個

例題: atcoder.jp

最適化であっても，最終形の判定問題を最初に考えるとうまくいくことがおおい.

例題:

atcoder.jp

絶対値の最大化は max$(x,-x)$ の最大化で言い換えるとうまくいくことが多い.

atcoder.jp

動的計画法関連

bitset高速化でもしない限りbool配列でDPは基本的に良くない何か情報を持たせたい
DPの遷移で、使用しない場合の chmax(dp[i+1][j], dp[i][j]) みたいなのを忘れない！！(やらかしが多い)
結果としてありうるか状態を判定する -> 判定問題は貪欲にできる -> 貪欲法をDPに落とす　の思考をスムーズに出来るようにする

例題:

https://techful-programming.com/user/event/session/I1Hs4VIF/problem/coding/18306

計算量関連

素直な全探索$ Ο(N ^ 2) $ が間に合うなら，まずそれを試す.

例題:

atcoder.jp

調和級数も疑ってみる(特に数列がdistinctだったりする時)

例題:

codeforces.com

置換関連

$i$ から $p_i$ に有向辺を貼って考えるとうまくいくことがおおい.(2点swapなどでも)

例題:

atcoder.jp

実装関連

bitのi番目を取る時の bit >> i & 1 この & 1 を忘れない！！！ (もはやライブラリ化したほうがよくないか？)
if(i == j == k) とか書かない！ C++はpythonじゃありません！！

メンタル面

落ち着く
冷静になる

2021-06-25

純粋培養競プロerの応用情報技術者合格体験期

令和3年4月の応用情報技術者試験に無事合格したので、合格体験期を書きます。

試験勉強前のスペック

都内の大学生(情報は専門外)で、かつPCいじりとかの趣味がなかったので、そこらへんに関する知識は0でした。競プロは少しやっていた¹ので、プログラミングだけは出来るかなーという感じでした。

受験のきっかけ

前回の試験の後に、合格した人のツイートが沢山流れてきて存在を知りました。春休み暇だし、一個くらい資格取れるといいなーみたいな軽いノリで受験を決めました。

使った参考書

キタミ式イラストIT塾応用情報技術者令和03年 | きたみりゅうじ | コンピュータ・情報処理 | Kindleストア | Amazon

評判が良さそうだったこの本を試験の2ヶ月くらい前に優しいフォロワーさんから頂きました。かなり噛み砕いて書いてあって²、重度のパソコン音痴だった私にもわかりやすかったです。

午前の勉強でやったこと

自分が怠惰すぎて、気づいたらほぼ何もしないまま試験1週間前くらいになってました。時がすぎるのって早いですね。。

そこで

www.ap-siken.com

のサイトを使って午前の過去問をやってみたところ、40%くらいしか点が取れなくて絶望していました。そこから毎日少しずつ過去問をやってわからないところを参考書で調べて、当日には55~65%くらい取れるようになりました(合格ラインが60%なので、危ない)

午後の勉強でやったこと

友人に午前が出来れば午後も出来ると言われた³ので、当日まで何もしていませんでした。⁴ 本当に心臓に悪いので、少しは前から見ておきましょう。

当日

朝

天才なので、起床試験に無事合格しました。⁵

会場に着いたら、全然人がいなくてびっくりしました。結局椅子は3-4割くらいしか埋まらなかったです。(受験料、もったいなくないですか？)

午前試験

テスト直前まで参考書を見てめっちゃ詰め込んでいました。⁶

午前試験はとりあえず60分くらいで全問埋め終わり、手応え6割強だな、受かってるといいなと祈りながら途中退出しました。

お昼

お昼は八王子でラーメンを食べました。八王子ラーメンを食べるのは初めてだったのですが、上に乗ってる玉ねぎがいいアクセントでおいしかったです。

ラーメンを食べながら、午後の選択科目を何にするか考えてました。この時点ではプログラミングを選択することしか決めていませんでした。

文明の力であるグーグルさんによると組込みシステム開発がプログラミングに近いらしいので、これを選択することに決めます。

残りは2つです。データベースはなんかプログラミングっぽいので選択することにして、後一つを悩んでいました。

すると国語力でシステム監査が解けるという噂を見たので、最期の一枠をシステム監査に決めました。結果的にはこれが大成功でした。

その後は会場に戻り、午後の過去問を見ながら、プログラミングはいけそう、データベース何もわからんという気持ちになっていました。

午後

解いた順番に書きます。

情報セキュリティ

まともに午後の勉強していないのでそれはそうなのですが、何もわかりません。適当に埋めて次に行きます。

プログラミング

情報セキュリティが全く解けなくて嫌な気持ちになったので、得意なプログラミングに行きます。全問を10分くらいで解けて、全知の気分を味わえました。

組込みシステム開発

かなりプログラミングに近い内容でした。一応全部の問題を20分くらいで埋めて次に行きます。

システム監査

国語の試験のような感じでした。読解することで知識ゼロでも大体埋められました。

データベース

最後にデータベースをやります。 sql 文も大体プログラミングみたいなものだと思って舐めていたのですが、全然違ってなにもわかりませんでした。とても悲しい気持ちになりました。

全部終わったので、1時間強を残して帰りました。手応えとしては五分五分くらいでした。

結果発表

f:id:tsuchinok:20210625125155p:plain

無事合格しました！午後の点数は、体感ですが

情報セキュリティ 7点
プログラミング 20点
データベース 7点
組込みシステム開発 17点
システム監査 18点

くらいだと思います。

感想

ギリギリでしたが、合格できて嬉しいです！

勉強の過程で、様々な知識が身につけられて面白かったです。

次に試験を受けるときは詰め込まなくてもいいように計画的に勉強しようと思いました。

競プロer向けのおすすめ科目

個人的には以下の3つがおすすめです。

プログラミング

緑コーダー以上なら全く勉強せずとも十分満点が狙えると思います。　正直取らない手はないです。

組込みシステム開発

これもプログラミングに近い科目でおすすめです。

システム監査

競プロで難読な問題文を読んでいる経験があれば、これくらい読めると思います。知識をほぼ要求しないのでおすすめです。

現時点でAtCoder2200↩
その分ページ数は多くて持ち運びは不便です(電子版のほうがよかったかも？)↩
要出典↩
午後試験の問題を見たのも、当日が初めてでした↩
起床試験で足切り食らう人を多く見かけます↩
結局直前の詰め込みは正義です(?)↩