概要

みなさま、2025-04-18 20:00(JST)から2025-04-20 20:00(JST)まで48時間かけて開催されたCPCTF2025へのご参加ありがとうございました！

この記事では Nzt3 が作成に関わった問題の作問裏話と想定解法を載せています。

目次

• [PPC Lv.4] One Power One Kill (原案・準備)
• [PPC Lv.4] A Little Cheat (原案・準備)
• [PPC Lv.4] Prime Dance (原案・準備)
• [PPC Lv.4] Lower Nim (解法・準備)
• [PPC Lv.4] Reversible Tile (制約提案)
• [Crypto Lv.5] One More PPC Problem (原案・準備)

[PPC Lv.4] One Power One Kill

問題はyukicoderにあります。
https://yukicoder.me/problems/no/3115

作問動機

「01列が隠されている。01列を聞くと部分文字列として何個含まれているか教えてくれるので質問3回でどこか1文字特定しろ。」という問題があります。この問題は「個数」という少ない情報量と「3回」という少ないクエリ数から01列という大きなものを当てているように見えます。実際には1文字しか当てていないのですが、その1文字の選び方で必要な情報量が変わります。
このように非常に少ないクエリ数で隠された情報を当てる、しかもクエリによって隠された情報の当てやすさが変わる問題を作りたくなりました。

作問

隠し持った整数を当てる問題を作りたいです。
Power!という感じの強そうな操作が好きなので、入れます。
意味不明な関数の値$f(X,A,B)$から$X^{\prime }=X^A(\mathrm{mod}B)$ を当てられたら嬉しいですね。$f$を$X$と$A^B(\mathrm{mod}10^9+7)$のGCDに設定します。いい性質がなさそうですね。

$B=1$や$(A,B)=(p-1,p)$で$f$を無視して解かれると嫌なので、$A,B$の制約を$X$の制約と揃えてジャッジを適応的にします。少なくとも$X=B\pm 1$と$X=B$を区別する必要を作ります。

あとは良い感じに解ける$A,B$の組が存在してくれると嬉しいですね。
$A=k\phi (B),B=p$を探索すると$(19000,101)$を見つけたので出題できそうです。
→ kenkenが$A=k\phi (B),B=p^n$ という方針を提案しました。
→ Naru820により乱択が提案されました。
乱択で十分高速に解けることがわかったのでそっちが想定解だったことにして出題しました。

ヒントと意図

ヒント1

ジャッジは適応的です。
$K$ の情報から $X^{\prime }$ が一意に定まらない場合、ジャッジが途中で $X$ を変更し、絶対に正解できません。

これは「適応的」というのがどういう意味かを示すヒントです。
問題では$X$が決められた後に$A,B$を渡すかのように書いていますが、実際にはジャッジは$A,B$を受け取った後に$X$を決定しています。(何も出力していないのでどのように$X$を変更しても絶対に以前の出力に矛盾しません)
ジャッジは$A,B$を受け取った後に絶対に不正解にさせられる$K$が存在しないか探索し、存在すればそれを選択します。

ヒント2

適当な $A,B$ について $K$ と $X^{\prime }$ の対応を調べてみましょう。
もし、 $K$ から $X^{\prime }$ が一意に定まるような $(A,B)$ の組が見つかれば、その対応を用いて問題を解くことができます。

これは「乱択で十分高速に解ける」ことを強く匂わせるヒントです。
実験コードを書くことに思い至れば直ちに解けると考え、実験を推奨しています。

ヒント3は具体的な $(A,B)$ ペアと、オイラーの定理を用いた構成方法を示しています。

感想

どのような方針でも埋め込みになるので提出コードに書かれた$A,B$を見て方針を知ることができます。dict埋め込みが見れたり、提案時想定の$(19000,101)$が見られたり、全探索提案の$(100,132)$があったりして楽しかったです。

$(p-1,p)$を提出して適応的なジャッジに倒されている人がかなりいました。想定誤答なので引っ掛かってくれて嬉しいです。

[PPC Lv.4] A Little Cheat

問題はyukicoderにあります。
https://yukicoder.me/problems/no/3119

作問動機

簡単な問題に操作を追加して少し複雑にならないか試しました。
桁DPのように2値のフラグを持つようにできると嬉しいので、そうなったものを出題しました。

ヒントと意図

ヒント1

$f(B)$ を具体的に求めることは難しいです。
値を交換する操作を行わない場合のスコア $f^{\prime }(B)$ を考えます。
この場合はある $B_i$ が$f^{\prime }(B)$ に寄与するかどうかは数列の他の要素に依存しません。
寄与を分解して $f^{\prime }(B)$ の総和を求めてみましょう。

交換を行わない場合の問題が主客転倒で容易に解けることを提示して数え上げの方針を与えています。
「値の交換」がこの問題の本質であり、そこを重点的に考えるべきだということを主張しています。

ヒント2

任意の整数列 $B$ について、 $f(B)-f^{\prime }(B)\le 1$ です。
つまり、値を交換する操作によって $A_i<B_i$ を満たす $i$ の個数 は高々 $1$ 個しか増えません。

$A_i<B_i$ を満たす $i$ の個数が増えるような操作であればどれを選択しても「 $A_i<B_i$ を満たす $i$ の個数を最大化する適切な操作」になります。

交換の操作の性質を提示しています。この「$+1$」の回数をどう数え上げるかがわかればこの問題は解けます。

Writer想定解は桁DPをベースに考えたDPですが、Testerの解はこのヒントに近い「$+1$」の回数を数え上げる方針になっています。

想定解法

$B$ を前から構築し、それぞれの状態が何通りあるか数えながらスコアへの寄与を計算します。

ある数列$B$において、値を交換する操作でスコアは高々1だけ増えます。スコアが増える場合はどこを交換しても良いので、都合の良いところを交換します。今回は$B$を前から構築するので「最初に出てきた改善」を採用することにします。改善を行ったかどうかのフラグをDPの添字に持たせます。

直前の値を状態として持つようにすると、「$i$番目まで構築して末尾は$x$」という状態から次の$i+1$番目に遷移する時間計算量$\Theta (N{M}^2)$のDPができます。これを高速化します。

$\max (A_i,A_{i+1}),\min (A_i,A_{i+1}),B_i$ の大小関係から $B_i$ の直接の寄与が計算できます。関係が同じものはまとめて計算できます。

値の交換によるスコアへの寄与は $B_{i+1}$ を追加する際に判定します。
$B_{i+1}$の$A_i,A_{i+1}$との関係も$3$通りで、交換の有無は具体的な$B_i,B_{i+1}$の値を知らなくとも$A_i,A_{i+1}$との大小関係だけから定まります。
$A_{i+1},A_{i+2},B_{i+1}$の大小関係で次の状態が定まるので、この後も$A$との大小関係だけ考えていればDPができます。

以上で末尾の値がどの関係に該当するかだけを持つ$O(N)$のDPができました。

感想

簡単な問題に適当な操作を入れたらDPの問題ができて、性質を考えると高速化できました。問題の性質から定数個の状態に分類できてDPの状態数が圧縮されるのはどのような時でも面白いですね。

Prime Danceより難しいからボスクラスになると思って提案したら、Prime Danceよりは簡単と言われた上にLv.5の2問が生えてきてボスではなくなってしまいました。

[PPC Lv.4] Prime Dance

問題はyukicoderにあります。
https://yukicoder.me/problems/no/3121

作問動機

変なコストの最短経路問題を作りたかったのと、グリッド探索の問題を作りたかったので、まとめました。

S.G..
####.

上のような同じグリッドを複数回通ることに意味があるケースで人々を倒す！(素振り)

ヒントと意図

ヒント1

ゴールへ移動する適当な操作列を用意します。
操作Aを行った直後に操作Bを行うことで、実質的に移動をせずに操作A,操作Bの回数を $1$ 回ずつ増やすことができます。

移動回数を増やすことは自由に行える、つまり「素数」という条件が実は特に問題にならないことを表しています。
最小移動回数を求める部分と素数に調整する部分を分離することを伝えようとしました。

ヒント2

どのような経路で移動したとしても、スタートからゴールまでの座標の移動は縦に $G_x-S_x$ 、横に $G_y-S_y$ で一定です。
また、操作により必ず座標が変化します。
つまり、どのように移動したとしても $(操作Aの回数)-(操作Bの回数)$ は一定です。

$4$方向の移動回数を添字として持ちたいですが、これは計算量的に難しいです。
実は$2$方向の回数を数えればよいということを提示し、この後の「$1$方向は添字にして$1$方向は最小化」につなげる狙いがあります。

想定解法

ゴールする操作列において、操作Aの回数と操作Bの回数の差は一定です。
操作Cと操作Dについても同様の関係があります。

操作Aを1回以上行っていれば、そこにBAを挿入することで操作A,Bの回数を好きなように1回ずつ増やせます。
操作Cについても同様です。

後から操作を1回ずつ増やせることを考えると、操作Aの回数を固定する(=操作Bの回数も固定される)と、操作Cが1回以上なら少ない方がよいことがわかります。

操作Aと操作Cの回数については固定の関係はなく、移動経路によって関係が異なります。
操作A+操作Cなど固定の関係がない値を距離として採用すると、素数にするための回数調整で全体の最小回数を達成できないケースがあります。

座標、操作Aの回数、操作Cを1回以上行ったか を添字に持って操作Cの最小回数を01BFSすると空間計算量・時間計算量ともに $O(H^2{W}^2)$ で解くことができます。操作Aの回数を空間ではなく時間の方向で持つことで空間計算量 $O(HW)$ に改善することができます。

感想

変なコーナーケースがある重実装として出題しましたが、変なコーナーケース部分に引っかかる人が想定より少なく、実装部分で落ちている人が想定より多かったです。

Try Average 6.35という大惨事です。

[PPC Lv.4] Lower Nim

問題はyukicoderにあります。
https://yukicoder.me/problems/no/3120

必勝判定として提案されていた問題にLSBによる最善手を提案してインタラクティブにしました。

ヒントと意図

ヒント1

このゲームは Nim という有名なゲームに条件をつけたものです。
Nimの必勝法を調べましょう。

Nimの必勝法構成にたどり着いてbit演算との関連性を疑うことを想定しています。

ヒント2

Nimと同様に、このゲームにおいても、次の命題が成立します。

• 数列 $A$ の総xor が $0$ $⟺$ 後手必勝

一方で、 Nim の必勝法をそのまま用いることはできません。
Nimの必勝法がどのようにして最適性を保証しているかを考えましょう。

Nimの必勝法構成である「総xorを0にする」を提示し、この問題もそのアイデアの応用で解けることを匂わせます。
ここから「ある桁以下の総xorを0にする」に辿り着けばこの問題も解けます。私が解法を提案したときは実際にこの手順で思いつきました。

想定解法

数列 $A$ の総xorが$0$のときは相手に先手を取らせます。
それ以降は数列 $A$ の総xorのLSBを選択し続けることで勝てます。

Nimにおいて$x$個の石を取ったとき、総xorのLSB($x$)の桁は必ず変化するという性質があります。二進法で扱っているので、変化した先は一意に定まります。
元々 $0$ だった桁は $1$ に変化します。

$x$を数列の総xorのLSBとして操作すると、数列の総xorのLSBがより大きい桁になります($0$のLSBは$+\infty$と考えます)。$K$は$x$で更新されているため、次の相手の操作でとる石の数のLSBは必ず数列の総xorのLSBより小さくなります。
数列の総xorのLSBより小さい桁は全て$0$であるため、操作によって$0$→$1$の変化があります。
以下、相手がLSBについて$0$→$1$の変更をし、自分がLSBをとって同じ桁について$1$→$0$の操作をし続けることで自分が勝利できます。

この「$K$以下を選ぶときにLSBをどこにできるか」を考えれば、初期状態で$K$が$100$など小さい場合についても必勝手順を構成できます。

感想

必勝判定については上位互換であるDecreasing Modulo Nimが出題されていたことが発覚したのですが、この問題の解説では具体的な必勝手順のLSBによる構成については触れられていませんでした。具体的な構成が出題されていないなら、Let's Play Nim!のように「必勝判定はみんな知っているけど具体的な構成はちょっと難しい」枠でもいいので出題しました。

既出は一瞬でバレましたが、具体的な必勝法を構成する部分も難しいと思うので耐えたと信じています。

LSBを操作するという非常に綺麗な戦略が最適で、制約が小さいので全ての山について愚直に操作可能か調べる実装が通ります。
考察メインの軽実装枠だと思って順位表を眺めていたらめちゃくちゃな惨状になっていてびっくりしました。インタラクティブ問題のデバッグのしにくさは恐ろしいですね。

[PPC Lv.4] Reversible Tile

問題はyukicoderにあります。
https://yukicoder.me/problems/no/3117

制約設定

この問題も原案が投げられたものを解く形で作られました。

時間$O(NM)$はすぐにわかり、行列累乗で$O(N^3\log M)$だけどそれより先がわからないな〜と思っていたら $O(N^2+N\log N\log M)$ が提案されました。このレベルの考察に対して高度な知識の必要な高速化を要求して面白いかという話になったので考察部分だけを要求する $O(NM)$ での出題になりました。

感想

難易度評価がわかりません。
One Power One Kill,Increment or Multiplyよりは簡単だと思ってかなり前の方に置くように提案したのですが、全然違いましたね。

[Crypto Lv.5] One More PPC Problem

作問動機

競技プログラマなら憧れるシチュエーションがあると思います。その中の1つがこれです。

最初の67個の入力から乱数のシードをハックして残り全ての出目が分かる(は？)

乱数を特定して問題を破壊しましょう。

問題概要

netcatでアクセスして解く問題です。

from secrets import randbelow

m = 80701148760020250419  # prime
a = 20250418
b = 240240240240

MAX_N = 10**5
MAX_Q = 100


class myRand:
    def __init__(self):
        self.v = randbelow(m)

    def random(self):
        self.v = (a*self.v+b) % m
        return self.v


def genCase(h, w, rd):
    A = [[rd.random() % MAX_N+1 for _ in range(w)] for _ in range(h)]
    A[rd.random() % h][rd.random() % w] = 0
    return (A, h, w)


def judge(case):
    A, H, W = case
    cnt = 0
    x, y = 0, 0
    print(f"{H} {W}")
    while cnt < MAX_Q:
        cnt += 1
        op = input()
        if op == '>':
            y += 1
        elif op == '<':
            y -= 1
        elif op == '^':
            x -= 1
        elif op == 'v':
            x += 1
        else:
            print("Invalid Input")
            return False
        if x >= 0 and x < H and y >= 0 and y < W:
            print(A[x][y])
            if A[x][y] == 0:
                return True
        else:
            print("Out of Stage")
            return False
    print("Query Over")
    return False


def main():
    r = myRand()
    caseHW = [(5, 5), (10, 10), (50, 50), (50, 50), (50, 50),
              (50, 50), (50, 50), (50, 50), (50, 50), (50, 50), (50, 50)]
    for i in range(len(caseHW)):
        h, w = caseHW[i]
        case = genCase(h, w, r)
        if not judge(case):
            print(f"WA on Case {i}")
            exit(0)
    print("AC!")
    with open("flag.txt") as f:
        print(f.read())
    exit(0)


if __name__ == '__main__':
    try:
        main()
    except:
        print("Judge Error")
        exit()

ランダムな値が書かれた二次元グリッドがあります。
ランダムなグリッドがゴールとして選択されるので、移動100回以下でゴールしてください。
最初は$5\times 5$や$10\times 10$の小さいグリッドですが、最後は$50\times 50$のグリッドで$9$連続成功しなければなりません。
$50\times 50$で開始位置は角のため、ゴールまでほぼ最短経路で進まないとクリアできません。
ゴールの座標はランダムなのでこの問題は正解できません。

ヒントと意図

ヒント1

chal.pyがどのような動作をしているか解説しています。
また、この問題の目標が「乱数を予測する」であることを提示しています。
問題の初手として脆弱性の存在する位置を示し、検索などで何かしら情報が得られることを期待しています。

ヒント2

線形合同法mod m について、実際にテストケースから得られる値と線形合同法の生成に用いられる値の関係式からテストケースで得られる値同士の関係式を提示しています。

数列$\{k_i\}$を提示しており、「剰余の方程式を解いて小さい数を求める」という構造を匂わせています。
LLLを知っている人にピンとくることを期待しています。

想定解法

この問題のテストケース生成では 線形合同法で生成した値を $N_{\max }$ で割ったあまりが使われています。この値は問題で指定された操作で確認することができるので、ここからあまりをとる前の値を復元します。
復元に成功すればゴールの座標の乱数が特定できるので最短経路での移動が可能になります。

線形合同法の関係式

線形合同法では　$A_{i+1}=(a\times A_i+b)\%m$ という漸化式により乱数を生成します。

問題では、生成した乱数列 $A_1,A_2,\cdots ,A_n$ を定数 $N_{\max }$ で割ったあまり $v_i$ をテストケース生成に使用しています。

$N_{\max }$ で割ったあまりをとる操作は $N_{\max }$ を何回か引くことに対応します。引く回数を $k_i$ とします。

$v_i=A_i-k_i{N}_{\max }(k_i\ge 0)$ という式が成り立ちます。

$A_i$ の漸化式を $v_i$ で表すことで次の式が得られます。

$$v_{i+1}+k_{i+1}{N}_{\max }\equiv a(v_i+k_i{N}_{\max })+b(\mathrm{mod}m)$$

これを変形すると

$$v_{i+1}-b-a{v}_i\equiv a{k}_i{N}_{\max }-k_{i+1}{N}_{\max }$$

このように非負整数列 $\{k_i\}$ の隣接項についての $\mathrm{mod}m$ での関係式が複数得られます。

関係式の左辺は問題の指示通りに移動することで得られる情報から計算できる既知の値なので、 $c_i=v_{i+1}-b-a{v}_i$ とまとめます。

この条件式を満たす数列 $\{k_i\}$ を探します。そのような数列は複数存在しますが、 $k_i<m/N_{\max }$ であることから大きな $k_i$ が存在するような数列は条件を満たしません。 $k_i$ がある程度小さい数列を構成します。

これを、複数のベクトルを整数結合で簡約しノルムの小さいベクトルを得るアルゴリズムであるLLL基底簡約を用いて解きます。

$\{k_i{\}}_{i=1}^n$ を求める

小さいテストケースでいくつかの連続する $\{c_i{\}}_{i=1}^{n-1}$ を求めておきます。20個得られれば十分です。
次のように $2n\times 2n$ 行列 $B$を構成します。

$$\left(\begin{array}{ccccccccc}0& 0& \cdots & 0& c_1& c_2& \cdots & c_{n-1}& L\\ 1& 0& \cdots & 0& -a{N}_{\max }& 0& \cdots & 0& 0\\ 0& 1& \cdots & 0& N_{\max }& -a{N}_{\max }& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& 0& 0& \cdots & -a{N}_{\max }& 0\\ 0& 0& \cdots & 0& m& 0& \cdots & 0& 0\\ 0& 0& \cdots & 0& 0& m& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 0& 0& 0& \cdots & m& 0\end{array}\right)$$

$1$ 行目はノルムを最小化したいベクトルです。この行の右側の $c_i$ を基底簡約によって $0$ にしたとき、左側に $k_i$ があることが期待されます。
このベクトルが他のベクトルの簡約に使われると $k_i$ の復元が面倒になるため、 $B_{1,2N}$ に非常に大きな定数 $L$ を置いてこのベクトルが簡約に使われないようにします。

$2$ 行目から $n+1$ 行目は $k_i$ を生成するためのベクトルです。
$B_{i+1,i}$ が $k_i$ への寄与を表し、$B_{i+1,n+i},B_{i+1,n+i+1}$ で$c_{i-1},c_i$ への寄与を表します。

$n+2$ 行目以降は関係式が $\mathrm{mod}m$ 上であることを考慮したベクトルです。 $1$ 行目のノルム最小化において、 $\pm m$ をコストなしで行えるようにします。

実際には $c_i$ を $0$ にするために、 $c_i$ の影響力を大きくするために大きな定数 $K$ を掛けた次の行列を用います。

$$\left(\begin{array}{ccccccccc}0& 0& \cdots & 0& c_{1}K& c_{2}K& \cdots & c_{n-1}K& LK\\ 1& 0& \cdots & 0& -a{N}_{\max }K& 0& \cdots & 0& 0\\ 0& 1& \cdots & 0& N_{\max }K& -a{N}_{\max }K& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& 0& 0& \cdots & -a{N}_{\max }K& 0\\ 0& 0& \cdots & 0& mK& 0& \cdots & 0& 0\\ 0& 0& \cdots & 0& 0& mK& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 0& 0& 0& \cdots & mK& 0\end{array}\right)$$

以上で構成された行列に格子基底簡約を行うことで $1$ 行目に対応するベクトルから $k$ が特定できることが期待されます。 $1$ 行目に対応するベクトルは定数 $L$ の存在から次のような形になっているため、これで $k_i$ が特定でき、そこから線形合同法の元の値 $A_i$ が計算できます。

$$\left(\begin{array}{ccccccccc}{k}_1& k_2& \cdots & k_n& 0& 0& \cdots & 0& LK\end{array}\right)$$

$0\le k_i\le m/N_{\max }$ を得たいですが、この行列では情報量(数列$v_i$の長さ)が不十分だと簡約後のベクトルに $k_i<0$ が混ざることがあります。
$\frac{m/N_{\max }}{2}$だけ平行移動することでノルム最小化が$k_i$の特定という目的に合致し、少ない情報量で正確な結果を得られることが期待できます。
具体的には次のような行列を基底簡約します。

$$\left(\begin{array}{ccccccccc}-\frac{m/N_{\max }}{2}& -\frac{m/N_{\max }}{2}& \cdots & -\frac{m/N_{\max }}{2}& c_{1}K& c_{2}K& \cdots & c_{n-1}K& LK\\ 1& 0& \cdots & 0& -a{N}_{\max }K& 0& \cdots & 0& 0\\ 0& 1& \cdots & 0& N_{\max }K& -a{N}_{\max }K& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& 0& 0& \cdots & -a{N}_{\max }K& 0\\ 0& 0& \cdots & 0& mK& 0& \cdots & 0& 0\\ 0& 0& \cdots & 0& 0& mK& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 0& 0& 0& \cdots & mK& 0\end{array}\right)$$

この行列を簡約すると次のようなベクトルを得ることが期待できます。

$$\left(\begin{array}{ccccccccc}{k}_1-\frac{m/N_{\max }}{2}& k_2-\frac{m/N_{\max }}{2}& \cdots & k_n-\frac{m/N_{\max }}{2}& 0& 0& \cdots & 0& LK\end{array}\right)$$

ここから$k_i$を復元できます。

実装には SageMathのMatrix.LLLが利用できます。
$A_1=v_1+k_1{N}_{\max }$ です。
以上で線形合同法で生成された値を1つ得られました。値が1つあればこれ以降に生成される乱数は全て計算できるため、この問題に正解することができます。

from secrets import randbelow
from pwn import remote, process
io = remote(~~)

H, W = map(int, io.recvline().decode().split())
x, y = 0, 0
while 1:
    if y % 2 == 0:
        if x+1 < H:
            x += 1
            io.sendline(b">")
            c = int(io.recvline().decode())
            if c == 0:
                break
        else:
            y += 1
            io.sendline(b"v")
            c = int(io.recvline().decode())
            if c == 0:
                break
    else:
        if x-1 >= 0:
            x -= 1
            io.sendline(b"<")
            c = int(io.recvline().decode())
            if c == 0:
                break
        else:
            y += 1
            io.sendline(b"v")
            c = int(io.recvline().decode())
            if c == 0:
                break
H, W = map(int, io.recvline().decode().split())
A = [0]*20
for i in range(W-1):
    io.sendline(b">")
    c = int(io.recvline().decode())
    if c == 0:
        print("Uwa...") # 必要数のデータを取る前にクリアしてしまった
    A[i] = c-1
io.sendline(b"v")
c = int(io.recvline().decode())
A[18] = c-1
for i in range(W-1):
    io.sendline(b"<")
    c = int(io.recvline().decode())
    if c == 0:
        print("Uwa...") # 必要数のデータを取る前にクリアしてしまった
    A[17-i] = c-1
io.sendline(b"v")
c = int(io.recvline().decode())
if c == 0:
    print("Uwa...") # 必要数のデータを取る前にクリアしてしまった
A[19] = c-1
print(A)

m = 80701148760020250419  # prime
a = 20250418
b = 240240240240

MAX_N = 10**5
MAX_Q = 100

N = 20
K = 10 ^ 43
L = 10 ^ 100
T = m//MAX_N//2
B = [[0 for _ in range(N*2)] for _ in range(N*2)]
for i in range(N-1):
    B[N][N+i] = (A[i+1]-b-a*A[i])*K
# これの係数が1以外にならないようにする
B[N][2*N-1] = L
for i in range(N-1):
    B[N+1+i][N+i] = m*K

for i in range(N):
    B[i][i] = 1
    if i > 0:
        B[i][N+i-1] = MAX_N*K
    if i < N-1:
        B[i][N+i] = -a*MAX_N*K

for i in range(N-1):
    if i > 0:
        B[N][N+i-1] += MAX_N*K*T
    if i < N-1:
        B[N][N+i] -= a*MAX_N*K*T
BL = matrix(B).LLL()
A2 = []
for i in range(N*2):
    if BL[i][2*N-1] == L:
        A2 = [(BL[i][0]+T)*MAX_N+A[0]]
        break
    elif BL[i][2*N-1] == -L:
        A2 = [(-BL[i][0]+T)*MAX_N+A[0]]
        break

for i in range(N-1):
    A2.append((A2[-1]*a+b) % m)
for i in range(N):
    assert A2[i] % MAX_N == A[i], i


class myRand:
    def __init__(self, iv):
        self.v = iv

    def random(self):
        self.v = (a*self.v+b) % m
        return self.v


A2 = A2[:1]
r = myRand(A2[0])
for i in range(H*W-2):
    A2.append(r.random())

ansH = r.random() % H
ansW = r.random() % W

x, y = 0, 2
while ansW < x:
    x -= 1
    io.sendline(b"<")
    io.recvline()
while ansW > x:
    x += 1
    io.sendline(b">")
    io.recvline()
while ansH > y:
    y += 1
    io.sendline(b"v")
    io.recvline()
while ansH < y:
    y -= 1
    io.sendline(b"^")
    io.recvline()


for i in range(9):
    H, W = map(int, io.recvline().decode().split())
    x, y = 0, 0
    for i in range(H*W):
        r.random()
    ansH = r.random() % H
    ansW = r.random() % W
    x, y = 0, 0
    while ansW < x:
        x -= 1
        io.sendline(b"<")
        io.recvline()
    while ansW > x:
        x += 1
        io.sendline(b">")
        io.recvline()
    while ansH > y:
        y += 1
        io.sendline(b"v")
        io.recvline()
    while ansH < y:
        y -= 1
        io.sendline(b"^")
        io.recvline()
for i in range(2):
    print(io.recvline().decode(), end="")

おわりに

今回のCPCTF 2025 : PPCはyukicoder上で353人参加となっていました。前回は158人参加だったので2倍以上ですね。多くの人に問題を解いていただきとても嬉しいです。難易度投票もよろしくお願いします。

今回はCryptoにも問題を1つ出すことができました。次回は暗号パズルとかブロック暗号とかもっとCryptoを作りたいですね。

参加していただいたみなさま、PPCのジャッジとして使わせていただいた yukicoder 様、スポンサーの 株式会社いい生活 様、株式会社フィックスターズ 様ありがとうございました。