feature image

2023年5月4日 | ブログ記事

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

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

自己紹介

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

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

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

結果

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

pwn

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

Big or Small

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

overrun

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

misc

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

welcome to CPCTF

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

PPC

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

Count Coins

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

Transfer

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

Find cpctf

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

Floor Sqrt

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

Geometric Progression Sum

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

Whisper Sucu

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

Digital Clock

まず、操作は回行うことができに割り振る方法は回あります
また、の座標の任意の頂点からの方向に進んでいくと回で同じ位置に戻ってきます。なので最大でも通りしか作ることができません。
よって答えはになります

God Field

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

MaxMinGCD

を入れ替えた時の結果と最大値を取ることで求めたい答えを得ることができるのでここではである時を考えます。
この時の約数のうちの約数に含まれているものの最大値のことです。なので、上から順にの約数に含まれるの集合を持ちその集合に含まれるの約数の最大値を求めることでこの問題を解くことができます。
また、以下の高度合成数はでその約数の数は64であるのでこの問題を十分高速に解くことができます

Move Road

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

HopStepJump

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

Lost Array

この問題を見た際にからを求める行列累乗の式が頭の中をよぎります。
行列累乗を用いてとなるを求めることができるのでこれを用いてを求めていきます。
である時、逆元が存在するのでを満たすが一つ存在します。よってであるのうち最大のもの以外をにしてとすることで辞書順最小のを求めることができます。
また、このようなが存在せずである時答えは存在しないのでnoを出力します
本番中は前日に作りたてほやほやの行列累乗ライブラリ(問題をまだ1問も解いてない)を使い、案の定オーバーフローを起こしてしまい通すことができませんでした。皆さんは作ったライブラリは本番で使う前に一度、他の問題でバグがないかどうか確かめるようにしましょう(当たり前)

Mex Max Matrix

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

一番左の列がA、一番上の列がBを表している

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

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

最後に

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

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

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

Ponjuice icon
この記事を書いた人
Ponjuice

競プロer AtCoder:A橙,H黄

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2021年8月12日
CPCTFを支えたWebshell
mazrean icon mazrean
2021年5月19日
CPCTF2021を実現させたスコアサーバー
xxpoxx icon xxpoxx
2021年5月16日
CPCTFを支えたインフラ
mazrean icon mazrean
2019年4月22日
アセンブリを読んでみよう【新歓ブログリレー2019 45日目】
eiya icon eiya
2023年4月29日
CPCTF2023 PPC作問陣 Writeup
noya2 icon noya2
2023年4月21日
CPCTFを開催します
noc7t icon noc7t
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記