高速な楕円曲線法① 理論と手法編

この記事はCTF Advent Calender 2024の4日目の記事です。

昨日の記事はn01e0さんのSECCON 13 Quals - Jumpでした。作問ミスって怖いですね。カツカツスケジュールになってしまうのも作問ミスも他人事ではないので、襟を正してレビュー等をしようと思います。

この記事は元々はCryptoワザップと題して「400-bit程度の合成数までならノートPCで素因数分解できますよ〜、512-bit程度の合成数ならば5000円と数時間くらいで素因数分解できますよ〜」みたいなことを書こうとしていた記事でした。しかし、その一環で楕円曲線法について調べ出したらRabbit Holeに落ちてしまったので、楕円曲線法に限定した記事として公開することにしました。

本記事では、楕円曲線法のアルゴリズムを解説した後、楕円曲線法に適用される高速化のテクニックを紹介します。実装やソフトウェアの使用方法などには触れません。

記号・用語:

楕円曲線法の概要

まずは、簡単に楕円曲線法のアルゴリズムについて紹介します。楕円曲線法はp-1法やp+1法の原理を応用したアルゴリズムです。これらのアルゴリズムは pが計算量に大きな影響を与えるという特性があります。これは、計算量が nに大きく影響される二次ふるい法や数体ふるい法とは対照的です。そして、楕円曲線法はこれらのアルゴリズムのなかでも最も高い性能を持つアルゴリズムです。そのため、楕円曲線法は nの大きさに依存する素因数分解アルゴリズムである数体ふるい法などを適用する前処理として用いられます。他にも、数体ふるい法を適用できないような非常に大きな数を素因数分解するのに用いられたりもします。2024年現在、楕円曲線法で見つかった最大の素因数は7^337+1の素因数である274-bitの数です(ECMNET)。

p-1法やp+1法、楕円曲線法のアルゴリズムについては、以下の記事に分かりやすくまとまっています。

wacchoz.hatenablog.com

本記事でも、簡単にですが楕円曲線法自体について説明をします。

楕円曲線法は、 nの非自明な約数をランダムに発見する乱択アルゴリズムです。発見できる約数の大きさや約数を発見できる確率は、アルゴリズムに与えるパラメータによって変動します。以降では、説明の簡略化のためにアルゴリズムが成功した場合は素因数 pを発見するものとします*1。

以下は、高速化が行われていない教科書的な楕円曲線法の大まかな実装です。

def get_M(n, bound):
  m = 1
  # equivalent to: for i in range(1, bound): m = LCM(m, i)
  for p in primes(bound+1): # primes in [0, bound]
    k = floor(log(bound) / log(p)) # k such that p^{k} <= bound < p^{k+1}
    m *= p**k
  return m

def ecm(n, bound):
  E, P0 = get_random_elliptic_curve_and_point(N)
  m = get_M(n, bound)
  try:
    Q = m * P0
  except ModInvException as e:
    return gcd(e.value, n)
  return None

楕円曲線法では、まず \mathbb{Z}/n\mathbb{Z}上の楕円曲線（のようなもの*2） E(\mathbb{Z}/n\mathbb{Z})をランダムに生成します。アルゴリズムが素因数 pの発見に成功できるとして、 E(\mathbb{Z}/n\mathbb{Z})と同じパラメータの \mathbb{Z}/p\mathbb{Z}上の楕円曲線 E(\mathbb{Z}/p\mathbb{Z})を考えてみます*3。ここで、 P+Q=0_{E(\mathbb{Z}/p\mathbb{Z})}、つまり P=-Qになるような点 P,Qを見つけられたとします。このとき、元の E(\mathbb{Z}/n\mathbb{Z})で P+Qはどうなるでしょうか？楕円曲線の性質より、 P=(P_x, P_y)\equiv (Q_x, -Q_y)=-Q \bmod p が成立します。よって、 P_x\equiv Q_x \bmod pです。一方で、楕円曲線の加法公式には Q_x\neq P_xの場合に L:=\frac{Q_y-P_y}{Q_x-P_x}が係数として登場します。ほとんどの場合 \gcd(Q_x-P_x, n)=pなので、この Lは計算することができません。よって、 P+Qを満たす値は E上に存在しないことが分かりました。同時に、 P+Qを計算する過程で素因数 pを発見できていることも分かるかと思います。

ここまでの議論で、 E(\mathbb{Z}/p\mathbb{Z})で P+Q=0_E(\mathbb{Z}/p\mathbb{Z})となるような Pと Qを発見できれば、素因数 pを発見することができると分かりました。これは、加算ではなくスカラー倍でも同様の結論になります*4。つまり、 mP\equiv 0_{E(\mathbb{Z}/p\mathbb{Z})}を満たすような正整数 mと Pを発見することでも、素因数 pを発見することができるということです。 mP=0_{E(\mathbb{Z}/p\mathbb{Z})}は、 mが E(\mathbb{Z}/p\mathbb{Z})の位数 \#E(\mathbb{Z}/p\mathbb{Z})の倍数であるときかつそのときに限り成立します。ここで、うまいこと mをとれば、 \#E(\mathbb{Z}/p\mathbb{Z})の一定割合は mを割り切ってくれるのではないかというのが楕円曲線法のアイデアです。

mの定め方は、あるパラメータ Bを用いて、 m:=LCM(1, 2, 3, ..., B)とします。こうすると、 \#E(\mathbb{Z}/p\mathbb{Z})が B-power-smoothな場合、つまり各素因数毎の積 p^eが全て B以下の場合にアルゴリズムが成功すると言えます。

\#E(\mathbb{Z}/p\mathbb{Z})は [p+1-2\sqrt{2}, p+1+2\sqrt{2}]にほぼ一様に分布します。このことを用いて、求めたい pの大きさ毎にパラメータ Bをうまく定めて素因数分解を行います。

計算量の解析

\rm{M}(\log_2 N)を \log_2 N-bitの整数の乗算にかかる計算量とします。すると、楕円曲線法の具体的な計算量は O(\exp(\(\sqrt{2}+o(1)\) \cdot \sqrt{\log p\log\log p}) \rm{M}(\log_s N))となります。本項では、これを導出します。この計算量は、先程のecmルーチン一度の実行にかかる計算量ではなく、 p以下の素因数を見逃す確率が e^{-1}を下回るために必要な計算量であることに注意してください。

まず、先程のecmルーチンに必要な計算量を見積もります。boundã‚’ Bとおくと、 m \approx B^{\pi(B)}が成立します。そのため、 mPを計算するために必要な計算量は素数定理を用いることで

\begin{align} O(\log B^{\pi(B)} \rm{M}(\log N)))&=O(\pi(B)\cdot \log B \rm{M}(\log N)))\\ &=O(\frac{B}{\log B}\cdot \log B \rm{M}(\log N)))\\ &=O(B \rm{M}(\log N))) \end{align}

と分かります。これはecmルーチンで最も支配的な部分であるため、これがルーチンの計算量となります。

次に、ecmルーチンを実行する回数と Bの最適な値を見積もります。

まず、関数 Lを以下のように定義します。

L(x) = \exp(\sqrt{\log x \log\log x})

x以下の整数が L(x)^a-smooth*5である確率は、 x\to \inftyで L(x)^{-1/(2a)+o(1)}であることが知られています(Canfield-Erdős-Pomerance theorem)。これは整数を [x-2\sqrt{x}, x+2\sqrt{x}]から選んだときにも、経験的に同じことが言えます。

Bを L(p)^aにして 1/(L(p)^{-1/(2a)+o(1)})回ルーチンを実行することを考えます。これの成功確率は、 (1-\epsilon)^{1/\epsilon} \to_{\epsilon \to 0} e^{-1}であることから p \to \inftyで 1-e^{-1}に漸近します。なので、このパラメータでと実行回数で要求する成功確率を達成できています。最後に、全体の計算量を考えます。これは、 1/(L(p)^{-1/(2a)+o(1)})\cdot O(L(p)^a \rm{M}(\log N))=O(L(p)^{1/(2a)+a+o(1)} \rm{M}(\log N))となります。この式を最適化する aは \sqrt{2}であるため、これを代入して O(L(p)^{\sqrt{2}+o(1)} \rm{M}(\log N))を得ることができます。

楕円曲線法の高速化

教科書的な実装を再掲します:

def get_m(n, bound):
  m = 1
  # equivalent to: for i in range(1, bound): m = LCM(m, i)
  for p in primes(bound+1): # primes in [0, bound]
    k = floor(log(bound) / log(p)) # k such that p^{k} <= bound < p^{k+1}
    m *= p**k
  return m

def ecm(n, bound):
  E, P0 = get_random_elliptic_curve_and_point(n)
  m = get_m(n, bound)
  try:
    Q = m * P0
  except ModInvException as e:
    return gcd(e.value, n)
  return None

この実装を高速化していきます。

高速化手法1: 射影座標とLucas Chain、基礎算術の高速化

まず、楕円曲線上の点を射影座標で持つことで、楕円曲線上の加減算で除算を行わないようにできます。射影座標を用いることは原著論文(Lenstra 1985)の時点から指摘されていました。射影座標については、以下で詳しく解説されています。

zenn.dev

次に、 mを陽に計算しないようにし、その代わりにループごとに Q := pQをk度計算することとします。楕円曲線上のスカラー倍は、既知の点の加算か二倍算を繰り返して行われます。射影座標は他の座標の持ち方と比べて加算に多くのステップ数がかかるという欠点がありますが、 P-Qが分かっているならば高速に計算することができます（詳細は20 years of ECMの2節を参照）。そのため、加算は差が既知の点同士のみで行いたいです。このような条件下で、最小ステップ数で pQを計算するための加法連鎖はLucas Chainとして知られています。Lucas Chainの長さは O(\log n)となるので、加法連鎖の条件に制限をつけることでのペナルティは大きくありません。以下は、 23Qを計算するためのLucas Chainの一例です:

  • 2P := 2*P
  • 3P := 2P + P (差はP)
  • 5P := 2P + 3P (差はP)
  • 7P := 2P + 5P (差は3P)
  • 9P := 2P + 7P (差は5P)
  • 16P := 7P + 9P (差は2P)
  • 23P := 7P + 16P (差は9P)

このようなLucas Chainは、小さい pについては前計算することができます。Lucas Chainが既知でない場合も、PRACアルゴリズムというアルゴリズムを用いることで最適な演算回数に近いchainを生成することができます*6。

さらに、これらのアルゴリズム演算の根底にある多倍長演算やmod p上での乗算の高速化も行えます。これには998244353で割ったあまりを求めることを日課にしている勢力にはお馴染みの、モンゴメリ乗算やBarrett Reductionといったテクニックを適用することができます。

natsugiri.hatenablog.com

これらの最適化を実装したコードを以下に示します:

def ecm(n, bound):
  E, P0 = get_random_elliptic_curve_and_point(n)
  Q = P0.to_proj_coords()
  for p in filter(is_prime, range(bound)): # primes in [0, bound)
    k = floor(log(bound) / log(p)) # k such that p^{k} <= bound < p^{k+1}
    p_chain = get_chain(p)
    for i in range(k):
      Q = compute_mul_using_chain(Q, p_chain)
    if gcd(Q.Z, n) != 1: return gcd(Q.Z, n)
  return None
高速化手法2-1: standard continuation

次に、アルゴリズム自体に改良を加えます。新しい処理を今までのアルゴリズムに続く形で実装し、今までのアルゴリズムをstage 1、加えたアルゴリズムをstage 2と呼ぶことにします。また、stage 1で用いていたboundをbound1(あるいはB1)と言い換え、stage 2で用いる新たなboundをbound2(あるいはB2)と呼ぶことにもします。

stage 2では、stage 1で計算された点である Q:=m\cdot P_0に様々な係数を別々で掛け合わせます。具体的には、 [\rm{B1}, \rm{B2}\)に含まれる素数すべてについて、 \gcd((pQ)_Z, n)を都度確かめます。こうすることで、「あと一歩」だった Eに対しても、。これには一見すると嬉しさが殆どないように思えるかもしれませんが、このステップがあることで log p倍ほどの高速化がもたらされます(Brent 1985)。また、以降に述べるテクニックによってこの計算はより高速に行えるようになります。

def ecm_stage1(n, E, B1): # not optimized
  return get_m(n, B1) * E.random_element()

def ecm_stage2(n, E, Q, B1, B2):
  for p in primes(B1, B2+1): # primes in [B1, B2]
    Q2 = p * Q
    if gcd(Q2.Z, n) != 1: return gcd(Q2.Z, n)
  return None

def ecm(n, B1, B2):
  assert B1 <= B2
  E = get_random_elliptic_curve(n)
  Q = ecm_stage1(n, E, bound1)
  if gcd(Q.Z, n) != 1: return gcd(Q.Z, n)

  return ecm_stage2(n, E, Q, B1, B2)
高速化手法2-2: Montgomery continuation

まず、 [\rm{B1}, \rm{B2}\)に含まれる素数をすべて s \in Sと t \in Tの和で表すことができるような S, Tを考ます。これは色々なとり方がありますが、 d=\lfloor\sqrt{\rm{B2}-\rm{B1}}\rfloorを用いて S=\{\sigma\in [0, d\) \ \vert\ \sigma \bot d \}, T=[\lfloor\frac{B1}{d}\rfloor, \lfloor\frac{B2}{d}\rfloor\)することにします。これはbaby-step giant-step法の考え方と近いです。これを使えばある \sigma \in S, \tau \in Tを用いて pQ=(\sigma+\tau)Q=\sigma Q+\tau Qと表せます。なので、 \sigma Q, \tau Qをすべて前計算した後に、 \gcd((\sigma Q+\tau Q)_Z, N)を毎度計算してあげればよいことになります。

ここで、 \gcd((\sigma Q+\tau Q)_z, N)\neq 0は \sigma Q+\tau Q\equiv 0_{E(\mathbb{Z}/p\mathbb{Z})} \pmod pを表していることを思い出します。このとき \sigma Q\equiv -\tau Q \pmod pであるため、Affine座標（射影座標でない、(x, y)の2つ組でとる座標）での楕円曲線の性質を思い出せば (\sigma Q)_x\equiv (-\tau Q)_x\equiv (\tau Q)_x \pmod p（ P_xはアフィン座標でのxをとる記法とする）であることが分かります。まとめると、 \sigma_x:=(\sigma Q)_x, S_x:=\{\tau_x\ \vert\ \tau \in S \}( \tau_x, T_xについても同様)と表記することとすれば、 \gcd((\sigma Q+\tau Q)_Z, N)\neq 1ならば \gcd(\sigma_x-\tau_x, N)\neq 1であるということです。

また、 (-\tau Q)_x\equiv (\tau Q)_xであるという性質を考えます。すると、 \sigma Q+\tau Qについて調べた場合、自動的に \sigma Q-\tau Qについても調べたことになると分かります。これを用いると、アルゴリズムでカバーする集合のサイズはそのままに、片方の集合のサイズを半分に減らすことができます。

この高速化では計算量は定数倍ほどしか変化していませんが、問題を扱いやすい形に整えることができました。ここまでを実装すると、以下のとおりとなります。

def ecm_stage2(n, E, Q, B1, B2):
  d = floor(sqrt(B2 - B1))
  
  S = list([s for s in range((d+1)//2) if gcd(s, d) == 1])
  T = list(range(B1//d*d, B2, d))
  sxs = [(s*Q).to_affine().x for s in S] # x coords of sQ
  txs = [(t*Q).to_affine().x for t in T] # x coords of tQ
 
  for sx in sxs:  
    for tx in txs:    
      if gcd(sx - tx, n) != 1:
        return gcd(sx - tx, n)
  return None
高速化手法2-3: FFT continuation

以上のMontgomery Continuationは計算量が O(d^2 n\log n)でしたが、これを高速化します。 \sigma_x \in S_xを解として持つ多項式 Fを考えます。このとき、 \tau_x \in T_xのうち、どれかは \gcd(F(\tau_x), n)\neq 1を満たします。すべての \tau_x \in T_xについて F(\tau_x)を求めることは、多項式の多点評価を行うことで O(d\log^2 d)の計算量で行うことができます。 Fも分割統治的に掛け合わせること O(d\log^2 d)の計算量で行えるため、この計算量で求めることができると分かりました。

また、 \tau_x \in T_xを解として持つ多項式 Gを考えた上で F, Gの多項式GCDを取る手法もあります。原理は理解できていないですが、多項式 F, Gの多項式GCDを取ると nと互いに素でない値が定数項に出てくるようです。直感的には \bmod pで同じ解を持つことが影響してきそうです。

def polyeval_method(sxs, txs, n):
  F = prod([(sx - X) for sx in sxs])
  for Ftx in multipoint_evaluation(F, txs): # equivalent to [F(tx) for tx in txs]
    p = gcd(prod(Ftxs), n)
    if p != 1: return p
  return 1

def polygcd_method(sxs, txs, n):
  F = prod([(sx - X) for sx in sxs]) # sxs
  G = prod([(tx - X) for tx in txs]) # sxs
  return gcd(polygcd(F, G)[0], n)
高速化手法3: Brent-Suyama’s extension

今までのstage 2では、 \sigma+\tauを掛け合わせていました。Brent-Suyama’s extensionは、掛け合わせる数 \sigma+\tauをある多項式 fを用いて f(\sigma)+f(\tau)とする手法です。 fは低次の x^eやDickson polynomialとされることが多くあります。このように fをとった f(\sigma)+f(\tau)は \sigma+\tauは割り切れる上に他の素因数も含みます。よって、アルゴリズムの成功確率が少し上昇します。

高速化手法4: Edwards Curve

ここからの手法は、20 years of ECMにも記載がなく、gmp-ecmに実装されていない手法です。

今までの手法では、ランダムな楕円曲線を y^2=x^3+ax+bのパラメータ a, bをランダムに決めることでとってきていました。この選択する楕円曲線を、計算するのに都合のよいものに変更することはできないのでしょうか？ECM using Edwards curvesでは、選択する楕円曲線をEdwards Curveと呼ばれる楕円曲線にしました。Edwards Curveでは、射影座標での加算のような制約を受けずにある程度高速な加算が可能な楕円曲線です*7。

また、最新の研究では複数の楕円曲線の表現間を移行しながら演算することで、複数の表現のいいところ取りをするといった手法も提案されています。
eprint.iacr.org

高速化手法5: stage 1 batching

いままでのstage 1では、各素数ごとに最適な加法連鎖を得て、それを用いて乗算を行っていました。ECM using Edwards curvesでは複数の素数をかけ合わせてある程度大きな数にした後に、加法連鎖を計算するといった最適化も加わっています。

以下のでは、掛け合わせる素数の組を工夫し、より演算回数が少ないような組み合わせを探索しています。

eprint.iacr.org


例えば、bound1=256とした際には、以下のように組み合わせることでより効率的に計算することができます。

おわりに

時間がなくて最後のほうが雑になってしまいましたが、時間があるときを見て追記していけたらよいかなと思っています。

明日はarkさんによる、about:blankテクニックと"disconnection"の解説です。お楽しみに〜

*1:合成数でも話の大筋は異なりません

*2:楕円曲線は体に対して定義されるものなので、「ようなもの」と表記しています。「ようなもの」なので、加法に対して閉じていないため群をなしません。

*3:循環論法になっていますが、アルゴリズムの正当性を証明することを目指したものではないので目を瞑ってください。

*4:スカラー倍は加算の繰り返しで計算されることから直ちに分かるかと思います。

*5:これがpower-smoothについての議論でなくて良い理由はあまりよく分かっていません。どこを見てもsmoothnessで議論していて謎です

*6:私の考えでは、Lucas Chainが既知でない場合は p^kに対してPRACアルゴリズムを適用し、それに沿って計算するほうがよいように思います。しかし、gmp-ecmの実装(ecm.c#L1207-1240)ではどうやらそうはなっていません。なぜなっていないのかの理由は謎なので、分かったら教えてほしいです。

*7:Ed25519のEdもこのタイプの楕円曲線を用いていることから名前が取られています

Simple Flag Checkerの7つの解き方による動的解析入門【AlpacaHack Round 4 作問者writeup】

本記事は2024年10月5日（土）にAlpacaHack上で開催された、AlpacaHack Round 4(Rev)上で出題された"Simple Flag Checker"という問題のwriteupです。

AlpacaHackは個人戦の短期間CTFを継続して開催しつつ、それらの問題を常設することを目標とした新しいCTFプラットフォームです。AlpacaHackで開催される各ラウンドは1ジャンルをテーマとしていて、今回のAlpacaHack Round 4(Rev)はReversingをテーマとしたラウンドでした。私は本Roundに2問の問題を提供し、今回解説する問題である"Simple Flag Checker"はそのうちの一つです。

この問題はその名の通り*1バイナリ自体はシンプルな問題です。もしもまだ問題を見ていない方は、この先を読む前に10分ほどでもよいのでバイナリを眺めることをおすすめします。本writeupは問題を見ていない人でもわかるように書いたつもりではありましたが、自分で多少でも解法を考えるとこの先の話が頭に入りやすくなるはずです。

alpacahack.com

今回のラウンドはReversingの初回ということもあり、様々なReversingのエッセンスを詰め込んだセットにしたいと考えていました。この問題は「デコンパイルや逆アセンブリを読むだけがReversingではない」というメッセージをこめていて、バイナリの動的解析の手法を学ぶ足掛かりになるような問題として作問しました。本writeupでは、動的解析のアプローチやそれに用いる道具の多様さを感じ取っていただるよう、シンプルな解法から少し捻った解法まで様々なバリエーションの解法を紹介します。

ここで紹介した解法を実装したソルバ及び問題自体のソースコードは、以下のGitHubリポジトリで公開しています。


github.com

  • 問題概要
  • 解法
    • ltraceを用いて関数呼び出しをフックし、返り値を得る
    • LD_PRELOADを用いてmemcmpを差し替える
    • memcmpã‚’putsに置き換え、各ループでのhashã‚’å¾—ã‚‹
    • gdbでmemcmpの返り値を得る
    • updateを自由に実行できるバイナリを作る
    • ctypes.CDLLを用いてPythonからupdateを実行する
    • angrとUnicornを用いてバイナリをエミュレートする
  • おわりに

*1:問題名はRound 2で出題されたSimple Loginのセルフオマージュです。

続きを読む

The 2024 ICPC Asia Pacific Championship 参加記

この記事は、2024/3/2 にベトナムのハノイで開催された 2024 ICPC Asia Pacific Championship の参加記です。自分はチーム GoodBye2023 として Yu_212 や shibh308 と参加しました。

Championship とは ICPC の Regional 大会の結果によって招待される Asia Pacific Regional 全体の大会で、World Finals の進出者を選抜するために開催されます。この制度自体は 2020 年からありましたが、情勢の影響で開催が見送られ続けた結果今回が初めての開催となっています。自分たちはいままでは World Finals を狙えるほどの実力があるチームではありませんでしたが、この制度によって World Finals への進出が十分現実的なものとなりました。そのため、我々は真面目に World Finals 進出を目指して練習を積み重ねました。この記事は、その練習と実際の Championship の様子を記した参加記となります。

他のチームメイトの参加記:

yu212.hatenablog.com

AI が考えた参加記のタイトル。DOMjudgeとの一戦って何？

事前準備

作戦

3 人に大きな実力差があるチームではなかったので、事前に役割分担を設けることはしませんでした。ただ、チーム内で一番競技プログラミングが得意なのは Yu_212 だったため、Yu_212 の頭をできる限り働かせることを意識した立ち回りを心がけました。そのため、ライブラリの写経は主に shibh308 が、shibh308 がやることがあった場合は自分が担当することになっていました。

また、初動については予め細かく決めておきました。Championship では横浜のように序盤だけ難易度順といったことがなさそうなため、序盤に複数問問題を読んでおくことになりそうです。自分と shibh308 が比較的英語を読むのが得意だったため問題を読むことに注力し、その間にPC のセットアップを Yu_212 に行ってもらうこととしました。

GitHub の Issue にまとめた開始時にすることリスト

また、問題数が多く問題の把握ができないことが多かったため、問題の簡単な概要と誰が読んだかを記すシートを作成して運用することにしました。他には作戦といった作戦は事前に決めていませんでしたが、競技中の状況判断はある程度システマチックに行えるようにしていました。これは、全員が全力で問題に取り組む立場でメタ的に状況を俯瞰して正しい判断を下すことが難しいと考えたためです。状況判断の例としては、「序盤の簡単な問題で誤答を出したり 20 分以上実装が詰まった場合は問題から引き剥がす」、「サンプルが弱い問題の実装中に手が空いているが居た場合、その人がサンプルを作成する」といったものがあります。

ç·´ç¿’

12 月は月末にある SECCON の決勝大会に注力したかったこともあり、時間はあったものの練習はほとんど行いませんでした。1 月はチームメイトが帰省していたので 7 日の OUPC が初練習となり、その後から本格的にチーム練を開始しました。最初の方はチームとしての動きのミスが目立ったものの次第に減り、15回ほど練習するうちにチームとしての動きのミスはほぼなくなったと思っています。後で数えたところ、合計では 22 回練習を行っていたようです。大学のプリンタは一ヶ月で一人 200 枚しか印刷できないのですが、それを 3 人分 2 ヶ月フルに使ってもなお足りないほどの問題文とコードを印刷することになりました。

練習部屋にある印刷した紙の置き場。自分たちが印刷した紙でほぼ満杯になった。

また、本番の環境が 去年の World Finals の環境と全く同じであるという情報が選手間のチャットで回ってきたため、それに気がついてからは Virtual Box 上にインストールした WF OS を用いて練習を行いました。WF OS のインストールには非常に時間がかかったため、一通りのセットアップまで終わらせた後のイメージを保存しておき、そのイメージをクローンする形で毎回の練習を行いました。このように毎回環境がリセットされているのは、開始時に準備する担当のチームメイトにとってよい練習となったと思います。

Virtual Box の画面。最後の4(+1)回の練習は WF OS で行った。

ライブラリ整備

Championship では、World Finals と同じように持ち込めるライブラリの枚数に制限がありそうでした。今まで用いてきたライブラリは両面印刷で30ページ弱ありましたが、持ち込むライブラリは片面印刷で25ページに抑える必要がありました。よって、今まで持ち込んでいたライブラリから大幅に削らなければなりません。

環境

PDFの生成は、一般に非常に面倒くさいことが知られています[要出典]。そのため、やらなければいけないとは思いつつ面倒でなかなか手がつけられませんでした。1月末くらいに流石にそろそろ整備しないと間に合わないという雰囲気が出てきていたため、重い腰を上げて 1/22 のバチャ終了後に徹夜して大枠を整えました。管理は GitHub の Private Repository で行い、PDF まわりは基本的には迷路さんの方法を参考にしました。ただ、この方法はTeXに依存しているために環境構築が面倒になっています。チームメイトがいじるときにTeXの環境構築などの障壁がないよう、docker さえインストールしてあれば make コマンド一発で PDF がビルドできるような環境も整えました。しかし、手元で make pdf を叩いて PDF を生成したのは結局自分だけだったようです。一体どうして……

しかしこの整備が無駄足だったかと言うと決してそんなことはなく、簡単に GitHub の CI に乗せることができました。これにより、最新版の PDF が常に Release からダウンロードできる環境を整えることができました。整備した理由はPushするとReleaseが走るCIがあるとオタク的にアガるというしょうもない理由でしたが、実用的にも割と役に立った気がしています。最終的に、これは出先でライブラリの内容を確認したり、チームメイトが更新の結果をチェックするための手段となっていたりしました*1。

また、CIを整える過程でCIの出力にいろいろな情報を出したほうが便利そうだということがわかったので、合計ページ数やページ数を食っているライブラリなどの情報を出力するようにしました。

持ち込んだライブラリのRelease
中身

今まで使用していたライブラリが beet さんのものだったため、それをベースとすることにしました。とりあえず今持っているコードをすべて突っ込んだところ 110 ページくらいになってしまったため、チームメイトといる / いらないの選別を行ってライブラリ数を減らしていきました。このときに GitHub のProjectsを使って整理したのですが、これがなかなか使いやすかったです。

選別のようす

これでひとまず 23 ページ程度には収まったのですが、必要そうなライブラリを追加していく過程でまた膨れ上がっていきました。結局 27 ページ程度まで膨れ上がりましたが、PDF の各所にあるマージンを徹底的に削ったり、空白や改行を削って一行に押し込んだりする自明な改善で 3 ページほどページ数を削減することで解決しました。

それぞれ改善前 / 改善後

このようなちまちまとした作業は最初にライブラリの環境を整備したのが自分だったためかほとんど自分がやっており、貧乏くじを引いてしまったとよく愚痴をこぼしていました。それはそれとして自分が満足するライブラリを作ることはできたのでよかったのかなとは思っています。

ハッシュ

いままでのライブラリにも写経チェック用のハッシュがありましたが、チームメイトがハッシュの使用に対してかなり強く反対していたために使用していませんでした。しかし、練習で写経チェックの時間が嵩んだことや写経ミスが相次いだことから、何らかの方法でハッシュを導入しないといけないとも考えていました。
チームメイトがハッシュに反対していた理由は主に「C++で書かれたハッシュプログラムの写経に時間がかかる」「for 文を補完で出すなどでライブラリを完璧に写していない場合にハッシュが無効となる」という理由でした。これらについては、行毎にハッシュを出力するシェルスクリプトを書くことで解決し、ハッシュを導入することができました。

ハッシュの手法としては、CLI で簡単に扱えて軽量な MD5 を用いました。ただ、行毎にハッシュ全体を乗せることは到底できないため、各行にはハッシュのうち何文字かだけ乗せることになります。ハッシュの文字数は多ければ多いほど衝突の確率は減りますが、同時に横幅も占有してしまうことになります。なので、写経でミスをした際にどの程度までの確率ならば許容するかを考えながらハッシュの文字数を選定しました。ハッシュは hex で出力されるため、2文字であれば256種類、3文字であれば4096種類の空間となります。これは完全に主観ですが、1/256 の衝突は実際に起こりそうですが、1/4096 であれば起こったら笑い話にできるレベルで起こらなそうです。なので、基本的にハッシュは 3 文字にすることにしました。

また、このハッシュを実際に運用するためにはライブラリ側にハッシュを出力しなければいけません。ライブラリのルールには "Text and illustrations must be readable by a person with correctable eyesight without magnification from a distance of 1/2 meter." と記されており、あまりにも小さい文字では持ち込むことができなさそうです。correctable eyesight の意味がうまく取れませんでしたが、「矯正して到達可能な視力の人間が 0.5 m から読めるサイズ」と解釈し、裸眼の視力がかなり悪い自分が矯正後に 50 cm 離して余裕で読むことができるサイズに抑えました。そうはいっても多少は怖かったため、6 pt の 3 文字バージョンと、9 pt の 2 文字バージョンの 2 部を持ち込みました。

ジャッジ環境の調査

DOMjudge の調査

ICPC では、DOMjudgeというオープンソースのジャッジ環境を使用することが一般的です。このジャッジが Codeforces や AtCoder といった慣れ親しんだジャッジと違う挙動をしている可能性に惑わされることがないよう、事前に DOMjudge のコードを実行する部分を読んで知識をつけておくことにしました。……というのは建前で、実際のところは ICPC 練習で CTF などへの参加を諦めていたためにパソコン欲が満たされていなかったことによる一種の発作のようなものだったと思います。

まずは DOMjudgeを自分のPCで動かすことにしました。このようなソフトウェアは動かしにくいイメージがあったのですが、少し調べるとDocker のイメージが公開されており比較的簡単に動かせました。

DOMjudgeのAdmin側画面のようす

DOMjudge はWebアプリ側を担当するサーバー（domserver）と、ジャッジを担当する judgehost と呼ばれるサーバーとに分かれています。judgehost は複数台登録することができ、これを用いて多くの提出を並列に捌くことが可能となっています。これらのうち、今回興味があるのは judgehost の、特に提出したプログラムを実行する部分です。これはrunguard.ccというプログラムと、それを実行するtestcase_run.shというシェルスクリプトが担当しています*2。

これらを眺めると、runguard はコンパイルされたバイナリに各種制限をつけた上で実行しており、testcase_run.sh は runguard の実行結果が書かれた program.meta というファイル及び output を解析して verdict を返すスクリプトであることが分かります。

次に、 runguard が何をやっているかを詳しく読みました。このプログラムは先程も述べたとおり、バイナリに制限をかけた上で実行するものです。この制限 は setrestriction という関数で主に行われています。このコードを読むと、どのような制限がかかっているかを詳しく理解することができました。制限の値は runguard を実行する際のパラメータで指定できるのですが、DOMjudge の標準で指定されているパラメータでは以下のような制約がかかっている（はず）です:

  • chroot を用いた制限
    • プログラム毎に別のルートディレクトリを用いるようにしている
  • ファイルのパーミッションを用いた制限
    • 実行用のグループ及びユーザーを用いることで、ファイルの作成及びすべての書き込みを禁止している
  • rlimit を用いた様々な制限
    • メモリ及びスタックサイズは無制限としている
      • メモリは cgroup を用いて制限している
    • プログラムが書き込めるファイルサイズを OLE の値としている
      • 最大で用いることができるプロセス数を 64 としている
    • CPU 時間を ceil(max(実行時間+1, 実行時間*1.1)) 秒に制限している
      • rlimit では 1 秒単位での時間制限しかつけることができない
  • 自プロセスの cgroup への登録
    • 詳細は後述

また、cgroup と呼ばれる機能を用いてプログラムが使用できるリソースをコントロールしています。これは主にメモリの使用量を制限するために用いられていますが、実行する CPU のコアなどを細かく指定することもできるようです。おそらく、実行されるコアによる不公平さを回避するための機能だったりするのでしょう。

勘のいい方ならお分かりでしょうが、ここまででは実行時間制限に関する厳密な制約は一つも出てきていません。これは、詳細な実行時間は別の部分で管理されているからです。このプログラムは自身を fork することで実行途中から監視用の親プロセスとバイナリ実行用の子プロセスに分岐しています。親プロセスの具体的な役目は、プログラムの終了を待った後に出力を保存し、プログラムの実行結果に関する情報を解析して metafile と呼ばれるファイルに書き込むことです。実行に用いた詳細な CPU 時間は cgroup の情報から得ることができ、親プロセスはこれを用いて TLE などの判定をしているのです。また、一つのプログラムがジャッジを占有してしまうことを防ぐため、ある程度時間が経過した後にプログラムを強制終了する処理も行われています。IO 処理など CPU 以外の部分で時間がかかっていた際に誤ってプロセスを終了してしまうのを防ぐため、プロセスを終了するまでの時間は実行時間制限より多少長めに確保されています。

これまでの流れを簡易的にまとめると、以下の通りとなります*3。

parse_option(); // コマンドラインオプションをパースする
open_metafile(); // 実行結果を格納するファイルを作成する

int pid = fork();
if (pid == 0) {
  // 子プロセスの場合だけ実行される
  setrestrictions(); // 自プロセスに制約を追加する
  run_binary(); // バイナリを走らせる
}
else {
  // 親プロセスの場合だけ実行される
  redirect_output(); // 子プロセスの実行結果を保存するファイルを作成する
  
  settimeraction(terminate); // timer の終了時にプログラムを強制的に終了
  settimer(hard_limit); // timer を設定。デフォルトでは max(TL*1.1, TL+1sec)
  
  wait(pid); // 子プロセスの完了を待つ
    
  read_program_output(); // 子プロセスの出力を読み取り、ファイルに保存
  
  check_statuscode() // ステータスコードを元に RE をチェック
  output_cgroup_stats() // cgroup の情報から TLE や MLE をチェックし、結果を metafile に書き込み
}

このような調査をしている最中、このプログラムに潜在的な脆弱性があることに気が付きました。これは、fork の前に open_metafile が実行され、open されたファイルが run_binary の前に close されていないことで発生しています。Linux では、fork や別プログラムの実行を行っても開いているファイルは子プロセスや別プログラムに受け継がれます。そのため、本来ならば監視プロセスしか書き込むことができない metafile にジャッジ対象のプログラムが書き込むことができてしまいます。これを用いると、metafile を改ざんして実行結果を偽装することができてしまいそうです。

ここからはこの脆弱性もどきについての話をしますが、これはしかるべき窓口を通して報告をした結果修正パッチがすでにリリースされており、公知のものとなっていることは申し添えておきます。

真っ先に思い至ったことは、実行時間制限を一秒程度伸ばすことができる可能性についてでした。前述した通り、プログラムが強制終了されるのは実際の実行時間制限より少し長い時間が経過した後です。そのため、どうにかして TLE であったという事実を覆い隠すことができれば実行時間制限を超えて実行できそうです。しかし、結論から言えばこれを行うことは不可能そうでした。なぜならば、実行時間制限を超えたことはあるパターンにマッチする文字列が metafile 内に存在するかで判定されており、かつプログラムが完全に終了された後に metafile を書き換えることが不可能だったためです。ただ、metafile に特定の文字列を書き込むことで、どんな実行時間のプログラムでも TLE として処理させることができそうです。これにより、夢の(?) 1 msでTLEを取得することが可能となりました。

プログラムが完全に終了された後に metafile を書き換えることが不可能であるということは、既存の metafile の先頭にコンテンツを追加することのみが可能であるということです。metafile のパースが tag, content = line.split(": ") のように行われているため、通常 metafile の 1 行目にあるメモリ使用量の tag を破壊して任意のメモリ使用量に置き換えることができそうです。これを用いることで、ありえないメモリ使用量（負など）を申告することができました。
また、普段は文字列が入ることが想定されていない特殊なタグに対して文字列を挿入することも可能となりました。例えば、送出された signal を示す tag に文字列を入れることで DOMjudge の提出詳細画面に任意の文字列を表示させることが可能となりました。ここで XSS などができれば立派な脆弱性だったのですが、Webフレームワークが入力文字列をエスケープしていたことにより XSS を行うことはできませんでした。他にも ReDoS などについても考えましたが、 metafile が通される正規表現はどれも ReDoS を行うことが不可能なものだったために成立しませんでした。

このバグを用いて改ざんした提出結果

このように全くもって悪用することが不可能そうなバグでしたが、潜在的に危険ではあることは確かなために DOMjudge のセキュリティ報告窓口を通じて報告しました。その日のうちに対応して下さり、とても有難かったです。

ジャッジサーバーの調査

競技の10日前ほどに Judge Manual が公開され、そこには実際に使用される GCP のインスタンスが記されていました。そのため、実際に同じインスタンスを借りて様々なコードの実行速度を調査しました。実行したコードは unordered_map やmap に要素を追加するコードや bitset のコード、そして各配列要素に対して xorshift のようなことを行うコードです。特に後者二つについては SIMD 化の影響をテストしたかったため、pragma を追加した場合とそうでない場合それぞれについてテストしました。また、それぞれのコードはAtCoderおよびCodeforcesでも実行し、慣れ親しんだジャッジとの速度の差についても意識できるようにしました。実行結果（ミリ秒）は以下の通りです*4。なお、実際に実行したコードはgistに公開しています。

unordered ordered vectorize vectorize_opt bitset bitset_opt
AtCoder 323 1104 - 720 - 656
Codeforces 732 1466 5506 717 5506 889
GCP 491 1190 1329 386 1694 479

これを見ると、SIMD化が関わらない場面ではAtCoderのジャッジとほぼ同等、SIMD化が関わる場面では2倍弱程度の高速化になっていることが分かります。そのため、Codeforcesで行っている普段の練習のような感覚で提出しても問題ないことが分かりました。

ただ、これは「本番のジャッジ環境がPDFに記されている通りであれば」の話です。今回の運営は横浜のような手練れの方々ではなさそうなため、掲載されているPDFはあまり考えず何らかのファイルをコピーしてきているだけという可能性も十分にあると考えていました*5。そのため、本当に示された通りの環境で動いているかをPractice中に確かめるためのコードを事前に用意しておくことにしました。

普段であれば /proc/cpuinfo に特定文字列が入っているかを確かめるコードを書けば十分でした。しかし、今回は前項で触れた通り chroot によってファイルにアクセスできないようになっているためにそれを行うことはできません。追記: procfs はマウントされていました。なので、普通に assert(WEXITSTATUS(system("grep 'XXX' /proc/cpuinfo")) == 0); とすれば良さそうです。CPUID命令というCPUに関する様々な情報を取得することができる命令を用いてCPUのブランド文字列を取得し、それが事前にチェックしていたものと等しいかどうかを確かめるようなコードを用意しました。コードは以下のような形となりました。

#include<stdio.h>
#include<string.h>
#include<assert.h>
int a[4];
void brand_string(int eax) {
  if (eax == 1) {
    __asm__("mov $0x80000002 , %eax\n\t");
  }
  if (eax == 2) {
    __asm__("mov $0x80000003 , %eax\n\t");
  }
  if (eax == 3) {
    __asm__("mov $0x80000004 , %eax\n\t");
  }
  __asm__("cpuid\n\t");
  __asm__("mov %%eax, %0\n\t":"=r" (a[0]));
  __asm__("mov %%ebx, %0\n\t":"=r" (a[1]));
  __asm__("mov %%ecx, %0\n\t":"=r" (a[2]));
  __asm__("mov %%edx, %0\n\t":"=r" (a[3]));
}

void get_brand(char* buf) {
  int* ibuf = (int*)buf;
  brand_string(1); memcpy(ibuf+0, a, 16);
  brand_string(2); memcpy(ibuf+4, a, 16);
  brand_string(3); memcpy(ibuf+8, a, 16);
}

int main(){
  char buf[12*4+1]{0};
  get_brand(buf);
  char* expected = "           Intel(R) Xeon(R) CPU @ 3.10GHz";
  assert(strlen(expected) == 41);
  assert(strcmp(expected, buf) == 0);
  puts(buf);
}

このCPUはGCPのマニュアルにも具体的なモデル名は書かれていませんでしたが、CPUのブランド文字列を見る限りカスタムモデルとなっているのだと思います。

コンテスト

力尽きてきたので軽めに書きます。他のチームメイトが詳細に書いてくれるでしょう。（参加記とは……？）

Practice

Practice Session は開会式を終えて昼食を食べた後に行われました。我々は事前に Practice でやることを GitHub に纏めていたのですが、Practice ではドキュメントと医療品以外は持ち込み禁止とのことだったので急遽予備のライブラリ群に書き写して持ち込むことにしました。ハンドクリームやウェットティッシュ等が許可されているかが不明でしたが、堂々としていたら持ち込むことに成功しました。

セッション中に日本でむちゃくちゃ買い込んできたお菓子を明日持ち込めるか聞いたところ、する場合は今日中に入れておく必要があるとのこと。ホテルにあるから今すぐ帰るべきか？と若干の圧をかけると、当日の持ち込みも許可されました。同様に同一のライブラリを 3 部まで持ち込んで良いと言われたので「それは事前に告知されていなかった、不公平だ」とゴネたところ印刷してもらえることになりました。むちゃくちゃ負荷をかけている気がして少し申し訳なくなりましたが、まあ事前にこういう部分を公開していない方も公開していない方だよね……ということで。

しばらくするとコーチ陣が電子機器などを携帯して入ってきていたので、あの書き写した努力は一体何だったのかという気持ちになりました。後半は言えば電子機器を持ち込めたのでしょうか……。

コンテスト中

  • 開始前: 風船の色数を数えていました。自分たちは 12 色という結論に至りました。
  • [0:00]: 事前の相談通り、Yu_212 がパソコンのセットアップをしている間に自分が前から、shibh308が後ろから問題を読みました。読んでいる間に shibh308 が H に簡単枠がありそうということで Yu_212 に伝え、実装していました。
  • [-0:10]: ちょうど実装が完了したくらいで、自分と shibh308 を合わせてすべての問題が読めている状態になりました。提出前に shibh308 がコーナーケースを指摘して修正などをしつつ、提出をしました。が、その提出は WA となりました。
  • [-0:20]: このような状況では他の人と交代すると決めていたため、コードを印刷して自分がデバッグをすることにしました。印刷を待っている間に解けそうな問題（C, D, E）を Yu_212 に説明し、説明が終わったくらいのタイミングで印刷が到着。少し眺めた後にバグがわかったので、Yu_212 に修正してもらいました。それを提出して AC。
  • [-1:00]: この段階で C が解けそうに見えてきたため C に集中することにし、D と E ã‚’ yu_212 に任せます。暫くすると J が Yu_212 によって解けていて、実装を Yu_212 が shibh308 に任せていそうな雰囲気が伝わってきました。shibh308 がそれを実装した上で提出し、AC。
  • [-1:15]: 確かこのあたりで C はほぼ解けていて、提出をし、assertion で RE を出すみたいなことをしていた気がします。
  • [-1:30]: このあたりでさっき投げた E が解かれていました。Cはまだバグっています。本当に C で沼に嵌っていたため自分から Yu_212 に Help を出し、一旦デバッグを交代してもらう代わりに結構解かれていた G などを考えることにします。
  • [-2:20]: トイレに行ったら C のバグのケースがなんとなく分かったので帰って報告すると、Yu_212 も同時に同様のケースを見つけていたよう。ここからは自分だけで修正できそうなので Yu_212 は他の問題に行ってもらうことにして、修正しました。提出したら AC。
  • [-2:40]: とりあえずとても解かれている G を考えながら何もわからないなあと言っていたら、shibh308 が解けたらしいので解法を聞きます。合っていそうで実装で詰まる要素もあまりなさそうなので、とりあえず実装してもらうことに。やる問題がなくなったので、解くことがほぼ必須になりそうな F を考えることにします。
  • [-3:00]: F を考えていたところ、なんとなく解けていそうな雰囲気が漂ってきました。それはそれとして解法が簡単すぎたので一回 shibh308 に確認を取ると、問題を途中で取り違えていたことに気が付きます。気を取り直してもう一度考えると、もう一度解けていそうな雰囲気が漂ってきました。今度は合っていそうだったため、実装を詰め始めました。このタイミングで K が解けたり解けていなかったりしていた気がします。
  • [-4:00]: K の実装が詰まったタイミングを見計らって、F の実装を開始しました。あと 2 時間で K と F ã‚’ 2 問通さなければいけないという多少ハードな状況だったため、速度は求めずに安全側に倒した実装を心がけました。具体的には、愚直解の一部を書き換えれば AC が取れる解になるタイプの問題だったため、まず愚直解から書き、その解の二乗を線形に落とすような修正を加えるという方法を取りました。これをすると、バグった際にランダムテストを回しやすい実装となります。実装できたので提出しますが、TLE。入出力高速化が何故か消えていたことが shibh308 に指摘されたのでそれを修正しましたが、なおも TLE でした。すべての関数呼び出しを削除し、vector を生配列に修正して提出すると、WA となりました。
  • [-4:55]: K のデバッグが最優先だったため、F は印刷した紙の上でデバッグすることに。K はもうペナルティを気にする段階でなかったため assert を用いてデバッグしていて、その間に自分が F を紙の上でデバッグしました。一箇所で参照する配列を間違えていたことに最後の 6 分くらいで気が付き、パソコンを 30 秒奪い取って修正し、提出をすると AC。
  • [-5:00]: もう自分ができることはなくなりました。あとは Yu_212 が K を合わせてくれることを祈りながらタイマーを眺めていましたが、最後まで合わずに競技時間が終了。

結果として、26位（大学別順位18位）という自分たちからすれば失敗の結果に収まりました。例年は Asia から 16-18 チーム程度の World Finals 進出チームが出るため、ギリギリで落ちている可能性が濃厚という成績のようです。

コンテストワクワク要素
  • 机の配置で文字を書いていました。自分たちは被害を被るような場所ではなかったので、あまり文句は言いません。
  • 問題を後ろから読む担当の shibh308 の問題文から最後の問題が抜けていました。幸い最後は難しめの枠でしたが、これで簡単枠だったら割と悲惨なことになっていたと思います。
  • 競技中にシェルの履歴を遡っていたら Practice 時の履歴まで遡れてしまって戸惑いました。CLion の shell だけ変なところに履歴がありリセットし忘れたみたいな話かな？と思いましたが、競技後に確認すると .bash_history に昨日の履歴が残っていました。
  • 向かいの Bocchi The Tech の声が壁越しに貫通してきて、普通にところどころ何を言っているか聞こえる場面がありました。具体的には、問題管理シートを書いていた Yu_212（12 問だと思い込んでいる）が 13 問らしいという情報を得る、高度合成数の話をしているのが聞こえてくるなどがありました。
  • 昼食のサンドイッチを配ってくださっていた方が、コンテスト中にカントリーマアムを指差して "Is this your countrie's cookie?" のようなことを話しかけてきた気がします。本当にびっくりしましたが、とりあえず適当に返していたら "Did you bring it from your country?" みたいなことまで聞いてきて「普通に会話する気あるんだ……」ともう一度びっくりしました。早く会話を終わってほしそうな雰囲気を出していたら次に行ってくれました。
  • どこかの国のコーチ二人が選手も使うトイレでタバコを吸いながら普通に会話していてびっくりしました。

コンテスト後

K が本当になぜ通らなかったのか分からなかったので、提出したコードを写真に撮ったうえでホテルに帰ってから OCR をしてコードを復元し、CF のミラーコンテストに提出してデバッグすることにしました。ここでそもそも入力からオーバーフローしていることに気が付き、一同驚愕……。#define int long long をしたところ無事通りました。悲しいね。

翌日のクルーズでは Speed Star の方々や日本から Technical Comittiee や作問として関わっている方とお話しさせて頂きました。ICPCの昔話や苦労話などいろいろなお話が聞け、とても刺激的でした。特に自分はジャッジシステム側の構成に興味がある身だったので、実際のオペレーションや構成がどうなっているかの話を（もちろん言える範囲で）聞けたのはとても興味深かったです。我々学生がこうして ICPC を楽しめるのは、本当にいろいろな方の尽力のお陰だというのを改めて感じました。

来年への抱負

去年までは完全に競技プログラミング引退老人卍という気持ちだったんですが、まだ World Finals も狙えそうだし現役競技者だぜという気持ちになったのでこれからも競技プログラミングを続けたいと思います。目指せ World Finals！

*1:手元でチェックするほうが簡単だと思うんですけれどもね……

*2:他にも domserver と通信をしてtesctase_run.sh を実行する judgedaemon.main.php も面白いといえば面白いですが、あまり本質的な情報はなかったために今回は省略します

*3:リソースの後処理などは除いています

*4:AtCoderはすでにpragmaとほぼ同等の最適化が行われているために pragma なしは省略

*5:実際はジャッジの準備などは横浜の方々が行ってくださっていたようです。本当にありがとうございます。そのため、PDF なども環境に合わさったものとなっていました。

SECCON CTF 2022 Quals Writeup / 参加記

概要

この記事は、2022 年 11 月 12 日から 11 月 13 日にかけて開催された SECCON CTF 2022 Quals の Writeup です。今年の SECCON CTF は 3 年ぶりにオンサイトでの本戦が復活し、本大会はその予選大会としての位置づけとして開催されました。

自分は昨年に引き続き st98 さんを誘い、2 人チーム _(-.- _) )_ として参加しました。結果として、15 問を通して 1955 点を獲得し、全体 22 位 / 国内 3 位となりました。ここでは、そのうちで自分の通した 11 問についての解法を記します*1。

他のメンバーの Writeup:

nanimokangaeteinai.hateblo.jp

這ってでも旗を取りに行く気概
  • 概要
  • writeup
    • [welcome] welcome*2 (700 solves / 14:00)
    • [pwn] koncha (111 solves / 14:00-14:31)
    • [crypto] pqpq (112 solves / 14:31-15:28, 16:47-17:28)
    • [misc] find flag (100 solves / 15:28-15:44)
    • [rev] babycmp (176 solves / 15:44-16:20)
    • [crypto] this_is_not_lsb (34 solves / 18:15-19:02)
    • [misc] noiseccon (22 solves / 19:06-22:24)
    • [crypto] BBB (50 solves / 22:09-23:56)
    • [misc] txtchecker (23 solves / 00:06-00:22, 03:34-06:09)
    • [crypto] witches_symmetric_exam (22 solves / 08:54-11:38)
    • [rev] eguite (86 solves / 11:41-12:55)
  • 解けなかった問題
    • [rev] eldercmp (19 solves / 16:21-16:45)
    • [crypto] insufficient (33 solves / 17:32-18:15)
    • [misc] latexipy (8 solves / 05:35-08:53, 12:55-13:59)
  • 感想

*1:ここまでほぼ去年のコピペ

続きを読む

TSG LIVE! 8 CTF Writeup

概要

この記事は、2022 年 5 月 14 日 12:33-14:13 に開催された TSG LIVE! 8 CTF の Writeup です。自分は一人で参加し、1550 点を入れて優勝しました*1。五月祭や駒場祭で開催されるこの CTF は短時間ながら退屈な問題が存在しないCTF で、毎回とても楽しみにしています。今回も期待に違わず CTF のエッセンスが詰まった面白い問題揃いでした。今年の TSGCTF も楽しみですね。

*1:うれし～～～～～！

続きを読む

zer0pts CTF 2022 開催記/Writeup

概要

この記事は、2022 年 3 月 19 日から同 20 日にかけて開催された zer0pts CTF 2022 の開催記です。

  • 概要
  • writeup
    • [pwn] Moden Rome(105 solves)
    • [web] Disco Party(51 solves)
    • [web] Disco Festival(1 solve)
    • [rev] Chirashi-sushi(8 solves)
    • [crypto] OK(9 solves)
    • [web/misc] zer0tp(1 solve)
      • 速習・DEFLATE
      • 速習・Zlib
      • オラクルパート
      • md5 パート
      • 本題
  • 開催記
    • 準備
    • 開催中
  • おわりに

この CTF は所属するチーム zer0pts が開催する CTF で、自分は運営として作問と当日の運用に携わりました。他のチームメイトの開催記/writeup は以下の通りです。

ptr-yudai.hatenablog.com

furutsuki.hatenablog.com

furutsuki.hatenablog.com

続きを読む

SECCON CTF 2021 Writeup / 参加記

概要

この記事は、2021 年 12 月 12 日 から 12 月 13 日にかけて開催された SECCON CTF 2021 の Writeup です。あと CTF Advent Calendar 2021 の 9 日目の記事です*1。
SECCON は長らく予選-本戦形式のオンサイト CTF として開催されてきました。しかし、社会情勢の影響もあり、去年に引き続き今年も Jeopardy 形式のオンライン CTF として開催されました。
自分は st98 さんを誘い、2 人チーム (o^_^o) として参加しました。結果として、15 問を通して 2543 点を獲得し、全体 10 位/国内 1 位となりました。ここでは、そのうちで自分の通した Welcome 以外の 9 問についての解法を記します。
また、ついでとして参加記っぽいことも書くことにします。あまり難しい問題を解いていないですし、良質な Writeup は自分が書くまでもないですからね。

なお、st98 さんの Writeup はこちらです:

nanimokangaeteinai.hateblo.jp

旗を持っているみたいで可愛いですね
  • 概要
  • 開始前
  • 開始後
  • [crypto] pppp (117 solves)
  • [misc] s/<script>//gi (115 solves)
  • [pwn] kasu bof (78 solves)
  • [pwn] Average Calculator (56 solves)
  • [rev] <flag> (11 solves)
  • [misc] qchecker (14 solves)
  • [crypto] oOoOoO (26 solves)
  • [rev] dis-me (15 solves)
  • [rev] sed programming (14 solves)

*1:すいませんでした

続きを読む

ICPC2020 国内予選 F - 避難所

ICPC2020 国内予選の F 問題「避難所」の解説です。よく見る解法とは違うアプローチで解いたため、せっかくなので解説記事にしてみました。

問題概要

n頂点m辺 (1\le n,m\le 10^5) の連結で単純な無向グラフGが与えられる。また、各辺E_iには 値A_i(1\le A_i\le 10^5)が割り当てられている。
ここで、G_cを辺集合\{E_i|c\lt A_i\}から構成されるグラフとする（つまり、値c以下の辺を除いたグラフ）。
また、f_{G,i}(c)をG_cにおいて頂点iを含む連結成分の個数として定義し、頂点iについて列[f_{G,i}(0),f_{G,i}(1),f_{G,i}(2)\cdots]を考えた時、これを辞書順最大にするようなiを全て求めよ。

続きを読む

ICPC2020 国内予選 参加記

出ました

コンテスト前

延長ケーブルと充電器、手の乾燥対策にハンドクリームを持ってきた。12時くらいに現地について、食堂でご飯を食べてから12:30くらいに演習室についた。人がいるかと思ったけど一人しか居なかった。

開始までかなり時間があって暇だったので、もくもくとMatrix Calculatorや他の500程度の問題を解いたり、初級者の一年生にダイクストラ法を教えるなどしていた。

今年は自PCで事前準備ありだったので、いろいろとコンテスト前にできた/する必要があった。具体的には、

  • Discord/LINEを落とした,PCも含めた全端末の通知を切った
  • ライブラリの検索/貼付用にhttps://beet-aizu.github.io/library/とリポジトリをローカルに落とした
  • 事前にテンプレートが入ったクリーンなディレクトリ(a/a.cpp,b/b.cpp,c/c.cpp...) を問題分作るシェルスクリプトを書いてコンテスト前に回す運用をした（コンテスト中にまわして消し飛ばしたらかなり嫌なので、回し終わったらrmした）
  • 拡張とかがいろいろあって間違って変なものをクリックしたら嫌だったので、chromeのプロファイルを新規作成した
  • VSCodeのデバッガが狂うので、CTF用に改造されたgdbをデフォルトに戻した
  • ID/passをローカルファイルに落とした

等をした。これは2週間前くらいから持ち物等と一緒にリストアップしていた。

10分前くらいに喉が痛かったのでのど飴を買った。そこそこ効いたと思う。

それと打ち上げがコンテスト終了後20分で開始らしく、かなり慌ただしくなることが予想されたので事前にある程度出れるようにはしておいた。

コンテスト中

始まった。と同時にDBが壊れているとのエラー。リロードしなおせば治ってるだろとか思いながら何回かリロードしても駄目で、シークレットブラウズでログインし直すも駄目みたいだった。さようなら……

こどふぉった後に開始時刻のアナウンスがまたあるだろうとか言いながら、突然繋がったら嫌なので5秒間隔くらいでF5を押していると突如繋がる。も、practice前の様子。

打ち上げの開始時刻の心配や運営チームの心労の心配とかをしながら引き続きリロードをしていると、状態がpracticeになっていた。今ならFA取れるぞとか冗談をいいつつ順位表をリロードすると、問題が8個くらいあることに気がつく。始まってね?

Aを見る stringにしてsubstrとかをすることが頭を過るも、Aなので何も考えずa[i-3],a[i-2],a[i-1],a[i]を比較するコードを書く。通る。4分

Bは読解が秒ではなかったので僕がBをやることに。らずひるどが問題概要を予め把握していてくれたので、やるだけだった。やる。通す。8分

Cはかなり難しそうで、すくなくともサラッと通せる問題ではなさそう。とりあえず目を通し、105くらいまで列挙すると残りが簡単に定まるのではないか?と思うも1010くらいなので駄目っぽい。最初108くらいになると思って解けたとか言っちゃった、ごめん。Dが構文解析っぽいのでそっちをやったほうが良いとのことで回ってくる。

Dは構文解析はあるにはあるも本質ではなさそう（BNFが1行とか2行とか） 。とりあえず出てくる変数を決め打ちそう→全変数間の大小関係を2-SATの変数として持ち、それぞれの式と推移性について条件式を作れば良さそうだなあとか思う。が、数えられないので終わり。

頭を捻っているとCが通る。(40分) この時点で学内2位/全体31位とかでbeetさんがかなり動揺していた。Dが全く解けなかったので聞くと、秒でn<=16なのでbit全探索と言われる。なににbitを建てるのかさっぱりだったので聞くが、決め打ったら後必要な情報がそれより大きいか小さいかだけと言いながら震える手で図を書いていた。ボロボロになりつつも秒で解法を出してきていて凄いし、それを30分出せなかったのは素直にかなり反省。???「これができないのは、ヤバいよ」

ということで書く。構文解析パートは関数一つだけでなんとかなるレベルのゆるい奴。正直僕もかなり動揺していたので、文字からindexへの変換をmap持って終わらせればいいものをわざわざ式内に登場するシンボルを置換したりしていて本当によくない。20分くらいで書き終わる。サンプルが合わん、何がいけなかったんでしょうねぇ…… 15分くらい唸るも、原因は

if (op=='<') return a < b ? a : b;
else return a > b ? a : b;

と

if(op=='<') swap(a,b);
return a > b : a : b;

を等価だと思っていたことだと判明。コンテスト中には何故これが等価でないのか分からずに納得できずも、とりあえずサンプル合うからヨシ!をした。（それぞれのreturnはminとmaxということにすら気がついていなかった）出す。通る。80分

そうこうしているうちに、Eがなんかギャグらしくて解けたらしい。なのでF読むかをしてらずひるどの考察を聞いているうちにEが通る。85分

ここで状況確認。とりあえず5～6位くらいで、早めに5完はしたので通過はしそう?FGHを読むも、GHは1時間半で0完なので捨てて良さそう（Gは見込みはなくはないが、Hは完全にヤバい幾何なのでさようならという感じ）。残りはFということで、Fの考察をすることに。

少ししてFが方針が生えたらしく、聞くと合っていそう。ただ、計算量が壊れそうなケースを見つけたのでそれを提示するもいい感じの方法が帰ってくる。あと70分くらいしかないので、とりあえず並列で実装をしてどっちかが通したらいいね作戦をすることに。

かなり後に気がついたんですが、ここで壮大なアンジャッシュが起きていたらしい。というのも、サンプルを試して解法を共有する際に両者の解法に少しズレがあったにも関わらず偶然同じステップを踏んでいた。嫌なケース等で合意が取れたので、把握している解法が違うなどとは思いもしない。

かなり辛い実装だったが、なんとか書き上がる、15分前。出す。合わない。解をソートしていないことに気がつく。ソートする。出す。合わない、10分前。 サンプルを試してステップ実行すると怪しい動きをしていそうだと気がつく。条件式が間違っていたので直す。出す。合わない、5分前。考察自体に致命的なミスがあることにチームメイトが気がつく、1分前。

終了 全体8位

ふりかえり・反省

ABは文句のない動きができた。Dで迷走したのは本当に頭が備わっていないせいで、高難度の練習を実装偏重にしていたのもあってよくなかった。頭を使おう。

Fでは、サンプルをチームで試して共有した上に生成した最悪ケースの出力が一致することを確認した。そのうえでのこれなので、今回はほぼ不幸な事故だったと思ったほうが良さそう。強いて言うなら、手で試せる範囲で一番強いサンプルを試すべきだった。

ただ、ある考察を否定する時に言っていることが全く分からなかったが、考察を投げた人が納得したので渋々納得したのは戦犯ポイント。ここで指摘していれば気がつけたかもしれない。言っていることの意味が分からず、かつ意味がわからないことに確信が持てるならば、ratismをぶっ壊して相手を疑うことをしたほうが良さそう。

ということで、チームとしての自分の動きも、個人としての自分の動きとしてもそこまで納得がいくものではなかった。結果はそこそこ良くはあったが、olpheチームに負けたなどもあってかなり悔しいのは確か。

なお、Fは自分のコンテスト中のコードを2byte書き換えたら正解チームのoutputと一致した。本当に下らないミスでとても悔いが残る上、思い違いをした解法が合っているとなるともう気がつきようがない気がする。ただ、終わったことなので今悔やんでもしょうがない。これを回避するには強くなるしか方法はないので、強くなる。  

コード

a.cpp · GitHub

b.cpp · GitHub

d.cpp · GitHub

Revisions · f.cpp · GitHub (初版がコンテスト中のコードで、その後が修正後のおそらくACコード)

ICPC2020 模擬国内予選 参加記

プラクティス

システムが初めてだったのでプラクティスをした ./l ではなく l < in > out としたらlsのエイリアスに反応してoutにファイル一覧が出ていて1WAした 国内予選ではほぼおそらくlはないけど罠を踏めてよかった 他にwでも死ぬらしいが、wまでは出ないのでセーフ

コンテスト前

家を出る前に持ち物チェックをしたのに充電器とハンドクリームを忘れた バッテリーは駄目になってて3時間持つか怪しかったので他チームの人に貸してもらった（本当にありがとうございます）チェックリストを作りましょう

コンテスト中

Aを見る こういうのは0に注意するんですよね～とか言っていたんですが、1<=a_i,b_i だったので残念(?) 書いて出す 6分弱 6位とか

Bが書かれ始めていたのでCを見る 今年も続投廻小宮ファミリー 生で見たのが初めてだったので笑ってしまった そうこうしてるうちにBが通って順位表を見たらFAだった（すげえ）

続けてCを読む n<=20とかであってくれとおもったけど10^5でした 普通にわからん… 思考が止まって眺めているだけに一瞬なっていて、これはまずいとしっかりと考える マス視点で何らかを埋めるんだろうなという気持ちにはなるが、わからん とりあえずわからんのでstartを(0,0)に、goalを(+,+)に補正する入力コードだけ書く マス視点だったら今までに消した範囲の数しかありえないよな→今いるところで全て消えているという仮定を置くと何を消したかの情報を持たなくていいじゃん 横に動いた場合と縦に動いた場合についてどこを消すべきかを配列に入れればいいね! 書き始める（考察15分くらい? 実装に15分くらい）

書き上がる 試す 境界外参照でエラー デバッグをするんですが、スタックトレースがないしブレークポイントがうまく打てないしで焦りまくって、結局printfデバッグする チームメイトにあと5分くらいで書けると伝えてから10分くらい経っていたので現状を聞かれ、せぐふぉってると伝える そうこうしていると原因を見つけた 配列のサイズをh+1,w+1にしていなかったとこがあった（10分くらいかかった）

直したので試す 最後の一ケースだけ合わん…… ここでブレークポイントが打てなかった原因が試しに追加した -O2 オプションのせいだったと判明 環境を直前にいじらない! さすがにハマりすぎているのでトイレに行って頭を冷やしてこいと言われるが、もうちょっとデバッグをする とりあえずいろいろな情報をダンプして見てみて、何がおかしいのかは判明 でもどうしてそういうことになっているかは分からない トイレ勧告2回目 流石に行く

帰ってきて少し見てみると分かる 原因は y+r, x+rを x+r, x+rにしていたことだった 後から思えば最初にダンプした情報でも値がおかしかったし、明らかに疑う場所は一つだった 頭が全く動いていなかった 本当に反省ポイント 動かすとサンプルは合う 出す 通る 70分弱 カス

この時点でEはとっくの昔に通っていたので一旦状況確認 可能性のあるDとFをどう解くかを話していた 聞こえてくる感じだとFはサイコロっぽい 読んでみると、ちょっとめんどくさいだけで解けそうじゃんと思ったが、入力がヤバすぎることが判明 Dを読む限り考察偏重っぽくてレート高いほうに任せたほうが良さそう&立体の回転/展開とかの空間把握と実装は少し自信があったのでFをやることに

とりあえずサイコロライブラリは写経してあったが、当然向きには対応していなかったので参考にはするが基本的には投げ捨てる方針でいく 写経担当の手が空いていたので分業して書くことにした 設計をとりあえず決める † みたいな展開図(標準展開図とか呼ぶ)で↑のときに0、→で1…みたいにする 回転自体は縦回転と横回転が一種ずつあれば全ての回転を網羅できることは分かったので、とりあえずDie構造体だけ書いて共有し、縦回転と横回転を書いてもらうことに

僕はとりあえず入力を書くことにした 方針自体は一瞬で立って、どこかからDFSをして頑張ればいい 持つべき情報は(与えられる展開図の(y,x), 標準展開図においてどこか, 標準展開図においてどっち向きか)

DFSをするために上下左右においてどう隣接してるかのリスト、今自分が上で、隣にあった場合の上の方向のリストが欲しいと分かる ここがこわれてるとデバッグが大変なことになる&最悪サンプルは合ってしまう可能性が大いにあるので、かなり丁寧にダブルチェックしつつリスト24個を埋める 結果的にここを丁寧にやったのはとても良かった ここらへんでDが通った

そうこうしている内に縦回転と横回転が終わったので、遅くてごめんと言いながらsolveの中身も書いてもらうことに 探索の内側については具体例と照らし合わせながら埋めた 扱うべき向きが三個くらい出てきて頭が壊れそうだったけどなんとかなった なんとかしたらsolveも書き終わったらしい とりあえず全部↑になるようなケースを手打ちで作って試す assertで死んだ 冷や汗が出たが、原因はすぐに突き止められて直したら合うので合体させた サンプルを試したら合体ミスでむちゃくちゃな値が出てきたけど、ちゃんと合体したらそれっぽい値は出た（30分前）

でもdiffを見ると違ったので、まずinputを疑う サンプル1のサイコロは3つだったので、手作業で標準展開図に補正してDieの中身をダンプしたのと比較 合ってる 15分前

なのでsolveから全探索を呼んでいる関数を確認して、少し怪しかったので書き換えると答えが変わるも合わない rotateが怪しい説が出てきたので、お人形さんになっていた写経担当を借りてきてrotateの説明をしてもらう 回転が一箇所間違っていたので修正する 合う 出す 通る 10分前 大口叩いて通せなかったらカスなのでヒヤヒヤしていた

GHは目を通してしかいなくて何も分からなかったので後は順位表を見ながらニコニコしていた なんでニコニコしてるんですかと言われたんですが、嬉しいからなんだよな

終了 全体9位

 

ふりかえり・反省

練習通りのステップを踏めなかった。Cは焦りがあったのもあるが、頭を使えていなかった。Fの実装をしているタイミングでようやく頭のギアが入った感覚があったが遅すぎる。ただ、Fをしっかりと詰めた上で書ききれたのは偉い。詰める練習をしていなければできなかったはず。

練習は本番のように、本番は練習のようにとか百万回聞いているが、本当に意識するべき。実装練習ばかりで頭を止めないでしっかりと考察を最近していないため、AOJの500-550の少し考察が必要なレベルを重点的に埋めるべき。本番も大きなミスなくやれるようにあと2週間気合を入れていく。

あとチェックリストを作りましょう（作りました）

 

コード

a.cpp · GitHub

c.cpp · GitHub

f.cpp · GitHub

 

コンテスト中に問題のdifficultyを推定した(かった)

～前回までのあらすじ～

コンテスト中に最終順位を推定したくなり、それをするにはコンテスト中にDiffを推定すればよいことが分かった。

keymoon.hatenablog.com

先行研究

コンテスト中にdiffを推定するということ自体は、すでにいくつかの先行研究がある。本項では、DEIM2020にて発表のあった「競技プログラミングコンテストにおけるタスクの難易度のリアルタイム推定*1」という論文で取られている手法の一つを紹介し、それの改善点について考察をする。

手法

まず、正解率pをレートとdifficultyの関係より導出される式 p=\frac{1}{1+6^{(d-r)/400}} より定めた。
そして、「時間T毎に各参加者が提出を行い、確率p_iで正答を得る。また、コンテスト参加者があるタスクに自分の解答を繰り返し提出し，正答であるという判定を得るまでにかかる時間が指数分布に従う。」というモデルを基に推定を行っていた。この場合の尤度関数L(d)は、指数分布の確率密度関数を用いて
\displaystyle L(d)=\prod_{i=1}^{N}{\frac{p_i}{T}\exp{\left( -\frac{p_i}{T}t_i \right)}}
と定められる。これの最大化については、尤度関数の対数を取り
\displaystyle \begin{eqnarray*} \log L(d)&=&\sum_{i=1}^{N}{\log(\frac{p_i}{T} \exp(-\frac{p_i}{T}t_i))} \\ &=&\sum_{i=1}^{N}{\left( \log\frac{p_i}{T}-\frac{p_i}{T}t_i \right)} \\ &=&\sum_{i=1}^{N}{\left( \log p_i-\log T \right)}-\sum_{i=1}^{N}{\frac{p_it_i}{T}} \\ &=&\left( \sum_{i=1}^{N}\log p_i \right) -N\log T -\sum_{i=1}^{N}{\frac{p_it_i}{T}} \cdots (1) \end{eqnarray*}
とした関数を最大化することと同じになる。これは、Tについて偏微分した
\displaystyle \begin{eqnarray*} \frac{\delta \log{L(d)}}{\delta T}=-\frac{N}{T}+\frac{1}{T^2}\sum_{i=1}^{N}{p_it_i} \end{eqnarray*}
が0となるようなTを離散的な各 d\ \mbox{s.t.}\ d \in ℤ, \rm{possibleMinDiff} \leq d \leq \rm{possibleMaxDiff}について求め、それによって\log L(d)を求めることで擬似的に実現できる。
そのようなTは
\displaystyle T=\frac{1}{N}\sum_{i=1}^{N}{p_it_i}
と表せるので、(1)式は
\displaystyle (1)=\left( \sum_{i=1}^{N}\log p_i \right)-N\log T-N \\
と表すことができる。

問題点

このモデルの問題点について考察する。
まず、各人がコンテストを通して解答できる時間の期待値e_iをT/p_iとしているが、それの根拠となる仮定である「時間T毎に提出して確率p_iで正答を得る」という点について。p_iを算出するのに用いているdifficultyの定義は「全体で正答できる確率が50%になるようなレート」であるが、この仮定の下では全体での正答確率がp_iとならないため、これは定義を満たしていない。
また、確率分布が以上の仮定に従うとすると離散的な指数分布を取ると考えられるが、その仮定とは別に指数分布となるモデルを考えているため、複数のモデルが並立していることになっている。
また、レート毎の解答時間の分布に指数分布を用いているが、レート毎の解答時間の分布は対数正規分布になることが観察と考察によって確かめられる。

pepsin-amylase.hatenablog.com

よって、本記事では対数正規分布を解答時間の分布として用いて推定を行ってみたいと思う。

正規分布による推定

difficultyの定義より、レートrの人が難易度dの問題を終了時刻t_{end}において正答できている確率は
\displaystyle \frac{1}{1+6^{(d-r)/400}}\cdots(2)
と表せる。
ここで、あるレートrにおいて正答を得られるまでの時間tは対数正規分布に依り、すべてのtについて対数スケールでの分散が一定であると仮定する。
そのため、あるレートrに対して対数スケールでの解答時間の中央値がe^\mu、同じく分散が\sigma^2のとき、時間tに対する確率密度関数は
\displaystyle \frac{1}{\sqrt{2\pi\sigma^2}t}\exp\left(-\frac{(\log t-\mu)^2}{2\sigma^2}\right)
となる。
ここで、正規分布は尺度s=\frac{2}{\pi}|\sigma|のロジスティック分布に近似できるため、そのような近似を用いて\muをsの式で表すことを考える。この\mu,sは、時間tに対する対数ロジスティック分布の累積分布関数\frac{1}{1+e^{(\mu-\log t)/s}}とレートあたりの正答率の式(2)より、
\displaystyle \begin{eqnarray*} \frac{1}{1+e^{(\mu-\log t_{end})/s}}&=&\frac{1}{1+6^{(d-r)/400}} \\ \Leftrightarrow e^{(\mu-\log t_{end})/s}&=&6^{(d-r)/400} \\ \Leftrightarrow (\mu-\log t_{end})/s&=&(d-r)/400\cdot\log 6=\frac{\log 6}{400} \cdot (d-r) \\ \Leftrightarrow \mu&=&\frac{s\log 6}{400} \cdot (d-r) + \log t_{end} \end{eqnarray*}
という式に従う。

以上より、\muを\sigmaに対する式として表すと、
\displaystyle \mu=\frac{|\sigma|\log 6}{200\pi} \cdot (d-r) + \log t_{end}
となる。ここで、簡便のためにc=\frac{200\pi}{\log 6}とする。

これを時間tに対する確率密度関数に代入すると、
\displaystyle \frac{1}{\sqrt{2\pi\sigma^2}t}\exp\left(-\frac{\left(\log t-\left(\frac{|\sigma|}{c} \cdot (d-r) + \log t_{end}\right)\right)^2}{2\sigma^2}\right) \\
となる。上式より、尤度関数L(d)を
\displaystyle L(d)=\prod_{i=1}^{N}\frac{1}{\sqrt{2\pi\sigma^2}t_i}\exp\left(-\frac{\left(\log t_i-\left(\frac{|\sigma|}{c} \cdot (d-r_i) + \log t_{end}\right)\right)^2}{2\sigma^2}\right) \\
と定める。対数を取ると、
\displaystyle \begin{eqnarray*} \log L(d)&=&\sum_{i=1}^{N}\log\left(\frac{1}{\sqrt{2\pi\sigma^2}t_i}\exp\left(-\frac{\left(\log t_i-\left(\frac{|\sigma|}{c} \cdot (d-r_i) + \log t_{end}\right)\right)^2}{2\sigma^2}\right)\right) \\ &=&\sum_{i=1}^{N}-\log(\sqrt{2\pi}|\sigma|)-\log t_i-\frac{\left(\log t_i-\left(\frac{|\sigma|}{c} \cdot (d-r_i) + \log t_{end}\right)\right)^2}{2\sigma^2} \\ &=&-N\log\sqrt{2\pi}-N\log|\sigma|-\sum_{i=1}^{N}\log t_i-\sum_{i=1}^{N}\frac{\left(\log t_i-\log t_{end}-\frac{|\sigma|}{c} \cdot (d-r_i)\right)^2}{2\sigma^2} \\ &=&-\left(N\log\sqrt{2\pi}+\sum_{i=1}^{N}\log t_i+N\log|\sigma|+\frac{{\displaystyle \sum_{i=1}^{N}}\left(\log t_i-\log t_{end}-\frac{|\sigma|}{c} \cdot (d-r_i)\right)^2}{2\sigma^2}\right) \\ \end{eqnarray*}
となる。\sigmaについて偏微分すると、
\displaystyle \begin{eqnarray*} \frac{\delta\log L(d)}{\delta\sigma}&=&-\frac{N}{\sigma}-\sum_{i=1}^{N}-\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{c\sigma^3}\\ &=&-\frac{N}{\sigma}+\sum_{i=1}^{N}\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{c\sigma^3}\\ \end{eqnarray*}
となり、上式の偏微分が0になるために\sigmaが満たすべき条件は

\displaystyle \begin{eqnarray*} -\frac{N}{\sigma}+\sum_{i=1}^{N}\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{c\sigma^3}&=&0\\ \Leftrightarrow\sum_{i=1}^{N}\frac{(\log t_i-\log t_{end})(c(\log t_i-\log t_{end})-|\sigma|(d-r_i))}{\sigma^2}-cN&=&0\\ \Leftrightarrow\sum_{i=1}^{N}\frac{c(\log t_i-\log t_{end})^2-|\sigma|(d-r_i)(\log t_i-\log t_{end})}{\sigma^2}-cN&=&0\\ \Leftrightarrow\sum_{i=1}^{N}\frac{c(\log t_i-\log t_{end})^2}{\sigma^2}-\sum_{i=1}^{N}\frac{(d-r_i)(\log t_i-\log t_{end})}{|\sigma|}-cN&=&0\\ \Leftrightarrow\left(\sum_{i=1}^{N}c(\log t_i-\log t_{end})^2\right)\frac{1}{\sigma^2}-\displaystyle \left(\sum_{i=1}^{N}(d-r_i)(\log t_i-\log t_{end})\right)\frac{1}{|\sigma|}-cN&=&0\\ \Leftrightarrow cN\sigma^2+\left(\sum_{i=1}^{N}(d-r_i)(\log t_i-\log t_{end})\right)|\sigma|-\sum_{i=1}^{N}c(\log t_i-\log t_{end})^2&=&0\\ \end{eqnarray*}
である。これを満たすような\sigmaを離散的な各d\ \mbox{s.t.}\ d \in ℤ, \rm{minDiff} \leq d \leq \rm{maxDiff}について求め、それぞれについて\log L(d)を求めた後、これが最大値をとるdを擬似的な最尤推定量とする。

\sigmaについての項は\sigma^2と|\sigma|しか出てこないことから、実装においては非負と仮定しても結果は変化しないことを利用すると良い。

実装,性能評価

以上のモデルを既存手法とともにC#にて実装をし、比較をした。実装は以下のリンクよりgistにて閲覧できる。
AtCoderからのデータ取得周りは外部の自作ライブラリに依存してるのでこれ単体では動かないです · GitHub

ABC170 旧モデル 提案モデル difficulty
A -163 -1000 -3425.5
B 14 -792 -872.4
C 233 -414 -166
D 274 323 1033.5
E 625 805 1466.4
F -240 1261 1913.6
f:id:keymoon:20200804132256p:plain
ABC170の推定
ABC171 旧モデル 提案モデル difficulty
A -205 -985 -2837.3
B -77 -1000 -1340.5
C -261 119 466.3
D 38 115 422.3
E -1000 308 733.7
F 614 1035 1721.5
f:id:keymoon:20200804132358p:plain
ABC171の推定
ABC172 旧モデル 提案モデル difficulty
A -167 -1000 -7393.8
B -60 -1000 -1410.4
C 704 347 877.7
D 17 351 944.7
E 710 961 1877.9
F 553 1368 2158.5
f:id:keymoon:20200804132439p:plain
ABC172の推定

旧モデルは収束するのは低難度帯に限られるが収束は早い。一方、提案モデルでは難易度によらず推定を行えているが収束はあまりしているようには見えない。

また、提案モデルでは解がほぼ確実に下方向にズレているのが課題である。そのため、どの程度ズレているのかを確かめてみた。

f:id:keymoon:20200804150254p:plain
推定データと実データ

すると、新ABCに限ってサンプリングしたデータではあるが、実データと推定データが比例しているという傾向が全diffについて見られた。つまり、最終推定値に1次関数による補正をかけたらこのモデルはそこそこな精度になるということである。
ここまで綺麗なズレが観測されるとなると、ここには何らかのモデル自体の欠陥が絡んできているのではないか?と思えてしまう。そのため、ズレがどこから来ているのかということを今後調べていきたいと思っている。

また、ABC/AGC/ARCそれぞれについて同様に調べてみると、グラフのかたむきは0.72程で変わらずに切片のみが変化していることが分かった。

f:id:keymoon:20200804202956p:plain
AGC/ARC/ABCについての推定データと実データ

おわりに

尤度関数と偏微分の式変形がかなり美しい結果に落ち着いたので、かなり満足しています。ただ、実装してみた結果うまく行かなかったので、とりあえず進捗を書くだけ書いておいて本業(競プロ)をしようという不純なモチベーションより筆を取り始めました。しかし、その途中で気まぐれでデータを比較してみるとかなり綺麗なズレが観測できたのでもう一歩な気もしてきました。もう少し頑張ってみます…

*1:https://proceedings-of-deim.github.io/DEIM2020/papers/I4-2.pdf

コンテスト中に最終順位を推定したい

 

概要

表題の通り、コンテスト中に(このまま椅子を温め続けた時の)最終順位を推定したいです。私はac-predictorってやつを作ってるんですが、それにコンテスト中の最終順位の推定機能を組み込めたら更に便利になるなってのがモチベーションです。

ただ、問題を詰めていくに従ってどん詰まりになってきたので頭の整理のためにでも書いてます。もし何らかの解決策を少しでもご存知であれば、是非教えて頂けると幸いです……。本稿で使用したnotebookはGistに上げておきました。

この記事でレートと言った場合、明示しない場合は内部レート(APerf(average perf), パフォーマンスの単純な加重平均)のことを指すことにします。

要件

リアルタイムに推定を出したい。できるならばすべての処理をクライアント(=JS)側に任せたいが、流石にブラウザ上でやるには厳しい計算が出てきた場合はサーバサイドでの計算もやむを得ないかも。(その場合はバッチ処理のような形を取る)

現段階での考えている手法

とりあえず、(このまま椅子を温め続けた時の)最終順位を予測するためには何が必要かを考える。最終順位=今の順位+自分を抜いた人の順位であるため、全ての人について自分を抜く確率がどれくらいあるのかを計算したい気持ちになる。

そのためには、それぞれの人が問題を一定の時間以内に解く確率を計算したくなる。

AtCoder の問題に取り掛かってから AC するまでにかかる時間の対数の平均値は、レーティングの1次式で表現できると考えられます。

pepsin-amylase.hatenablog.com

とあるため、これは問題のDifficultyと分散を求めると良さそうである。

よって、各問題のDifficultyと分散を求めることとする。

ここで、Diffは「コンテスト中に50%の人が解けるレート」として計算されているため、「コンテスト終了時に50%の人が解けているレート帯」をそのままDiffとして考えることにする。

コンテスト本番の (ユーザー, 問題) の対を1つのデータ点として内部レーティングを説明変数、その問題に正解したかを被説明変数とするロジスティック回帰によって正解予測モデルを作っています。このモデルで正解率が50%になる内部レーティングを difficulty としています。

pepsin-amylase.hatenablog.com

ここまでをまとめると、

各問題について:

  • コンテスト中の順位表よりDifficulty(=終了時に半分の人が解けているレート帯)を推定
  • そのDifficultyより各人が自分を抜く確率を推定
  • そこから最終順位を予測

 というプロセスで推定を行うということになる。

Difficultyを推定する

追記(2020/7/31)

本項でいくつか記事を参考にさせていただき、またAtCoder ProblemsのDiff推定部分の担当もしていらっしゃるid:pepsin-amylaseさんより「最近それをやった論文がある」と教えていただいたため、それを読んだ。それを用いた場合C問題程度まではきれいな推定ができるが、それ以降ではまだきれいな推定ができなかった。

その後も手法を改善する努力などは行っているため、何か進展があればここに追記する。

(追記:記事を書きました。未だに上手くはいっていません…)

keymoon.hatenablog.com

(追記終わり)

 

Difficultyを推定するに当たって、終了時に半分の人が解けているレート帯を求めることをしたい。

まず、観察として「全ての問題について、各レート帯の何割の人がどの程度の時間で解けているか」をプロットすることとした。

その結果が以下である。

f:id:keymoon:20200726005112p:plain

各問題についてのレートと解答時間の関係


縦軸のaperfは内部レート、横軸は時間の対数である。

赤の点はがそのレート帯の人の50パーセンタイルが解けたときの時間、黄色が40/60,青が30/70… といったことを示している。

これを見てもわかるように、それぞれのパーセンタイル毎の値は微妙な曲線になっている。

また、各レート帯毎の解ける時間については対数正規分布になっているように感じる。

これらの観測を基に、コンテスト中の順位表から終了時に5割の人が解けているレート帯(すなわち終了時刻に赤点線が当たる場所)を求めたいという気持ちになる。

f:id:keymoon:20200726005036p:plain

開始10分時点での情報をプロットしたもの

そのためには、「各レート帯での解けるまでの時間の中央値を推定」→「その中央値を基にDiffを推定」というステップを踏むべきであると考えた。

課題

ここまで考えたのは良いものの、その推定をどのように行ってよいかが分かっていない。

ここから、行ったことと考察を書く。

中央値を推定するフェーズ

対数正規分布になりそうだという観測を基に、その時点での結果について正規分布のフィッティングを行うこととした。

どうにも打ち切りモデルというものによる推定になりそうだが、このような高度なモデルを使用することなくcurbe_fittingを行ってみることとした。

teratail.com

f:id:keymoon:20200726010257p:plain

1000秒時点のデータを基とした、curbe_fittingによる推定

その結果、20分程度まではある程度まともなデータが得られたが、それ以降では頓珍漢な結果が出てしまう結果となった。

どこかで分散を求めてしまって、それを基に全てを推定とかのほうが楽なのかもしれない……?

Diffを推定するフェーズ

一度対数を適用してもまだ対数っぽい見た目をしていたのでもう一度適用すると良いかもしれないと思い、適用してみる。

f:id:keymoon:20200726005400p:plain

log(log(x))を横軸の目盛りに取った場合

結果としては、まだ対数っぽさが残っている気がする。

最初の方に解けた上位陣を無視して、最後の方の傾きだけを基に推定すれば良いかとも思ったが、できるならば最初の方から推定できていてほしさがあるため、上位陣込みのデータを基に推定可能な汎用的なモデルを構築したい。

あと、中央値となる点の「確実性」の重みは、推定がどの程度の点の量で行われたかによって変化すると考えた。そのため、それを加味した上でフィッティングは行うべきな気がする。

終わりに

数学的な議論を踏まずに観察でモデルを構築しようとしているのが良くないのかもしれないですね……。

これらの推定やモデル案について、少しの提案や意見でもあればお待ちしています。宜しくおねがいします。

TSGCTF 2020 Write-Up

2020年7月11日～7月12日にかけて開催された、TSGCTFのWrite-Upです。

今回はソロチームとして参加し、Sanity CheckとSurveyを除いてはMiscの2問のみを通し、512点を獲得して38位となりました。

ここでは、自分の通した問題についての解法を記したいと思います。

 

Beginner's Misc

eval(b64encode(input().encode('UTF_8')))==math.pi

となるようなinput()を作れ、という問題。

要するに、eval(s)==math.piで、b64decode(s)がUTF_8として正当であるようなsを作れば良いです。 

とりあえず、UTF_8の形式を見てみます。

Unicode code points   Range    Encoding  Binary value
-------------------  --------  --------------------------
 U+000000-U+00007f   0xxxxxxx  0xxxxxxx

 U+000080-U+0007ff   110yyyxx  00000yyy xxxxxxxx
                     10xxxxxx

 U+000800-U+00ffff   1110yyyy  yyyyyyyy xxxxxxxx
                     10yyyyxx
                     10xxxxxx

 U+010000-U+10ffff   11110zzz  000zzzzz yyyyyyyy xxxxxxxx
                     10zzyyyy
                     10yyyyxx
                     10xxxxxx
from: https://stackoverflow.com/questions/9356169/utf-8-continuation-bytes

この表より、上位3bitが110である場合は次に上位2bitが10のContinuation byteが続く、1110である場合は次の2つにContinuation bytesが続く、11110の場合は… と言ったことが分かります。

また、base64の4文字をデコードした際は3byteになるため、この3byteを一塊として考えることにします。

問題の趣旨に立ち戻ると`math.pi`と等価になるような小数を作れ、という問題でした。ただ、pythonの浮動小数点数のイコールは少々誤差があっても許容されるので、base64に存在する文字のうち整数と除算命令('/')、加算命令('+')を使って近似することを考えます。

ここで、これらの文字について、base64の4文字の塊のうち何文字目に使用した時にどの種類のbyte(0xxxxxx or 10xxxxxx or 110xxxxx or...)を生成するか、という表を作成しました。

 

後は手作業で、ひたすら近づくような解を生成しました。正直全探索したほうがよかった。

できた解はこれで、

>> 379/140+1540274047210746040/3545344156695621040+0o00

3.141592653589793

>> math.pi

3.141592653589793

pythonで実行した際に等価となります。

最後の+0o00はpaddingが必要になってしまったために、適当に表を見て捻り出しました。

 

Self Host

未知の言語で書かれた言語自身のコンパイラが与えられるので、そのコンパイラのバイナリを作ってねという問題。そして、更にそのバイナリによってコンパイルしたコンパイラのバイナリ、によってコンパイルされたコンパイラのバイナリによってflagが入ったソースがコンパイルされるので、そのソースのコンパイル結果をflagを吐くようにしてねって話。

書いていて意味が分からなくなったんですが、以下の記事のhackと同じことを未知の言語でやってねって話です。

0x19f.hatenablog.com

で、とりあえず最初に未知の言語をコンパイルてきるようにしないことには話が始まりません。幸いC-likeな構文ではあったので、自分が書きなれているC#に手作業で直すことにしました。人力トランスパイラと申す。この言語は整数型とリスト型しかなく、文字列も整数のリストのシンタックスシュガーといった形になっています。また、動的型付けな言語であることも予想がついたので、C#の言語機能にあるdynamic型で動的型付けを実現します。1000行ほどにみっちりと出たエラーを気合で2時間かけてつぶし、とりあえずコンパイルが通るようなソースを完成させました。x.cs · GitHub

次に、Thompson hackを実装します。

hackする対象は関数をコンパイルする関数とします。その関数"compile_function"には、関数名と引数リスト、関数の中身の構文木が与えられます。アセンブリを吐かせるのはコード的にめんどくさいので、構文木にコードを追加することにします。

要件としては、「compile_function関数が来たら、書き換えた部分の構文木をそのまま追加し、1token目がflag変数である関数が来たらwrite(flag);の構文木を付け足す」が満たせれば嬉しいです。また、構文木をそのまま埋め込むのもめんどくさいのでコンパイラにあるparse関数を借りさせてもらうことにします。このparse関数は関数(とグローバル変数)しかパースできないので、一旦関数化してパースし、その中身から構文木を引き抜いてくることにします。

ここまでを踏まえて、そのコードを考えるとこうなります。(tokenize関数はないですが、tokenizeした結果をそのまま書くと冗長になってつらいので便宜的にこうしています。)

if (fn == "compile_function") { body = parse(y)[0][3] + body; }
if (body[0][1] == "flag") { body = body + parse(tokenize("f(){write(flag);}"))[0][3]; }

そして、一行目のparseに突っ込まれている変数'y'に、付け足した全体のコード(が入っている関数)が入っていると嬉しいです。なのでそうなるようなQuineを書きます。

とりあえず、このような構造になるようにしたいです。

y = /* ここ以下の字句解析結果 */;
x = /* yのリストを字句解析した結果になるようにがんばる */;
y = tokenize("f(){y = ") + x + y + tokenize("}") 
/* これでyには追加したコードの字句解析結果が入ってる */

このようになるように頑張ると、

y = /* ここ以下の字句解析結果 */; 
x = ["[", "\"" + y[0] + "\""];
i = 1;
while (i < len(y)) { 
  x = x + [","] + ["\"" + y[i] + "\""]; i = i + 1;
}
x = x + tokenize("];") /* xにはリストyの字句解析結果が入っている */
y = tokenize("f(){y = ") + x + y + tokenize("}");

となります。

 最後に、この言語にはエスケープがないため、全ての文字列を別の形式で表すようにします。 先程も述べた通り、この言語では文字列は整数リストのシンタックスシュガーにすぎないので、例えば"flag"は[102, 108, 97, 103]といった形で表せます。こうすることで、yに最初に入れておく字句解析結果にダブルクオーテーションが出てこなくなって嬉しいです。

このようにした結果がこうです。

gist.github.com

あとは、これを先程の移植したコンパイラでコンパイルすれば、Thompson hackが仕込まれたアセンブリを得ることができます。

 おわりに

Self Hostに半日かかってしまい、自分のプログラミング能力の微妙さに悲しくなってました。もう少し早く解いて他の問題にも手をつけられるようになりたかったです。

 

AtCoderで黄色になりました。

これはなに

色ポエムです。ポエムなので大抵が自分語りです。許してください。「黄色になるまでに何をしたのか」を純粋に読みたい場合は、記事を最後まで読む必要はありません。(おまけはおまけなので)

はじめに

2019/06/29に行われたABC132にて、AtCoderで黄色になりました。苦節20ヶ月、とりあえず1つのマイルストーンに到達することができたことを嬉しく思っています。

 

 

黄色になるまでにしたこと

注意 : 途中まで書いて気がついたのですが、「青下位から青中位までにしたこと」の記憶が完全に飛んでいるため、「青中位から黄色になるまでにしたこと」になっている気がします。ただ、記したことは一般論のようなものなので、概ね影響がないと思います。

問題を解く

言うまでもなく、問題を解きました。自分にとって最も効果的だった精進は、「自分がコンテストに出た時に通せたら嬉しい範囲の問題」を解くことです。レート1800台の時は700-800点程度でしょうか。以下のツイートの青くらいの範囲を二日に一問程度解ければ理想だと思います。

 

これにより実力は上がっている実感は実際のところありませんでしたが、明らかに成績は向上しています。自分の考察スタイルは論理的に詰めるのではなく、考察をとにかく手当たり次第に行って考察を進めるスタイルです。解法ガチャとか呼ばれてますね。ガチャの当たり率が上がった気がしました*1。

以下のツイートは黄色になった時点での自分の精進量です。

 

精進グラフです。

f:id:keymoon:20190630222735p:plain

注意ですが、この数を真に受けないでください。自分はJOIの低難易度やABC-A/B等を全て埋めているため、相当「盛られて」います。(2018年冒頭のそれが盛った形跡ですね。)

また、自分の場合は考えることで導き出した答えがより身に入るため、解説ACは行いませんでした。その代わり、テクニックに貪欲になるよう心がけました。

面白い性質や問題を見た際、「その性質がどこまで一般的に通用するか?」ということを考えるクセを付けると良いと思います。これは「素振り典型」とか勝手に呼んでいるものとも近く、「今回の問題はこういう性質があったからこういう方法が取れたんだな!」とか思えると良いです。また、同じくアルゴリズムはできる限り抽象化して理解することをお勧めします。「累積和を二本合わせるテクはXORでも使える!GCDでも!」と個別に理解するより、「累積和を二本合わせるテクは順序を入れ替えても結果が変わらない演算*2全てに使える!」と理解したほうが効率は良いです。

勉強したアルゴリズムは例題を解くだけでなく、ライブラリを作りました。自分は比較的マイナー言語であるC#で競技プログラミングをしているためライブラリは自作せざるを得なかったですが、ライブラリを書くことは確実に理解に繋がります。また、上記の抽象的な性質を捉えることの助けにもなります。

また、面白そうなアルゴリズムの記事を見つけたら貪欲に読み、理解し、ライブラリを生やしましょう。リツイートして #後で読む とするだけに留まりがちではないですか?(自戒)

メンタリティを意識する

コンテスト中の精神管理は、コンテストの成績に直結すると言っても良いであろう事項です。しかし、あまり言及を見かけません。みなさんも以下のような経験はありませんか?

  • いつもならば解けなさそうな高難易度の解が見え、緊張してしまったため自明な嘘だと見抜けなかった。
  • 残り5分で実装を終えるも緊張してデバッグが不可能になり、自明なバグを見落とす。
  • 自明であろう問題でWAを出してしまい、その後の問題が読めなくなる。
  • 順位表を見て、自分の順位の低さと推定パフォーマンスの色に動揺してしまう。

自分は全てありました。そして、これを克服できればパフォーマンスが上がることも明らかでした。

ここで、自分の行った対処を紹介します。

まず、通常時から成功体験を積むことです。高難度を何問か通せた経験があれば、コンテスト中もある程度落ち着けるようになります。また、WA判定を受けた際、できる限り平常心を保つよう心がけました。練習でもWAに動揺していたら本番でも動揺するのは当たり前です。さらに、普段の精進中にもコンテスト中に行う思考を心がけることも大切です。動揺するとどうしても頭が真っ白になり、何をするべきかがわからなくなってしまいます。普段からやるべきことを心がけていれば、自然と本番でもできるようになるものです。

自分が最もコンテスト中のメンタル管理に成功したと思った事例は、終了40分前から考え続けて10分前に考察が終わり、3分前に提出したものがTLE判定を受けた際の対処に成功したものです(画像)。これは成功体験となり、自分のメンタルの強さに対する大きな自信となりました。

f:id:keymoon:20190630233103p:plain

また、コンテスト外での精神状態も重要です。

highestを更新しない期間が(たった4ヶ月程ですが)ありました。この時は問題をコンテスト外で解いていなかった上に競プロにフォーカスしていなかったので当たり前ではありますが、コンテストに出る習慣を失わなかったのは結果として良かったと思います。継続することは衰えを減速させることが可能です。

精進に気持ちを向かわせることも大事です。ただし、これは自分があまり上手くないのでなんとも言えないです。自分の場合は「精進したい気持ちになるまで待つ」ことを心がけました。焦ると焦りが先行していいことがない気がします。寝ようと無駄に焦っておふとんの中で眠れなくなるアレと同じですね。

それと、人のやり方/言説に惑わされないようにしました。人のやり方は参考に留めるべきです。もちろんこの記事も。using namespace std;をやめるかは自分で判断することですし、解法ガチャも無証明もOEISエスパーも、自分の判断で行うべきことです。やるかを決定する過程で人の意見は当然参考にするべきですが、無条件に意見を信奉して自分を見失うことは避けた方が良いです。自分の体に合った方法を見つけましょう。

最後に

まだまだ書きたいことがあった気がしましたが、多分これくらいで十分な気がします。コンテストで使った知識を載せて終わりにしたいと思います。思いつく限り列挙しているため、抜けは確実にあります。許してください。

使った知識

 

おまけ1:茶～青色になるまで

色ポエムをそもそも今まで書いたことがないということで、青になるまでの分を書いてみました。

最初は本編に入っていましたが、あまりにも自分語りが過ぎるので分離しました。個人的にはこれよりおまけ2を見てほしいです。

競技プログラミングを始めるまで

はるか昔、Objective-CでiOSアプリケーション開発の触りをやりました。思えばあの頃、塾の課題を全探索してサボっていた僕は本質的に競技プログラミングがやりたかったのかもしれません。当然競技プログラミングなんて知らない僕は次第に飽き、フェードアウトしていきました。

プログラミングを再開したのは2016年の12月です。その当時ハマっていた筐体音ゲーを家でプレイしたいという欲求からUnityに手を出します。結果としてプレイアブルなものが完成しました。ここでプログラミングの楽しさを知り、NAudioを弄ってサンプル単位でループ再生が可能な音楽プレイヤーを作ったりTwitterのbotを宅鯖で運用するなどしてしました。

2017年10月初頭、以下のツイートを見かけます。

このツイートを見て「競プロ」という概念を知りました。

2017年11月初頭、文化祭が終わって労働から開放された僕は暇になります。AtCoderでC#も使えることを知った僕は、競技プログラミングでもを始めようかとぼんやり思っていました。

さて、僕はその後開催されたABC077に出損ねます。これは、かの有名な「Small Multiple」による大虐殺回でした。これに出ていたら恐らく競プロを継続していないでしょう。運命に感謝。

茶色になるまで

f:id:keymoon:20190630193506p:plain

紀貫之みたいなノリでABC078に参加しました。

このコンテストはDの入力受け取りのみにしかfor文を要求されないようなコンテストで、なんと初回参加で17位を取ることができました。

f:id:keymoon:20190630200900p:plain

 完全に味を占めた僕は、こうして茶色に、競技プログラマになりました。

  • 使ったテクニック/知識 : 入出力、foræ–‡

緑色になるまで

あまり覚えていません。コンテストに継続的に参加し、無事緑まで到達することができました。

f:id:keymoon:20190630203612p:plain

水色になるまで

ここで、僕は大きな失敗を経験します。JOI予選落ちです。バチャをしていて勝率が80%程度だったため、高を括っていたら無事落ちました。残念。

ABCと間違えてARCに出たショックからTwitterアカウントを動かし始めた*3僕は、2017年最後のABCで水色になることができました。

  • 使ったテクニック/知識 : DP、シミュレーション、埋め込み*4

青色になるまで

水色になった僕は蟻本などを読み、本格的にアルゴリズムの勉強を始めました。しかし、精力的にやろうとしなかったためコンテスト3回分ほどの停滞期(?)を迎えてしまいます。

学年が上がるまでに色を変えることが目標だった僕は非常に焦り、少しずつではありますが蟻本を読み進めました。AGC→構築回→速解きと成功を重ね、恐らくこの時点での実力であった青下位に急激に突入しました。この後、その影響で青下位での停滞が続くことになります。

  • 使ったテクニック/知識 : エラトステネスの篩、imos法、UnionFind、next_permutation、テストケース特定

おまけ2:タイムカプセルのはなし

これはなに

 青になった週の僕が「ブログに書くネタにどうせ困ってそうだから」みたいな理由でタイムカプセルを遺してくれていました。生意気ですね。ありがとうございます。

正直すっかり忘れていて、さて記事を書くか!となった時に電撃が走ったかのように思い出しました。思い出した時は本当に感情が爆発しそうになりました。月並みな表現だとエモいって奴です(語彙力)。

読んでいる時に一段落ずつコメントをつけていたら、ちょうど対談のような感じになりました。ということで、対談企画と題して放流したいと思います。現代の社会通念上不適切な表現もありますが、改変するのも何かが違うと思ったのでそのままにしました。

ただ、書いていることは上述の通り記事のネタになっているため、内容の重複も多いです。要するに出涸らしですね。

本編

とりあえず、黄色おめでとうございます。青までは競プロをしていればなれて*5、黄色が実力が保証されるラインだと感じています。

ありがとうございます、本当に。それにしても、「青までは誰でもなれて」って凄いこと言ってますね。全くそんなことはないのに。実力保証されちゃった。わーい。

 

黄色が凄い人なのはどう考えても明らかなので、もし上を見て卑屈になっているなら更に上を見ることを一旦やめ、下を見てみてください。昔の自分がちっぽけに見えることでしょう。

すごい人だって すごい人だってさ。嬉しいです。レートの価値とか云々言われてますけど、あなたから見れば今でも十分凄いですよね。今の僕が橙を見るのと同じように。

まあ卑屈にはなってないですね。ということはあなたが卑屈になってるのかな?もっと素直に喜べばいいのに。でも、あなたからほぼ成長していないみたいな感覚はありました。そんなあなたから見ても十分黄色は凄いんですね。面白いです。成長できたかな。

 

グラフはどんな形でしょうか。ギリギリ掠った?調子が良くてブチ抜いた?青の頃より、更に停滞へのプレッシャーは強くなっているはずです。負けないように、そして「レートを意識しすぎるとつまらなくなる」ということを忘れないでほしいです。

 グラフね、ギリギリ掠りました。本当に2050適正って感じで、漸近していく感じで近づいていきました。これからが大変そうです。

レートを意識しているとつまらなくなる、まあそうかもしれないですね。少し前の停滞期は実際辛かったです。でも不思議と停滞に対する恐怖はないですね。一時期の停滞を克服したからかもしれません。停滞については後述します。

 

ところで、どのような精進を積めば黄になれましたか?今の僕は解説を読む癖もないですし、問題も余り解かなくなってしまいました。600点ですら通せるか怪しく、平常時なら400すら億劫で通せないことが多いです。

 精進、むちゃくちゃありきたりな質問ですねそれ。そう思ったのだけ覚えてますよ。「ありきたりな質問しか出てこない」って。
600ですら通せるか怪しく400ですら億劫、実は今でも変わってないんですよね。やっぱ成長してないじゃないか!(というか青なりたてのあなたが「600を通せるか怪しく」って、それができたら黄色ですから。目標高すぎ。)
でも、(体感は別として)実際600は安定して通せてます。確実に成長はしたんだろうなあ。
「どのような精進を積めばいいか」については次の質問が関連しそうなので、一緒に答えてしまいますね。

 

通常時にやる気を出すコツはなんですか。春への思いでしょうか?それとも、黄色に対する思い?

通常時にやる気を出すコツ、僕がうまく行ったのは、「やる気を出すというより「やる気になるまで待つ」」って奴です(眠い時に布団に潜って寝ようと努力するより、眠さを待ちつつ読書をするのと同じですね)。でもすぐやる気が出したいって?その方法は僕もまだ分からないです。ごめんなさい。
僕がやる気を出すきっかけになった話をしましょうか。これが面白くて、「春への思い」ではないんです。あなたは将来、残念ながら春合宿に行けません。怠惰なので精進をしようとせず、本番に自明貪欲を見落とします。それが悔しいのかなんなのかはわからないんですが、何故かやる気が出てきました。今でもそれは継続しています。
で、どんな精進を積んだかですよね。個人的にはこれといったものはありません。

問題を解く際、解説ACはしなくて良いです。(だってあなたは考えたものの方が頭に残るでしょう?)なので、自分が解けるか解けないかギリギリ程度の問題を考えるようにしましょう。

それと同時にやらなければいけないのは、新しいテクニックを身につけるようにすることです。これについてはアルゴリズムの話とかと繋がりますね。後述します。

 

アルゴリズムはどのようにして学びましたか?僕は構築等の地頭ゲーは得意ですよね。しかし、アルゴリズムができなければ黄には行かないはずです。

正直なところ、あなたがその後勉強して必要になったアルゴリズムはありません*6。強いて言うならセグ木で数回殴りましたが。ただ、アルゴリズム/データ構造の勉強は楽しいですよ。実際のところ。それと、恐らく橙を目指すに当たって本格的に必要になってきます。
それよりも大事なのは文字になっていない典型というか、あれです、素振り典型です。直感力とも言えます。
僕は問題を解いたり、何らかの面白いものを見たりした時に「どういう状況であればこのテクニックが使えるか」と一般化することを心がけました。累積和は結合法則云々が成立するなら使える、みたいなやつです。
ああそう、構築は割と出るようになって嬉しいですよ。ちゃんと全て通せています。それにしてもあなた、自分の地頭に謎の自信がありますね?僕はもうないです。

 

必ず青の間に停滞期は訪れている筈です。その時に、どのようにして乗り切りましたか?落ち込んだのはそうですが、気持ちを切り替えることはできましたか?

停滞期ですか…ありましたねぇ。というかJOI後の数ヶ月以外は全てが停滞期でした。
Highestを更新できない期間がとても長いのは本当に心がしんどくなります。ただ、そういう時でもコンテストに出続けました。まだコンテストは楽しいと思えていたので。継続は大事。精進もせずに怠惰に出るのは決して悪いことではありません。いつか成功し、やる気が戻るきっかけとなったりします。

 

勉強など他のするべきこととの両立はできたでしょうか。もしできてないなら、流石にマズいので頑張ってください…

お前お前お前お前～! 言うじゃないですか。分かってるじゃないですか。そうなんですよ、できてないんですよ。マジヤバい。
いや今日でTwitter控えるんで。マジで。明日から本気出ーす。

 

最後になりますが、とりあえず大学卒業までに橙になれると嬉しいですね。応援しています。

これ本気で思ってますか? 去年*7中に黄色とかあなたが言っていたのを覚えているので、その目標が達成できなかったときの精神安定の為に書いたとか。
深読みしすぎか。だとすると、この目標はぶれてないですね。大学卒業までに橙。方針通りに進めているのかもしれません。
頑張ります。まずは受験の方をですけどね。

最後に

過去と現在の深夜ポエムを晒してしまいました…(絶対後悔する。)

タイムカプセル、いいものですね。普段は客観視することができない自分を客観視することができました。もう少し話を聞きたかったな、って思ったりしました。

*1:ちなみにくじ引きサイクルというゲームはガチャの当たり率を上げて当たりを引くことが目標のゲームです。時間が溶けるので絶対にやるべきではありません。自分の最終リザルトは黃229個です。

*2:これを「結合的な演算」または「結合法則が成立する」と呼びます。セグ木に載るやつですね!

*3:当該ツイート(リンク)、しかもパフォ1955の大成功でした。なに凹んでるんだ。

*4:素数リストをネットから落としてきて埋め込み、エラトステネスの篩を使わずに通しました。

*5:これが不適切な表現です。青になりたてで卑屈になってるだけです。全くそんなことはないと思います。許してください。

*6:これは嘘で、BinaryHeapの実装(C#にはないため)、行列累乗が役立ちました

*7:青になった年と同じ年

Harekaze CTF 2019 Write-Up

概要

2019年5月18日～5月19日にかけて開催された、Harekaze CTFのWrite-Upです。

所属しているチーム「生活習慣崩壊ズ」は7問通して910点を獲得し、28位となりました。そのうち、自分は4(+1)問通し、500(+100)点を獲得しました。

ここでは、自分の通した問題についての解法を記したいと思います。

ONCE UPON A TIME(Crypto 100pts)

鍵となる行列keyがあり、フラグを5×5行列に整形した行列flagについてflag×key又はkey×flagが与えられる(これをcryptoとする)。この演算は251(素数)で割った剰余環上で行われる。

素数mod上での積には逆元があるので、当然逆行列を考えることもできる。 逆行列の求め方はいろいろあるが、余因子行列の各要素を行列式で割る求め方が最も良いと思う(逆元を適用させやすいため。)

嬉しいことに、keyとなる行列には逆行列が存在した。これをkey^-1とすると、crypto×(key^-1)又は(key^-1)×cryptoのどちらかがflagとなることがわかる。これを計算すると、求めたいflagが出てくる。

Encode & Encode(Web 100pts)

  JSON形式で指定したファイルパスからfile_get_contentsで読み込んだファイルがクライアントに渡される。file_get_contentsにパス文字列には以下のようなバリデーションが掛けられていて、さらにクライアントにファイルを渡す前に正規表現でフラグに該当する部分が削除されるようになっている。フラグは/flagにあるので、ここをなんとかして読み込めたら勝ち。

f:id:keymoon:20190519144301p:plain

まず、/flagを読み込むことを考える。JSON形式の文字列を一度パーサに通しているため、おそらく何らかのエスケープをしておいてもエスケープを戻してくれるだろうと推測する。いろいろと実験をすると、unicodeエスケープ(\u0000)を戻してくれそうだと分かる。よって、{page:"\u002f\u0066\u006c\u0061\u0067"}のようなクエリを投げる。すると、{"content":"HarekazeCTF{<censored>}"}と検閲済みのflagが帰ってくる。元の情報を損なわない形で整形なり切り取りなりをして正規表現/HarekazeCTF\{.*}\/をすり抜けるようにすれば良いと分かる。

PHPにはフィルタと呼ばれる機能があり、php://filter/convert.base64-encode/resource=[resource]とするとリソースをbase64エンコードして返してくれる。これを使い、php://filter/convert.base64-encode/resource=/flagをunicodeエスケープしたものを投げつけて終わり。

[a-z().](Misc 200pts)

JSFuck等の縛りJS系問題。制約は問題名の通りで、英小文字と()、ピリオドのみ使用可能。

この制約の下、(数字の)1337と評価されるJavaScriptを200字以内で書けたら勝ち。

まず使えるオブジェクトを列挙する。JavaScriptは悪魔的な言語なので、起点となるオブジェクトがあれば大抵なんでもできる(要出典)。よって、起点となるオブジェクトを探す。グローバルが空になっているため、通常の環境のようにいろいろと使えるわけではない。調査の結果、eval,console,escape,unescapeあたりが使えそうだと分かった。

1337を生成する方針として、文字列としての"1337"から生成することとする。これはNumberのコンストラクタに入れることで実現でき、コンストラクタはその型のオブジェクトから取得することができるからである。

次に、文字列を生成する方法を考える。流石に1337という文字列が落ちている筈もないため、一文字ずつ生成してから空文字列に対して.concatをしていくアプローチを取りたい。

空文字列はs.substr(s.length)とすることによって取得できるため、どこかにある文字列を使えば良い。これには、eval.nameが最も短く済みそうである。よって、空文字列はeval.name.substr(eval.name.length)として取得できる。

次に、concatする各"1","3","7"について探す。JavaScriptはキャストを結構緩めにやってくれるので、これらはStringでなくNumberでも良い。様々な調査の結果、1はeval.length、3はconsole.log.name.length、7はconsole.context.name.lengthを使うこととした。 最後に、今までの結果を纏めてあげる。

eval.length.constructor(eval.name.substr(eval.name.length).concat(eval.length).concat(console.log.name.length).concat(console.log.name.length).concat(console.context.name.length))

これは180byteなので、制約に収まる。

Avatar Uploader 1(Misc 100pts)

finfo_fileがpngかつgetimagesizeのimagetypeがpngでないようなものを出せば良い。 finfo_fileはシグネチャのみを判定しているため、シグネチャだけ合っていてimagetypeがバグるような「画像」を突っ込めば良い。 具体的には、以下のようなバイナリを突っ込んだ。

f:id:keymoon:20190519032438p:plain

Twenty-five

ppencodeのコードが換字式暗号でスクランブルされた状態で渡されるので、デコードしなさいという問題。換字式暗号パートの本質部分は自分ではなく漁師が片付けたが、なぜか実行しても上手く実行されなかった。

ということでppencodeに掛けた状態のものをデコードする作業をすることになった。まず、ppencodeのエンコーダを探してエンコード方法を確認する。少し探すと、

shinh.skr.jp

ここによって実行されていることがわかった。ソースを読む。すると、"$_="";v112.114.105.110.116.32.49"といったソースに整形されるような式を評価し、もう一度評価することによって実行を実現しているようだ。

f:id:keymoon:20190519054803p:plain

置き換え部分のロジックを読むと、ピリオドの部分と数字の部分が交互に出てきていることが分かる。数字は個別に置き換わっているようなため、置き換えている配列を確認する。すると、綺麗に文字数が1ずつ増えていることがわかる。

f:id:keymoon:20190519054305p:plain

数字と何文字差があるかは実行時の乱数依存だが、コードに必ずといってもいいほど含まれる空白はコードポイントが32で、これは通常のコードに含まれる文字のうち最小であることから差分が推測できる。

このようにしてコードを復元すると、

my $flag="ViZGUiyGEON{Gq.zeUeQGtei.FZd/zeUe/NZGToGqvR_iqipRheh}";$flag=~y/raEKcNnVMSwJgCbLAfmOuIsBWliXvtGxdHekUpjqFQTZhPoDzYRy ouvqriklpzawthxgfnbjcmdsye/ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz/;print $flag;

となる。これを実行し、フラグHarekazeCTF{en.wikipedia.org/wiki/Frequency_analysis}を得た。

感想

今回はそこまで真面目に参加できなかったが、様々な問題を解けてよかった。特に、縛りJSの問題は前から挑んでみたいと思っていたためとても面白かった。相変わらずだが、binary方面に全く手を出せないのが悲しいのでそこの力もつけていきたいと思った。