nkhrlab~

280字超の記事

勝敗グラフと有向閉路の存在性

グラフ アルゴリズム

勝敗グラフ

本記事における勝敗グラフを次のように定義する．勝敗グラフは有向グラフの一種である．

頂点集合 V，辺集合 Aを持つ有向グラフ G = (V, A)を考える．
i, j \in Vに対し a_{i, j}を次のように定義する．
a_{i, j} = \begin{cases} 1 & \left((i, j) \in A\right) \\ 0 & \left((i, j) \notin A\right) \end{cases}.

Gが次に示す条件を満たすとき，かつその場合に限り， Gは勝敗グラフである．
\forall i, j \in V, a_{i, j} + a_{j, i} = \begin{cases} 0 & \left(i = j\right) \\ 1 & \left(i \neq j\right) \end{cases}.

本記事の主張

次の命題は勝敗グラフGが有向閉路を持つことの必要十分条件である．
\exists i, j, k \in V, a_{i, j} + a_{j, k} + a_{k, i} = 3.

続きを読む

AtCoder に登録したら解くべき精選過去問 10 問を PostgreSQL で解いてみた

競技プログラミング AtCoder AtCoder Beginners Selection SQL PostgreSQL アルゴリズム

はじめに

この記事は，次のQiita記事に「過去問精選 10 問！」として示されている10問の問題をPostgreSQLを用いて解いたものである．
qiita.com

また，AtCoderではこれらの問題をまとめた初心者向け問題集として「AtCoder Beginners Selection」を用意している．

問題

これらの問題では，PostgreSQLで標準入出力を取り扱うことが困難であるため，入力は共通表式(WITH句)を用いていくつかのテーブルとして与え，出力もまたテーブルとするよう，問題を変形している．

また，各問題の解答方針についての解説はすでに公式に公開されているため，本記事では解答方針についての解説を詳しく行うことはせず，主にSQL特有の事情についての解説を中心とする．

0. PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

問題文の冒頭に「高橋君はデータの加工が行いたいです。」とあるが，SQL(DML)はすでに構造化されたテーブルデータの操作を行うために作られた言語であり，未だ構造化されていない段階のデータを取り扱うのは容易ではないため，この冒頭のみで「はじめてのあっとこーだー」というには難易度の高い問題であることが予感される．果たしてその予感は的中するのだ．

テーブルtblに，標準入力の文字列と「何行目に入力された文字列か」という情報を与える．テーブルは順序を保持しないため何行目であるかの情報が必要である．解答には，テーブルtbl内の情報から必要な部分の文字列を正規表現を用いて切り出し，数値に変換する操作と，文字列の結合操作が必要である．

WITH tbl(num, str) AS
(
  VALUES
  (1, '72'),
  (2, '128 256'),
  (3, 'myonmyon')
)
SELECT
  (
    TO_NUMBER((SELECT str FROM tbl WHERE num = 1), '9999') +
    TO_NUMBER(SUBSTRING((SELECT str FROM tbl WHERE num = 2) FROM '^.*\ '), '9999') +
    TO_NUMBER(SUBSTRING((SELECT str FROM tbl WHERE num = 2) FROM '\ .*$'), '9999')
  )::TEXT ||
  ' ' ||
  (SELECT str FROM tbl WHERE num = 3) AS result
続きを読む

HarekazeCTF2018: [Misc 127]Unnormalized-form Data 想定解法

CTF HarekazeCTF PostgreSQL Writeup SQL

この記事について

本記事は，HarekazeCTF2018に私が出題した問題 [Misc 127]Unnormalized-form Data の想定解法について解説を行うものである．HarekazeCTF2018の期間中に43チームが本問題のフラグを獲得した． harekaze.com

問題文

Unnormalized-form data is troublesome.

解法

配布された unf.zip を展開して，2つのファイルを得る．

  • operation.txt
  • unf.sql

operation.txt の観察

operation.txt は次のような内容である．

$ sudo nano postgresql.conf
$ sudo /etc/init.d/postgresql reload
[ ok ] Reloading postgresql configuration (via systemctl): postgresql.service.
$ psql -U postgres -c "CREATE DATABASE unf"
CREATE DATABASE
$ psql -U postgres -d unf < unf.sql >> /dev/null
$ psql -U postgres -d unf -c "SELECT FLAG()"
             flag
-------------------------------
 HarekazeCTF{****************}
(1 row)

$

この記述はフラグの取得までの手順を示している．

続きを読む

CTFサーバとの自動対話

CTF Ruby

CTFでは指示されたサーバに接続して問題を解くことがよくある．例えば次のようにnetcatを利用した接続の方法が示される問題はその典型である．

nc 192.168.61.74 6174

しかしながら，このコマンドを実際に端末で実行してサーバと対話的に通信しても問題が解けない場合がある．例えば，サーバとの接続に時間制限があり，しかもその時間が問題を解く人にとってあまりに短い場合がこれに当てはまる．

例えば，サーバから送られてくる1以上1000以下の2つの整数の掛け算20題を10秒以内に計算する問題が出題されたとしよう．この場合は，人が暗算で問題を解き，キーボードを使って解答を送信するという一連の操作20題分を10秒以内で行うことはほとんど不可能であると考えられる．

このような問題を解くにあたって，サーバとの対話的通信を自動的に行うクライアントを作成することが有効である．また，サーバからのデータの代わりに標準入力のデータをクライアントに与えることができれば，クライアントの動作の検証も容易である．

そこで，この記事では2つの整数の掛け算20題を計算する問題を出題するサーバスクリプト，これに対応したサーバとの自動対話および標準入力による動作確認が行えるクライアントスクリプトを紹介する．

続きを読む

Tokyo Westerns CTF 3rd 2017(2017/9/2 - 2017/9/4) - Writeup

Writeup CTF セキュリティ

チーム「Harekaze」のメンバーとしてCTF「Tokyo Westerns CTF 3rd 2017」に参加した．チームは940点を獲得し33位となった．個人では2個のフラグを得ることができたので，Writeupを書く．

[PPC 24]Palindromes Pairs - Coding Phase -

空白区切りで与えられる文字列のリストに対して，そのうちの2個を取り出し結合したものが回文となる組み合わせがいくつあるかを答える問題．文字列のリストの大きさは高々50という制約のため，すべての組み合わせをしらみつぶしに調べても高々2500個の組み合わせを調べればよいことが明らかで，これは十分に短い時間で実行可能である．そこで，素朴な方法を実装した次のRubyスクリプトを作成した．

続きを読む

無向グラフに関する頂点数・染色数制約下での辺数の最大化

グラフ アルゴリズム

この記事で扱う問い

無向グラフ G = (V, E)の染色数を \chi(G)と表すとき，グラフ Gに対する頂点数についての制約 |V| = mおよび染色数についての制約 \chi(G) = nを同時に満たす無向グラフのうちで，辺数が最大であるものはいかなるグラフであろうか．ただし， 2 \leq n \leq m.

特殊な m, nに対する答え

まず，特殊な m, nについて考えよう．

m = 7, n = 2について考える*1．すると，この問題は「頂点数 7，染色数 2である無向グラフ G = (V, E)のうち，辺数最大なるグラフとはどのようなものか？」という問いになる．

染色数が 2であるから，グラフ Gの頂点集合 Vはちょうど 2個の独立集合への分割 S \in 2^{2^V}, S = \{S_1, S_2\}をもつはずである．さらに， |S_1| = x_1, |S_2| = x_2とおくと，制約を満たすグラフのうち辺数が最大となる Gについて，辺数は x_1, x_2のみによって決まる．まずはこのことを確認しよう．

*1:この m, nの組み合わせに対する問題は大学院の入学試験でも出題例がある．

続きを読む