CPCTF2023で新入生内優勝しました！

チーム「poraken」としてkenken,ramdos,mapleと一緒に参加して新入生内１位、総合２位という良い結果を残せたので自分の解いたところを中心に書いていこうと思います。

自己紹介

23Bのぽんじゅーすです。ここでは、CPCTFに関係のありそうな経験について書いていきます

競プロ： AtCoderを高２年生の終わり頃からゆるーくやってます。現在は黄色です。

CTF ： CPCTFが開催されることを聞いて３日前くらいからのんびり始めました。ほぼ初心者です。

結果

合計得点5313.95で新入生内優勝できました！（わーい！！！）
自分の貢献度は5313.95点中433.42点でした（チームのみんな強すぎない????）

考察した問題がpwn2問、misc1問、PPC2問と少なめなので他のPPCの問題も解いてきて書いていこうと思います

pwn

よく競プロでバグを生み出しては書いたコードを読みなおす人なのでバグを見つけるのは得意です！

Big or Small

負の数かどうか受け取った時に確認されていないので適当な負の数を与えて負けます。すると入力した分だけお金を失うことができるので大金を得ることができます

overrun

このような文字列を受け取るような問題では"%p"か適当な長い文字列を与えておけばバグるというpicoCTFで事前に学んだ数少ないことを試してみたところflagが出てきてくれました（助かる）

misc

元々は他の人が担当していたのですが、途中時間が余っていたので１問だけ担当しました

welcome to CPCTF

チームメイトが前二つを見つけてくれており、残りはビジュアライザのところにあるということでビジュアライザを開き色々なところをぽちぽちクリックしていると見つかりました

PPC

CPCTF開催中に考察した問題はHopStepJumpとLostArrayの２問のみと少なめなので、他の問題も解いてきました

Count Coins

各イベントを書いてある通りに実行することによってN回目のイベントが終わった時のコインの枚数がわかります

Transfer

各駅停車の電車に乗った時と急行の電車に乗った時の到着する時間をそれぞれ求めてより早くついたほうが答えになります

Find cpctf

全ての位置に対してcpctfにすることが可能かどうかを調べれば良いです

Floor Sqrt

このように $⌊ N ⌋$ が出でくる問題では大体 $⌊ N ⌋ = M$ である時の条件を満たしているものの数がO(1)で出ることが多いのでそれを試してみます。すると $M^{2}$ から $M^{2} + M - 1$ までが条件を満たしていることがわかるのでそれぞれの $M$ について求めていくことで答えが出ます

Geometric Progression Sum

Q回の操作した後の答えがわかれば良いのでimos法を用いて計算することができます。隣に遷移するときにX倍するimos法であることに注意します

Whisper Sucu

各頂点ごとに偶数回目に到達する時の最短距離と奇数回目に到着する時の最短距離を持てば良いので頂点を二倍にしたBFSで解くことができます

Digital Clock

まず、操作は $K$ 回行うことができ $H, M$ に割り振る方法は $K ＋ 1$ 回あります
また、 $(x mod H, y mod M)$ の座標の任意の頂点から $(- 1, 1)$ の方向に進んでいくと $l c m (H, M)$ 回で同じ位置に戻ってきます。なので最大でも $l c m (H, M)$ 通りしか作ることができません。
よって答えは $min (K + 1, l c m (H, M))$ になります

God Field

dp[何番目の攻撃まで見たか][使った防具の集合]で残りHPの最大値を持つことで状態数が $M 2^{N}$ で遷移にそれぞれ $O (2^{N})$ かかるのでこの問題を $O (M 2^{2 N})$ で解くことできます

MaxMinGCD

$A, B$ を入れ替えた時の結果と最大値を取ることで求めたい答えを得ることができるのでここでは $i \leq j$ である時を考えます。
この時 $i \leq j \leq n ma x (g c d (A_{i}, B_{j}))$ は $A_{i}$ の約数のうち $B_{j}$ の約数に含まれているものの最大値のことです。なので、上から順に $B_{j}$ の約数に含まれるの集合を持ちその集合に含まれる $A_{i}$ の約数の最大値を求めることでこの問題を解くことができます。
また、 $1 0^{5}$ 以下の高度合成数は $7560$ でその約数の数は64であるのでこの問題を十分高速に解くことができます

Move Road

車を右に動かすことを考えるとだいぶ計算量が悪くなりそうなのでSotatsu君が移動すると同時に左に一マス移動するというふうに考えます。すると、この問題を普通のBFSの問題と見ることができます。この時、移動するマスの一つ右のマスに一度移動していることに注意します

HopStepJump

本番中めっちゃ誤読して１時間ほど無駄にしました。またその後、解くことができずに解説を見て通しました。FPS的な発想の問題、めっちゃ苦手です...勉強しないとだなぁ

Lost Array

この問題を見た際に $A_{1}, ..., A_{K}$ から $Y$ を求める行列累乗の式が頭の中をよぎります。
行列累乗を用いて $C_{1} A_{1} + C_{2} A_{2} + \dots + C_{K} A_{K} \equiv Y mod p$ となる $C$ を求めることができるのでこれを用いて $A_{i}$ を求めていきます。
$C_{i} \neq = 0$ である時、逆元が存在するので $A_{i} \equiv (Y - C_{1} X) / C_{i} mod p$ を満たす $A_{i}$ が一つ存在します。よって $C_{i} \neq \equiv 0 mod p$ である $i$ のうち最大のもの以外を $0$ にして $A_{i}$ を $(Y - C_{1} X) / C_{i} mod p$ とすることで辞書順最小の $A$ を求めることができます。
また、このような $i$ が存在せず $Y - C_{1} X \neq \equiv 0 mod p$ である時答えは存在しないのでnoを出力します
本番中は前日に作りたてほやほやの行列累乗ライブラリ（問題をまだ１問も解いてない）を使い、案の定オーバーフローを起こしてしまい通すことができませんでした。皆さんは作ったライブラリは本番で使う前に一度、他の問題でバグがないかどうか確かめるようにしましょう（当たり前）

Mex Max Matrix

問題を見ただけではどのような挙動になっているのかよくわからないので一度実験コードを書いてみてどのような感じの結果になるのかを試します。

すると面白いことに０の含まれる行や列以外ででは値が０になりそれ以外の列で撮る値は高々３種類しかないことに気が付きます。そこでどのような規則でこのような値を取るのかについて考察すると以下のようになっています。

$A_{i} \neq = 0 \cap B_{j} \neq = 0$ である時 $M_{ij} = 0$
$A_{i} > m e x (A) \cap B_{j} = 0$ である時 $M_{ij} = m e x (A)$
$A_{i} = 0 \cap B_{j} > m e x (B)$ である時 $M_{ij} = m e x (B)$
それ以外の時 $M_{ij} = m e x (A + B)$

これを累積和などを用いて実装することで各クエリに対して $O (1)$ で答えることができます

最後に

PPCのHARDを解答みないで通せたのが１問もなかったことがとても悔しいです。このおかげで大学ではもっと精進して頑張ろうというモチベが上がりました（やったね）

新入生内優勝まで導いてくれたチームの皆さんには感謝してます、ありがとうございます！！！

面白い問題をたくさんとけて満足してます。運営の皆さんもありがとうございました！！！