Ark's Blog

𝔇eadline-𝔇riven 𝔇evelopment

ようこそ

線形空間𝔽₂^V上の問題に対する連結グラフから全域木への帰着

連結無向グラフが与えられたとき、それが線形空間 \mathbb{F}_2^V上の問題であれば、連結グラフから全域木に帰着できるかもしれないという話です。着想は

の解説から得ました。想定解の一部に「連結グラフの問題を全域木の問題に帰着」している箇所があります。この記事は、これを数学的に理解するためのものです。

続きを読む

ContrailCTF 2019 writeup

ContrailCTF 2019 にチーム ./Vespiary として参加しました。結果は 1542 points で 9 位でした。

f:id:ark4rk:20200104014852p:plainf:id:ark4rk:20200104014858p:plain

以下は自分が解いた問題のwriteupです。3問解いて内訳はnetwork*1, web*2 です。

  • [network] debug_port (100pt)
    • 問題概要
    • 解法
    • フラグ
  • [web] LegacyBlog (100pt)
    • 問題概要
    • 解法
    • フラグ
  • [web] NoWallForUs (436pt)
    • 問題概要
    • 解法概略
    • 解法詳細
      • 1. サーバ側の構成を把握する
      • 2. サーバ内のファイルを入手する
      • 3. mysqlのパスワードを取得する
      • 4. mysqlに接続してフラグを奪取する
    • フラグ
  • 感想
    • ContrailCTF 全体に対して
    • NoWallForUs に対して
続きを読む

X-MAS CTF 2019 writeup

X-MAS CTF 2019 にチーム ./Vespiary として参加しました。結果は 4051points で 42 位でした。日本チームでは1位でした。

https://xmas.htsp.ro/homexmas.htsp.ro

f:id:ark4rk:20191223090933j:plainf:id:ark4rk:20191223090937j:plain

以下は自分が解いた問題のwriteupです。4問解いて内訳はmisc2, ppc1, web1です。

続きを読む

半環上の最大部分配列問題とKadane's algorithm

この記事はSunrise Advent Calendar 2019の9日目の記事です。

adventar.org

内容はごった煮ということなので、アルゴリズムと代数について書きます。

TL; DR

  • Kadane's algorithmと呼ばれる最大部分配列問題を O(n)で解くアルゴリズムがある。
  • このアルゴリズムはトロピカル半環上で動作する。
  • つまり、半環上に一般化できる!
続きを読む

IQが1なので任意のコマンドを実行するたびにSLが走る様子を眺めたくなった

この記事はIQ1 Advent Calendar 2019の3日目の記事です。

adventar.org

続きを読む