平面グラフアルゴリズム
お待たせいたしました。Competitive Programming Advent Calendar 2019 8日目の記事です。
平面グラフとは
平面グラフとは、平面に辺を交差させずに描画できるグラフのことをいいます。現実世界の例では多くのroad mapがそうであったりします。平面グラフでは、たとえば最短路問題がで解けたり(Frederikson)、多くの最適化問題で、通常のグラフよりも効率的なアルゴリズムが発見されています。
この記事では平面グラフの性質や、アルゴリズムなどを紹介していこうと思います。もともとは実装しようと思っていたんですが、ちょっと人生が忙しいので保留です(一生保留しそう)(ごめんなさい)。
基本編
Eulerの公式
連結な平面グラフについて、頂点数を
, 辺数を
, 面数を
とすると
が成り立つ。非本質ですが、頂点は0次元、辺は1次元、面は2次元なので、符号と
が共通していますね。暗記向けです。
単純な平面グラフ(
)について、
これにより、辺の数がであることがわかります。そうすると面の数も
です。平面グラフアルゴリズムの計算量に
しか現れないのはこのためです。ちなみに、アルゴリズムの計算量などで
といっても定数倍が大きいものが多い印象です。
Kuratowskiの定理
グラフが平面グラフである必要十分条件が、「
は
をマイナーに含まない」ことをいう定理です。
は
頂点の完全グラフ、
は
頂点の完全二部グラフを指します。グラフ
がグラフ
のマイナーであるとは、
が
から、(1)辺の除去, (2)辺の縮約, (3)孤立点の除去を繰り返して得られることをいいます。
それぞれと
https://www.researchgate.net/figure/Excluded-minors-for-planar-graphs_fig1_238872253
グラフの集合がある性質
に対してminor-closedであるとは、
の要素を縮約したグラフも性質
を満たすことをいいます。明らかに、「平面に描画できているグラフを縮約したグラフは平面に描画できる」ので、平面グラフはminor-closedなグラフの集合となります。興味深い点は、
はいずれも平面に描画できないのですが、平面に描画できる必要十分条件がこの2グラフの(マイナーとしての)有無で決定されるということです。証明は省略しますが、興味のある方はぜひ調べてみてください。
中級編
グラフの平面性判定
与えられたグラフが平面グラフかどうかはで判定ができます。これめっちゃすごいですね。アルゴリズムは、いろいろなものが開発されてきましたが、Boyerのアルゴリズムが有名な気がします。
アルゴリズムの説明(アルゴリズムは全然中級じゃないです)
お絵かきをしました。適当に書いたグラフなのでとくにコーナーケースじゃないです(すみません)
本質は線形にするための実装と正当性の証明なんですが、手でやる分には比較的簡単にできます。
- グラフをdfsし、訪れた順にidを振っていく。dfs木と後退辺を覚えておく
- 各辺の優先度を
とする。つまり両端のidのmin
- 辺を優先度の大きい順に追加していく。同じ優先度はなんでもいいけどdfs木の辺優先
- そのときに2連結になるように、頂点を適宜増やしていく
- 新たなループが生成されるとき、externally activeな頂点を外平面に向けるようにflipする(将来的に処理される辺はすべて外平面に来ているはず)
- 最後まで追加できれば描画完了。無理なら平面グラフでない
ある頂点がexternally activeというのは、その頂点またはその子孫から後退辺をたどって、今見ている優先度よりもidの小さい頂点に行けるということで、要は今後辺を追加されるときに面に埋め込まれちゃうかもしれない、気をつけなければいけない頂点です。
描画完了できない場合は平面グラフではないんですが、詰むケースは数パターンに場合分けされ、それぞれの場合についてどの部分グラフが禁止マイナーになっているかを調べることができます。
かなり雑に説明しちゃったんですが、 http://www.th.cs.meiji.ac.jp/assets/researches/2007/toyota/index.html に日本語記事があるので気になる方は照らし合わせながら追ってみてください。
Separator定理
えー、一番の本質です。平面グラフで一番うれしい性質です。グラフの頂点集合の分割
で、(1)どの辺も
を直接結ばなく、(2)A, Bの頂点重みは全体の2/3以下にできるとき、頂点集合
を
のセパレータと呼びます。グラフに
のセパレータが存在するかはかなり重要な関心であり、なぜかというと、
のセパレータが存在するなら、分割統治アルゴリズムが使えるからです。うれしいことに、平面グラフは
のセパレータをもつことが知られており、
でセパレータを構築できますLipton & Tarjan。実際多くの平面グラフアルゴリズムはこのセパレータの性質によって高速性が導かれています。
木幅が
この記事ではあまり深く書くことがないです。
たぶん上級編
直線による描画
平面グラフの定義において、平面に描画するときに直線を使う必要はありませんが(曲線でよい)、実は任意の平面グラフは直線のみを用いて平面に描画が可能です。もっと言うと、のサイズのグリッド上の格子点に頂点を配置して、かつ、直線のみを使って描画することも可能です。
最大カット
最大カット問題は、一般グラフにおいてNP-Hardであることが知られていますが、平面グラフにはアルゴリズムが存在します
アルゴリズムの説明
これもまたさまざまなアルゴリズムが提案されてきたのですが、シンプルで有名なのがA simple MAX-CUT algorithm for planar graphsだと思います。
平面グラフと双対グラフです。
頂点をに倍加して、最大マッチングを考えます。
連結な単純グラフ
が入力として与えられたとき、まず
をとる。双対グラフの辺のコストは、その辺が横切る元のグラフの辺のコストと同じにする。
に置き換えたグラフを考える。
以上のグラフでmaximum weighted matchingを考える。必ずperfect matchingが存在することが示せ、このとき、各
双対グラフでのEulerian subgraphと元のグラフのカットには1対1対応があり、この最大重みeulerian subgraphが元のグラフでの最大cutになっている。
計算量についてまとめます。平面グラフの双対グラフも平面グラフであり、頂点数、辺の本数もで、頂点を4倍加してもオーダーは変わりません。あとは平面グラフのmaximum weighted matchingを考えればいいのですが、これはTarjanによると
なので、そのままmax-cutもこのオーダーで解けることになります(クソ雑)。
最小交差数
A separator theorem for minor-closed classesによると、固定されたについて最小交差数が
以下か判定する線形アルゴリズムがあるそうです。
同型判定
平面グラフの同型判定は線形で可能です https://dl.acm.org/citation.cfm?id=803896
Minor-closedグラフとセパレータ
さて、平面グラフはminor-closedなグラフのクラスでしたが、minor-closedな性質をもつぐらふの集合は他にもあります。たとえば、toroidalグラフとよばれる、torusに辺の交差なしに埋め込めるグラフもminor-closedです。
A Separator Theorem in Minor-Closed Classesでは、minor-closedなグラフはのセパレータをもつのでは？という話がされていて、実際に
をマイナーとして含まないグラフについて
のセパレータを持つことを証明しています。これは応用範囲が広く、たとえばbounded degreeのグラフが
のセパレータをもつことなどがすぐに導かれます。
ちなみに、bounded average degreeグラフはこの性質を満たしません(証明はErdos)。
のセパレータをもつなら、分割統治が回るので、平面グラフ以外にも多くのminor-closedなグラフについて平面グラフの場合と類似する高速なアルゴリズムがあると思います(あまり詳しくありません)
最後に
平面グラフやべーーーーー やべーーーと話題に
気になったポスター
IPのBranch&Broundを、GCNNを使って決定するという論文。なんでGCNNなのか結局ポスターを見る限りはわからなかった。比較対象がみんなアで、そんなに強くなさそう感がすごい。
joisino論文。distributed local algorithmという視点がいいし安心の解析がある。
手書きポスターニキ。ERランダムグラフから適当に辺を取り除いたグラフ同士の同型テスト(matching)やSimilarityを求める多項式アルゴリズム・準多項式アルゴリズムを作った。すげ絵
cascading portfolio problemとは、アルゴリズムとテストケースがあり、それぞれのアルゴリズムがどのテストケースをpassするかや、実行時間が分かっているときに、アルゴリズムの順序で、「テストごとの、初めてテストを通過するまでの時間、の和」を最小化するものを求める問題。いろいろなFPTを構成いている。なぜNIPSに出した。
Optimal Transportの計算量を久しぶりに改善したらしい。かなりグラフ理論系
点の追加や削除にも対応したFacility Location問題を解いているっぽい。とりあえず愚直よりよい計算量が挙げられたと書いているけど、クエリ毎はうくにきあちゃんだろ。
Universal Approximation Theorem for GNNs?
絶対に後で読む。
うわさのpaper. NNの中には構造的に特定の判定問題を得意とするものがありそうで、実際ランダムにネットワークを構築しながら探索する手法で、従来のよりもずっと小規模なネットワークで匹敵する性能のものを発見。
グラフ上のsemi-supervised learningでベンチマークを軒並み改善していそう
特徴のあるグラフについて、そのグラフラプラシアンを解析することで、analyticalに性質を検証するっぽい。
うわさの論文2. 後で読む。
グラフの特徴量をdiffuseしたらいろいろうれしいという論文だった気がする。汎用的手法っぽい。
これかなりすごい。GNNが任意のグラフを識別できることとグラフについての任意の関数を近似できることが等価であることを示したっぽい。後で読む。
よくわからんけどボロノイ図出てきたから興味ある。
タイトル的にかなり面白そう。後で読む。
タイトル的に面白そうでかなり人がいたので写真を撮った。
kNNを学習するのすごい。
ピクセルごとに微妙に加減する攻撃はあるけど、ある関数を作用させる攻撃はあんまりなさそうで、それを考案した。出力画像がなめらかなのが、見た目的な特徴っぽい。
既存のクラスタリングアルゴリズムにえいやっとすると、fairなクラスタリングがほぼ同じ精度でできるっぽい。fairとは、大きさが偏っていないということ
クラスタリングをtime seriesでやるっぽい。内容はしらんけどアイデアおもろそう。
ランダムなネットワークの入力ビットをどれほどflipすると結果が変わるか、そして学習済みモデルだとどうなるか、を調べた論文
Optimal Transportしらんけどグラフの距離を測るのはおもしろい。
上に同じく。
すごく面白い観点からGCNの性質を見ていると思う。後で読みたい。
グラフの距離おもしろい定期。
GNN関係なさすぎるけどこんなことができるのか系。普通にすごすぎる。見世物として完成度高い。
タイトル的にメモ。
上に同じ。そろそろ疲れた。
ポスターやべ〜〜〜〜〜。今度読むかも
VCのLP緩和がHalfIntである証明
https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf
LP緩和の解はシンプレックスの端点であり、シンプレックスの端点は、「異なる2つの実行可能解の合成でかけないこと」と同値。
non-halfintがあったとすると、その解をεだけ上下にずらしたものも解になることを示し、矛盾を導く。
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
https://hochbaum.ieor.berkeley.edu/html/pub/EJOR-3var.pdf
IPの制約がMonotoneのときは、minCutに帰着して多項式時間でhalfintegral解が求まるっぽい。目的関数は非線形でもいいらしい。
あとで読む。
非CTF勢によるCTFの解き方
writeupです。
++age;
— Tasker (@task4233) December 4, 2019
今日誕生日なので, 1日限定でCTFを開催してみました。https://t.co/U02CnUnGge
問題はあまり難しくないかもしれませんが, 息抜きにでも参加してみてください！
深夜にツイッターを見ていたら面白そうなものが生えていたので暇をつぶそうという気持ちになりました。ちなみに当方、ほぼCTFの経験はありません(数年前のSECCONオンライン予選で誰にでもできるような助っ人をした程度)
一応全完しました(8位) 追記: 後半に問題が増えたようで10位に落ちていました
むずかった問題のEditorialを書きます。
Matryoshka-2
N3q8ryccAAShfltxJQIAAAAAAAAhAAAAAAAAANCfkrrgAewBsV0ALGiBABn6B/yQVSAphFxUm968 7FM/eBKHsAAl3tYLd6ikKF8eCxfBpakkNinQtBUJ08Ne8VXEbXadlBDf2kjHQRmn9R4jtG5gEczh 2uyf6CbHkRb3fK5OVwYITpphK/tDcMG96Kn2xE+sfmAXAwQADS/6WNRgi+P/LBZbGgfI/18r1tz8 tmPC3h65sw7+ziewhNSqLZ0hh9VTxfKw52blwNkhVT64OMgyfSq6cr53GA0/iNVw/HazDnYlKKnZ COaTPORRJQDKO1Ngs1mtR5ZSpcd6P6B9K3w6e5V5OSpx8W27mVGKw7MVctmTL1CUa5gtaHsMm0V7 t04qFD5cR8wJO6a4LTkoMeIDnN52MAzwOQLCqoPVkIi4FlyvWe+WNMyVvN4wgALSpeggZY44sppe 2pEa7t8uTWmkx3EWyXuqC3WtL2zaaxWckVczSW9a+oTHVqXW2OGvtGpo8ytmoMWrWnz54qoD9kf/ jfwaBYLuYpVKPvvpRKsrfrWfxojmSN5RINVyM2kv8ev26oTwDQac9DZvc28+gBkazMHweLC8ieSI Cbd4INBZQcSx7Ufcj4WH9wAAAIEzB64P1TvrS1ck0/6zcBiBQB5HXlta8CpiDsFj1Rfbm6jy08no 4qzQYkZBoykapbsEeZuYGbzrg0V4DEFTOdBZ2W3lrFuJAwEOgXkMP6BB76KehvYW2CJ7JpNBGeFG ioKdzTmGk7MAAAAXBoG5AQlsAAcLAQABIwMBAQVdABAAAAxuCgHMJMICAAAA
からフラグをエスパーします。
しかし、デコードしても意味不明なバイナリなのでああ。。。となっていました。
しかし、xxdを噛ませてみると、先頭が
$ cat whatAmI | base64 -D | xxd 00000000: 377a bcaf 271c 0004 a17e 5b71 2502 0000 7z..'....~[q%... 00000010: 0000 0000 2100 0000 0000 0000 d09f 92ba ....!........... 00000020: e001 ec01 b15d 002c 6881 0019 fa07 fc90 .....].,h....... 00000030: 5520 2984 5c54 9bde bcec 533f 7812 87b0 U ).\T....S?x... 00000040: 0025 ded6 0b77 a8a4 285f 1e0b 17c1 a5a9 .%...w..(_...... 00000050: 2436 29d0 b415 09d3 c35e f155 c46d 769d $6)......^.U.mv. 00000060: 9410 dfda 48c7 4119 a7f5 1e23 b46e 6011 ....H.A....#.n`. 00000070: cce1 daec 9fe8 26c7 9116 f77c ae4e 5706 ......&....|.NW.
のようになっていることに気づきます。
$ cat whatAmI | base64 -D > tmp $ file tmp tmp: 7-zip archive data, version 0.4
勝ちです。
書いてみるとシンプルなんですが、非CTF勢からすると、base64デコードしてバイナリになった瞬間の絶望感がすごいのでなかなか先に進みませんでした。
Matryoshka-3
$ xxd ../broken
00000000: 5858 5858 1400 0000 0800 d393 844f 42e3 XXXX.........OB.
00000010: 0746 1f01 0000 5c01 0000 0400 1c00 666c .F....\.......fl
00000020: 6167 5554 0900 03bd 7ce7 5d59 7be7 5d75 agUT....|.]Y{.]u
00000030: 780b 0001 0400 0000 0004 0000 0000 4d90 x.............M.
00000040: bf4a 0431 1087 fb7d 8ab1 b239 b227 1c1e .J.1...}...9.'..
00000050: 770f 2008 16b6 5e23 d9ec ec25 9a4d 4232 w. ...^#...%.MB2
00000060: ebb1 8ac5 de16 5636 8288 3622 8a27 586a ......V6..6".'Xj
00000070: efc3 04d1 c730 8716 361f 0cf3 e7f7 3195 .....0..6.....1.
00000080: e6f3 2910 0fc7 82aa b39d 2d33 d2ba 3dac ..).......-3..=.
00000090: 9136 ceb3 6cb6 bb3f 8085 5442 820a c00d .6..l..?..TB....
000000a0: 702f a43a 41a8 944e b0be e604 2413 42e3 p/.:A..N....$.B.
000000b0: 9cf5 1440 db90 8009 2527 0ec2 d6ce a74a ...@....%'.....J
000000c0: 5933 00c9 0378 7498 1a45 daa7 85fd 3d24 Y3...xt..E....=$
000000d0: 9197 e803 cb0e 6c03 41da 4697 602c 2991 ......l.A.F.`,).
000000e0: 6664 0afe 9f96 9492 111a 68d7 b388 5028 fd........h...P(
000000f0: c37d cbd6 ae20 9262 634e 9583 a24d 69a6 .}... .bcN...Mi.
00000100: 64b0 87b4 1980 7c0b 8a36 328f d514 66ca d.....|..62...f.
00000110: c5fe 3a2e 1fe2 f229 f6af 7179 f5f5 7e1b ..:....)..qy..~.
00000120: bb97 d8df c5fe 2d76 abef d5e3 e7c5 65ec ......-v......e.
00000130: 6e62 f71c bb8f d8dd 6792 c885 699e 130a nb......g...i...
00000140: 5968 3b67 9e0b 61ad 6106 d991 cbff fe12 Yh;g..a.a.......
00000150: f2d1 78b2 3d1e 0e27 4c52 ad7f 0050 4b01 ..x.=..'LR...PK.
00000160: 021e 0314 0000 0008 00d3 9384 4f42 e307 ............OB..
00000170: 461f 0100 005c 0100 0004 0018 0000 0000 F....\..........
00000180: 0001 0000 00a4 8100 0000 0066 6c61 6755 ...........flagU
00000190: 5405 0003 bd7c e75d 7578 0b00 0104 0000 T....|.]ux......
000001a0: 0000 0400 0000 0058 5858 5800 0000 0001 .......XXXX.....
000001b0: 0001 004a 0000 005d 0100 0000 00 ...J...].....
という謎の壊れたバイナリが渡されるのでフラグを取り出す問題です。 えー、前問から、file signatureを見るんだなとエスパーができて、実際XXXXになっているので明らかに怪しいです。
えー、これまで2連続で何かを解凍しているので、何かを解凍するんだろうと予想します。
これまでに解凍したbzip2ファイルや、7zファイルをバイナリとして見てもそんなに似ていないので、拡張子をエスパーします。自分で適当に作ったzipファイルとバイナリの初めを比較すると
1400 0000 0800がかぶっていたので、zipなんじゃないかとエスパーして、とりあえず先頭4byteをzipのそれに書き換えます。
$ xxd broken2
00000000: 504b 0304 1400 0000 0800 d393 844f 42e3 PK...........OB.
00000010: 0746 1f01 0000 5c01 0000 0400 1c00 666c .F....\.......fl
00000020: 6167 5554 0900 03bd 7ce7 5d59 7be7 5d75 agUT....|.]Y{.]u
とりあえずzipだと判定されました(それはそう)
$ file broken2 broken2: Zip archive data, at least v2.0 to extract
zipファイルと言われているんですが、unzipコマンドを叩くと
Archive: broken2
End-of-central-directory signature not found. Either this file is not
a zipfile, or it constitutes one disk of a multi-part archive. In the
latter case the central directory and zipfile comment will be found on
the last disk(s) of this archive.
note: broken2 may be a plain executable, not an archive
unzip: cannot find zipfile directory in one of broken2 or
broken2.zip, and cannot find broken2.ZIP, period.
と怒られます。
なぜか(?) tarコマンドで解凍してやろうという気分になり、
$ tar -xvf broken2
とやるとflagは得られました(は?)
まじで意味わからん。一応バイナリの終盤にもXXXXがあったんですが、結局何だったんでしょう(求有識者)
InvisibleFlag
catするとi󠅶n󠅡v󠅬a󠅩l󠅤i󠅆d󠅬F󠅡l󠅧a󠄺g󠅴:󠅡t󠅳a󠅫s󠅣k󠅴c󠅦t󠅻f󠅄{󠄱T󠅤h󠅟1󠅹5󠄰_󠅵1󠅟5󠅫_󠅮1󠄰n󠅷v󠅟4󠄱l󠅖1󠄵d󠄿_󠅽fl4g}となっているようなファイルが与えられます。明らかに怪しいのでバイナリとしてみると
00000000: 69f3 a085 b66e f3a0 85a1 76f3 a085 ac61 i....n....v....a
00000010: f3a0 85a9 6cf3 a085 a469 f3a0 8586 64f3 ....l....i....d.
00000020: a085 ac46 f3a0 85a1 6cf3 a085 a761 f3a0 ...F....l....a..
00000030: 84ba 67f3 a085 b43a f3a0 85a1 74f3 a085 ..g....:....t...
00000040: b361 f3a0 85ab 73f3 a085 a36b f3a0 85b4 .a....s....k....
00000050: 63f3 a085 a674 f3a0 85bb 66f3 a085 847b c....t....f....{
00000060: f3a0 84b1 54f3 a085 a468 f3a0 859f 31f3 ....T....h....1.
00000070: a085 b935 f3a0 84b0 5ff3 a085 b531 f3a0 ...5...._....1..
00000080: 859f 35f3 a085 ab5f f3a0 85ae 31f3 a084 ..5...._....1...
00000090: b06e f3a0 85b7 76f3 a085 9f34 f3a0 84b1 .n....v....4....
000000a0: 6cf3 a085 9631 f3a0 84b5 64f3 a084 bf5f l....1....d...._
000000b0: f3a0 85bd 666c 3467 7d0a ....fl4g}.
となっています。
なにかの文字コードなんだろうなあと思いつつ、nkfで片っ端から試すのですが、一向にヒットしません。
とりあえずわかりやすいようにasciiを取り除きます。すると
00000000: f3a0 85b6 f3a0 85a1 f3a0 85ac f3a0 85a9 ................ 00000010: f3a0 85a4 f3a0 8586 f3a0 85ac f3a0 85a1 ................ 00000020: f3a0 85a7 f3a0 84ba f3a0 85b4 f3a0 85a1 ................ 00000030: f3a0 85b3 f3a0 85ab f3a0 85a3 f3a0 85b4 ................ 00000040: f3a0 85a6 f3a0 85bb f3a0 8584 f3a0 84b1 ................ 00000050: f3a0 85a4 f3a0 859f f3a0 85b9 f3a0 84b0 ................ 00000060: f3a0 85b5 f3a0 859f f3a0 85ab f3a0 85ae ................ 00000070: f3a0 84b0 f3a0 85b7 f3a0 859f f3a0 84b1 ................ 00000080: f3a0 8596 f3a0 84b5 f3a0 84bf f3a0 85bd ................
となって、明らかに規則性があります。しかし、本当に文字コードに関する知識がなくて、ここから先に進みません。しょうがないので、何の文字コードであれアルファベットの文字は連番だろうとエスパーして、全探索します。
f3a0は必ずついているっぽいので省いて、先頭のそれを省いた4byteの整数になおして考えます。
そうすると文字列は以下のようになります。
34230 34209 34220 34217 34212 34182 34220 34209 34215 33978 34228 34209 34227 34219 34211 34228 34214 34235 34180 33969 34212 34207 34233 33968 34229 34207 34219 34222 33968 34231 34207 33969 34198 33973 33983 34237
各要素から最小値を引いてあげて正規化したのち、それを0~255程度ずらしてcharとして出力してみます。
� n y v q S y n t � � n � x p � s � Q ~ q l � } � l x { } � l ~ c � � �
� m x u p R x m s � � m w o � r � P } p k � | � k w z | � k } b � � �
� l w t o Q w l r � l ~ v n q � O | o j � { � j v y { � j | a � � �
� k v s n P v k q � ~ k } u m ~ p � N { n i � z i u x z � i { ` � �
j u r m O u j p � } j | t l } o � M z m h � y ~ h t w y � h z _ ~ � �
~ i t q l N t i o � | i { s k | n � L y l g � x } g s v x g y ^ } � �
} h s p k M s h n � { h z r j { m � K x k f � w | f r u w ~ f x ] | � �
| g r o j L r g m � z g y q i z l � J w j e v { e q t v } e w \ { � �
{ f q n i K q f l y f x p h y k � I v i d ~ u z d p s u | d v [ z � �
z e p m h J p e k ~ x e w o g x j H u h c } t y c o r t { c u Z y � �
y d o l g I o d j } w d v n f w i ~ G t g b | s x b n q s z b t Y x � �
x c n k f H n c i | v c u m e v h } F s f a { r w a m p r y a s X w �
w b m j e G m b h { u b t l d u g | E r e ` z q v ` l o q x ` r W v � ~
v a l i d F l a g z t a s k c t f { D q d _ y p u _ k n p w _ q V u }
u ` k h c E k ` f y s ` r j b s e z C p c ^ x o t ^ j m o v ^ p U t ~ |
t _ j g b D j _ e x r _ q i a r d y B o b ] w n s ] i l n u ] o T s } {
s ^ i f a C i ^ d w q ^ p h ` q c x A n a \ v m r \ h k m t \ n S r | z
r ] h e ` B h ] c v p ] o g _ p b w @ m ` [ u l q [ g j l s [ m R q { y
q \ g d _ A g \ b u o \ n f ^ o a v ? l _ Z t k p Z f i k r Z l Q p z x
p [ f c ^ @ f [ a t n [ m e ] n ` u > k ^ Y s j o Y e h j q Y k P o y w
o Z e b ] ? e Z ` s m Z l d \ m _ t = j ] X r i n X d g i p X j O n x v
n Y d a \ > d Y _ r l Y k c [ l ^ s < i \ W q h m W c f h o W i N m w u
よく見るとv a l i d F l a g z t a s k c t f { D q d _ y p u _ k n p w _ q V u }が見えます。
おおおおおお、となるんですが、提出しても合いません。
よく考えると、いくつかのcharが負の整数になっていてprintできていないので、整数を表すcharについては別に全探索してあげます。
validFlag:taskctf{D1d_y0u_kn0w_1V5?}
をゲットします…
ちなみにこの時点で、問題の制約に不備があり、flagは[a-z][A-Z][0-9]_しか含まないことになっていたので、?はどうするんや？？？？という気持ちになっていました。clarを投げて解決。
これ、結局何の文字コードだったんでしょう…？
On the existence of optimal solutions to integer and mixed-integer programming problems
- Unbounded
- Infeasible
- has an optimal solution
の3通りしかないけど整数計画問題はそうとは限らなく、
いくらでもいい結果が存在する
というパターンがある。
たとえば、
maximize
subject to ,
is positive integer
など。
この論文では、最適解が存在する十分条件を提示している。それは整数計画問題の場合、変数の非負性や整数性を除いた条件が、等式であることで、混合整数計画の場合、制約の係数が有理数であること、である。
ところで、整数計画の実行可能解の存在判定はNP-Completeである。証明はいくつかあり、一つはSATを整数計画として表せることによる方法で、もう一つは、制約を二分探索すれば整数計画の最適解が求まってしまうことによる方法である。
