CPCTF 2023 に参加しました

結果

チーム参加。3位/131チーム

解けた問題(ジャンル別問題掲載順)

PPC

• Find cpctf (33 solves)
• Floor Sqrt (34 solves)
• Geometric Progression Sum (24 solves)
• Whisper Sucu (24 solves)
• Digital Clock (12 solves)
• Max Min GCD (14 solves)
• Move Road (13 solves)

OSINT

• Dokoda? 3 (46 solves)

Crypto

• Entrance to the Crypto World (61 solves)

PPC

Find cpctf (33 solves)

頭から見ていって、 cpctf にできないか調べる。事前に $A_i = x$ の数を数えておくことで、高速に求めることができる。

Floor Sqrt (34 solves)

実験すると、条件を満たす数は平方数から連続するので、 $n$ 以下の平方数を $low$ として、二分探索を毎回行って終点を探す。

Geometric Progression Sum (24 solves)

加算する部分をimos法のような感じで表現できるので、その性質を活用する。

Whisper Sucu (24 solves)

$（今いる頂点、今いる時間の偶奇）$ で頂点を作り、ダイクストラをする。

Digital Clock (12 solves)

$H, W$ は $H > W$ としてよい。下図のようなものを書いてると、結局 $(H, W) = (x, 0)$ となる部分にのみ注目すればよいことがわかる。

答えは

$$\begin{align} min( k + 1, \lfloor \frac{H}{gcd(h, h - m)} \rfloor \times m) \end{align}$$

となる。

Max Min GCD (14 solves)

$C_k = min(gcd(A_k, B_i), gcd(A_i, B_k)) (i = k, k + 1, \cdots, N)$ とよみかえることができるので、それぞれの場合について考える。また、 $max(gcd(A_k, B_i))$ は、$max(gcd(A_k,（B_i, B_{i + 1} \cdots B_Nの約数）))$ と言い換えることができる。 $i$ を後ろから見ていき、 $A_k$ の約数と同じ約数がすでに出現しているかどうかを探せばよい（ぼくはsetで管理した）。 $O(N \sqrt{N} \times \log{N})$

Move Road (13 solves)

車がズレるのを考えるのは大変なので、自分がズレることを考える。すると、以下のように言い換えることができる。あとはdfsをすればよい。

OSINT

Dokoda? 3 (46 solves)

これはどこで撮られた写真でしょう?

交番に絞って画像検索を書けたら東大のそばの交番が出てきた。いろんなアングルを検証してみても、やっぱりこれだった。

Crypto

Entrance to the Crypto World (61 solves)

CJ, YGNEQOG. JQY FKF AQW NKMG VJKU UKORNG UWDUVKVWVKQP EKRJGT? YKVJ C NKVVNG KPIGPWKVA, UWEJ C UWDUVKVWVKQP EKRJGT ECP DGEQOG C XGTA FKHHKEWNV EKRJGT. QPG GZCORNG KU VJG GPKIOC ETGCVGF DA VJG IGTOCPU. YJA FQP'V AQW EJGEM KV QWV? PQY, JGTG KU VJG HNCI. EREVH{3PL0A_7J3_Y0TNF_0H_ETAR70!}

メンバーから「これはシーザー暗号だ」と言われて回ってきた。 CyberChefに投げて復元してもらった。

upsolveしたい問題

• [PPC]God Field (13 solves)
  • 普通にめちゃくちゃ悩んだ上にヒントも2つ開けたんだけど、さっぱりわからず。にもかかわらず、執筆時点で見たwriteupはどれも「やるだけ～」みたいな雰囲気を感じてて怖い。MMRZは丁寧な解説を求めています。
• [Crypto]Simple (6 solves)
  • 実はPPC以外にもこれだけは時間をかけて取り組んでいました。 $p, q$ がわかったのに時間切れになってしまった。

感想

問題文はどれも簡潔で、そして面白かった。

「競プロとCTFの複合コンテストとか俺得じゃん」と思いながら意気揚々とPPCを解いていたのだけど、しばらくしているうちに他メンバーがほとんどの解けそうなCTFを解きつくしてて、結局ほぼ6時間競プロをするだけの人になってた。

CTFerの方々は普段からPPCの存在に悩まされてるからか、「PPCが多い！！」と言っていたけど、逆の意見が無かったのはちょっと界隈の違いを感じて面白かった。最終的な順位を見てみると、「競プロ専」「CTF専」「バランスタイプ」のどれもいい感じの順序になっている気がして、準備の完璧具合に感動すら覚えた（のがコンテスト終了直後の感想なんだけど、いま改めてみるとCTF専は上位にはあまり多くないのかも？）。

それと、オリジナルのジャッジサーバーなのに軽快で、インフラ力を感じた（SUGOI）。