CPCTF 2023 writeup - ruthen's blog

個人参加で13位でした。

[Easy] [Reversing] passcode以外のEasyまでの全ての問題と、MediumのPPCを解きました。

[Newbie] [Misc] 2DCode 1

Hintを開けるとDotCodeだとわかり、free barcode scanner dotcodeなどと調べるとオンラインリーダーがヒットする。

[Newbie] [PPC] Count Coins

実装する。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N, X;
    cin >> N >> X;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    REP(i, N) {
        if (A[i] == 1) {
            X = min(X + 1, 10LL);
        } else {
            X = max(X - 3, 0LL);
        }
    }
    cout << X << '\n';
    return 0;
}

[Newbie] [Crypto] Entrance to the Crypto World

最後にフラッグらしきものがあり、EREVHを見るとCPCTFを2文字ずらしたものだとわかる。

[Newbie] [PPC] Transfer

比較する。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << min(A + B, C + D) << '\n';
    return 0;
}

[Newbie] [OSINT] Tube

china xinxiuなどと検索するとWikipediaの駅の記事がヒットし、Shenzhen Metro Line 2だと分かる。

[Newbie] [Web] easylogin

Hintを開けると' OR 0=0 --をパスワードとして入力すれば良いことがわかる。しばらくcpctf.spaceにログインを試みていた。

[Newbie] [Forensics] investigation

zipをダウンロードすると画像がたくさんあり、頑張ってその中からフラッグが書かれたものを探す。

何も考えずにHintを開けたがこれくらいは解けても良かったと思う。

[Newbie] [Shell] netcat

WSLのbash上でnc netcat.cpctf.space 30005を入力するとフラッグが手に入る。

[Newbie] [Misc] welcome to CPCFT

Hintを開けるとトップページとDiscordのreadmeチャンネルとVisualizerにあると書かれている。 VisualizerではF12を押してctrl+fで}を探すと見つかる。

Hintなしで解いている人がいてすごい。

[Easy] [OSINT] Shan shui

写真から郵便番号を特定する問題。

最初はparty sky pekingなどと検索していたがダメで、Hint2まで開けると郵便番号を見ろと書いてある。いろいろ調べると中国市外局番と郵便番号検索がヒットするので773を入れる。検索結果が複数あり悩むが、0773-2629999で検索すると出てくる物件の名前でGoogle Mapで検索すると郵便番号が541012と出てくるので近そうな541000を入れる。

全探索しても良かったと思った。

[Easy] [Misc] 1dayattack

Hint2まで開けるとMarkupというPixelシリーズのスクリーンショット編集機能の脆弱性だと分かり、記事を読むと解析サイトが見つかる。問題文中にPixel 4aと書いてあるので解ける。

[Easy] [Misc] 2DCode 2

Hint2まで開けるとQRコードが壊れていると分かる。ファインダパターンという回の部分と、タイミングパターンという- - -の部分を温かみのある手作業で直して適当なQRコードスキャナーで読み取るとフラッグが得られる。

[Easy] [Pwn] Big or Small

nc big-or-small.cpctf.space 30008を入力するとカジノが始まる。 zipにソースコードがあるので読んでみるが特に変なことは思いつかない。ただ乱数は毎回ランダムである上、100コインスタートなのに100000コイン稼ぐ必要があり愚直にやるのは無理だなとなる。

Hint2を開けると掛け金の下限がないことが分かるので-1000000などと入れて50%が外れるまでやると解ける。

[Easy] [OSINT] Dokoda? 1

Hint1を開けると画像検索しろとあるのでやる。シンボルプロムナード公園というらしい。 Google Mapのストリートビューを使いながらざっくりとした経度と緯度をURLから読み取った。

多分ここ行ったことあるな。

[Easy] [OSINT] Dokoda? 2

Dokoda? 1と同じくGoogle Mapを使う。東海工産で調べるとそれらしき場所がヒットするのであとは1と同じ。

[Easy] [PPC] Find cpctf

部分文字列になるかを全箇所試す。

最初substringではなくsubsequenceだと思っていた。これ解けるのかな。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    string S;
    cin >> S;
    vector<int> cnt(26);
    REP(i, N) cnt[A[i]]++;
    string T = "cpctf";
    int ans = 0;
    REP(i, N - 4) {
        vector<int> need(26);
        REP(j, 5) {
            // S[i + j] + A[i] = T[j]
            need[(T[j] - S[i + j] + 26) % 26]++;
        }
        int ok = 1;
        REP(j, 26) {
            if (need[j] > cnt[j]) {
                ok = 0;
            }
        }
        if (ok) {
            ans = 1;
            break;
        }
    }
    cout << (ans ? "Yes" : "No") << '\n';
    return 0;
}

[Easy] [PPC] Floor Sqrt

$N$ が大きいので平方分割したくなる。 $\lfloor \sqrt{n} \rfloor = k$ と決めると、 $k^2 \leq n \leq k^2+k-1$ のとき条件を満たすことが分かるのであとは $k$ を全探索する。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N;
    cin >> N;
    long long ans = 0;
    for (long long k = 1; k <= 1000000; k++) {
        ans += max(0LL, min(N, k * k + k - 1) - k * k + 1);
    }
    cout << ans << '\n';
    return 0;
}

[Easy] [PPC] Geometric Progression Sum

すべての $i$ について $L_{i} = 1, R_{i} = N$ だった場合、前の要素を $X$ 倍していけば良い。区間がもっといろいろ考えられるが、競プロ方言であるところのimos法っぽくやれば良い。実装ではイベントソートのように実装している。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

#include <atcoder/modint>
using mint = atcoder::modint998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, X, Q;
    cin >> N >> X >> Q;
    vector<vector<tuple<int, int, int>>> GL(N), GR(N);
    REP(i, Q) {
        int b, l, r;
        cin >> b >> l >> r;
        l--, r--;
        GL[l].push_back({b, l, r});
        GR[r].push_back({b, l, r});
    }
    mint cur = 0;
    vector<mint> A(N), xp(N + 1);
    xp[0] = 1;
    REP(i, N) xp[i + 1] = xp[i] * X;
    REP(i, N) {
        // precalculation
        for (auto& [b, l, r] : GL[i]) {
            cur += b;
        }
        A[i] = cur;
        cur *= X;
        // postcalculation
        for (auto& [b, l, r] : GR[i]) {
            cur -= b * xp[r - l + 1];
        }
    }
    REP(i, N) cout << A[i].val() << " \n"[i + 1 == N];
    return 0;
}

[Easy] [PPC] Whisper Sucu

頂点倍加BFSをする。

もうちょっと真面目に書くと、偶数時刻のうち最も早く到達した時間と、奇数時刻のうち最も早く到達した時間から他の頂点に移動する場合のみを考えれば良いので、その分頂点数を増やす。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

#include "graph/read_graph.hpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    auto G = read_graph<int>(N, M, true);
    constexpr int INF = 1 << 30;
    vector dp(2, vector(N, INF));
    dp[0][0] = 0;
    queue<pair<int, int>> que;
    que.push({0, 0});
    while (!que.empty()) {
        auto [s, v] = que.front();
        que.pop();
        for (auto &e : G[v]) {
            if (s + 1 == e.cost or e.cost == 3) {
                if (dp[s ^ 1][e.to] > dp[s][v] + 1) {
                    dp[s ^ 1][e.to] = dp[s][v] + 1;
                    que.push({s ^ 1, e.to});
                }
            }
        }
    }
    int ans = min(dp[0][N - 1], dp[1][N - 1]);
    if (ans == INF) ans = -1;
    cout << ans << '\n';
    return 0;
}

[Easy] [Pwn] overrun

時間もないのでHint1を開けると逆アセンブルした結果が書いてある。 char name[50];などと書かれているのでとりあえず長い文字列を入れてみるとフラッグを教えてくれる。

[Medium] [PPC] Digital Clock

$x+y=K (x \geq 0, y \geq 0)$ を満たす整数 $(x \bmod H,y \bmod W)$ のペアを数える問題。

$x \bmod H,y \bmod W$ はそれぞれ $H,W$ 周期なので、 $lcm(H,W)$ 周期で同じものが出てくる。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long H, W, K;
    cin >> H >> W >> K;
    long long ans = min(H / gcd(H, W) * W, K + 1);
    cout << ans << '\n';
    return 0;
}

[Medium] [PPC] God Field

$N,M$ が小さく、また防具が壊れているか壊れていないかの2値なのでbitDPをしたくなる。

dp[i][b]=現在i番目の攻撃まで受け終わっており、使った防具の集合がbである として、現在未使用の防具に対し、今回の攻撃で使う防具の組合せを全探索すれば良い。このとき、 $N$ 要素の集合の冪集合の各要素に対してその部分集合を全体 $O(3^N)$ で列挙するテクニックを使うと、 $O(NM3^N)$ で解ける。（使わなくても良いかもしれない。）

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    long long X;
    cin >> N >> M >> X;
    vector<long long> A(N), B(M), C(M);
    REP(i, N) cin >> A[i];
    REP(i, M) cin >> B[i] >> C[i];
    int N2 = 1 << N, mask = N2 - 1;
    vector dp(N2, X);
    REP(i, M) {
        vector np(N2, 0LL);
        REP(b, N2) {
            int use = b ^ mask;
            vector<int> ts;
            for (int t = use; t; t = (t - 1) & use) ts.push_back(t);
            ts.push_back(0);
            for (auto &t : ts) {
                long long dmg = B[i];
                REP(j, N) dmg -= (t >> j & 1) * A[j];
                dmg = max(dmg, 0LL);
                if (C[i] == 1 and dmg > 0) dmg = X;
                np[b | t] = max(np[b | t], dp[b] - dmg);
            }
        }
        swap(dp, np);
    }
    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';
    return 0;
}

[Medium] [PPC] Max Min GCD

$C_k$ は $A_k$ または $B_k$ の約数となる。

$A_k$ の約数を列挙し、 $B_j (j \geq k)$ の約数をカウントしておいた配列を見てチェックする。 $B_k$ についても同様。これは $k$ を降順にチェックすると高速に判定できる。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

#include "math/divisor.hpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];
    vector<int> ca(100005), cb(100005);
    for (int i = N - 1; i >= 0; i--) {
        auto da = divisor(A[i]);
        auto db = divisor(B[i]);
        for (auto& d : da) ca[d] |= 1;
        for (auto& d : db) cb[d] |= 1;
        long long ans = 1;
        for (auto& d : da)
            if (cb[d]) ans = max(ans, d);
        for (auto& d : db)
            if (ca[d]) ans = max(ans, d);
        C[i] = ans;
    }
    REP(i, N) cout << C[i] << " \n"[i + 1 == N];
    return 0;
}

[Medium] [PPC] Move Road

上下左右に移動できることから、例えば左上から順番に見ていくというようなことはできないことが分かる。

4方向に移動した後どうなるか観察する。

右方向に移動する場合、右のマスが空いている必要があるが、移動した0.5秒後に車が追いかけてくるので車との相対位置は変わらない。

下方向に移動する場合、真下のマスと左下のマスが空いている必要があり、元のマスの左下のマスに移動する。

上方向に移動する場合、真上のマスと左上のマスが空いている必要があり、元のマスの左上のマスに移動する。

左方向に移動する場合、左の2マスが空いている必要があり、元のマスから左に2マス行ったマスに移動する。

静止した場合、左のマスが空いている必要があり、元のマスの左のマスに移動する。

よって実は移動方向が少し変なBFSをすれば良い。

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

#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    REP(i, H) cin >> S[i];
    vector dp(H, vector(W, 0));
    queue<pair<int, int>> que;
    REP(j, W) {
        dp[0][j] = 1;
        que.push({0, j});
    }
    while (!que.empty()) {
        auto [x, y] = que.front();
        que.pop();
        // up
        if (x > 0 and S[x - 1][y] == '.' and S[x - 1][(y + W - 1) % W] == '.' and dp[x - 1][(y + W - 1) % W] == 0) {
            dp[x - 1][(y + W - 1) % W] = 1;
            que.push({x - 1, (y + W - 1) % W});
        }
        // down
        if (x < H - 1 and S[x + 1][y] == '.' and S[x + 1][(y + W - 1) % W] == '.' and dp[x + 1][(y + W - 1) % W] == 0) {
            dp[x + 1][(y + W - 1) % W] = 1;
            que.push({x + 1, (y + W - 1) % W});
        }
        // left
        if (S[x][(y + W - 2) % W] == '.' and S[x][(y + W - 1) % W] == '.' and dp[x][(y + W - 2) % W] == 0) {
            dp[x][(y + W - 2) % W] = 1;
            que.push({x, (y + W - 2) % W});
        }
        // stay
        if (S[x][(y + W - 1) % W] == '.' and dp[x][(y + W - 1) % W] == 0) {
            dp[x][(y + W - 1) % W] = 1;
            que.push({x, (y + W - 1) % W});
        }
    }
    int ans = *max_element(dp[H - 1].begin(), dp[H - 1].end());
    cout << (ans ? "Yes" : "No") << '\n';
    return 0;
}