研究がまた先行研究とかぶった話

まあ別に初めてではないのであれなんですが

今回はちゃんと1~2週間ぐらい網羅的にサーベイして、完全にかぶっていないことを確認したつもりだったんですが、

先行研究のciteが2とかだった上に、問題の英語名が特殊で、自分の検索ワードと全然マッチしなくて、

しかもその先行研究の先行研究は、分野外(ハードウェア系)の最適化問題で現れた問題で、完全に界隈外の学会だったので

まったく気づきませんでした。

30年ほど昔の研究でした。

GNNの研究をしていると最近の論文しかないため、論文をサーチすれば何ができていて何ができていないかは比較的簡単に分かるのですが

離散最適化など、何十年にも渡って研究されているトピックの場合、あまり世に広まっていない論文だと

全然気づかないこともあるみたいですね。

反省として、こういうときは論文ではなく教科書を先にサーベイすべきです。

東大の図書館、実は本郷にきてから初めて利用したのですが

教科書が無限にあってすごい(それはそう)

ところで、担当してもらっていた先生から励ましの言葉をもらいました

Finding a paper working in your problem is not a bad news at all. It is a process of shaping your topic to the latest one. I am sure that the ideas you have got so far will be applied to solve some research problem soon.

これまでわりと一人で研究をしてきたのでこういう言葉を初めてかけてもらった気がします。

涙がでちゃって、あーやっぱ悔しかったんだなあと客観的に思ってしまいました。

一人ってよくないですね。

ツイッターで言語不明瞭をしちゃうし。

ちなみにこのトピックですが、一応先行研究との差集合は存在するのでそれで続けるという方針はあるのですが

いま客観的にみても、メインの主張がすでに言われているので、まったく同じ分野だとあまりインパクトあることは言えないかなあ

という気持ちになっています。

まあ人生の記録としてブログに

平面グラフアルゴリズム

お待たせいたしました。Competitive Programming Advent Calendar 2019 8日目の記事です。

平面グラフとは

平面グラフとは、平面に辺を交差させずに描画できるグラフのことをいいます。現実世界の例では多くのroad mapがそうであったりします。平面グラフでは、たとえば最短路問題が O(n \sqrt{\log n})で解けたり(Frederikson)、多くの最適化問題で、通常のグラフよりも効率的なアルゴリズムが発見されています。

この記事では平面グラフの性質や、アルゴリズムなどを紹介していこうと思います。もともとは実装しようと思っていたんですが、ちょっと人生が忙しいので保留です(一生保留しそう)(ごめんなさい)。

基本編

Eulerの公式

連結な平面グラフ Gについて、頂点数を v, 辺数を e, 面数を fとすると v - e + f = 2が成り立つ。非本質ですが、頂点は0次元、辺は1次元、面は2次元なので、符号と (-1)^\mathrm{dim}が共通していますね。暗記向けです。

単純な平面グラフ( n \ge 3)について、 m \le 3n - 6

これにより、辺の数がO(n)であることがわかります。そうすると面の数も O(n)です。平面グラフアルゴリズムの計算量に nしか現れないのはこのためです。ちなみに、アルゴリズムの計算量などで O(n)といっても定数倍が大きいものが多い印象です。

Kuratowskiの定理

グラフ Gが平面グラフである必要十分条件が、「 G K_5, K_{3,3}をマイナーに含まない」ことをいう定理です。 K_n n頂点の完全グラフ、 K_{n,m} n, m頂点の完全二部グラフを指します。グラフ Hがグラフ Gのマイナーであるとは、 H Gから、(1)辺の除去, (2)辺の縮約, (3)孤立点の除去を繰り返して得られることをいいます。

f:id:xuzijian629:20191214112709p:plain

それぞれ K_5 K_{3,3} https://www.researchgate.net/figure/Excluded-minors-for-planar-graphs_fig1_238872253

グラフの集合 Sがある性質 Fに対してminor-closedであるとは、 Sの要素を縮約したグラフも性質 Fを満たすことをいいます。明らかに、「平面に描画できているグラフを縮約したグラフは平面に描画できる」ので、平面グラフはminor-closedなグラフの集合となります。興味深い点は、 K_5, K_{3,3}はいずれも平面に描画できないのですが、平面に描画できる必要十分条件がこの2グラフの(マイナーとしての)有無で決定されるということです。証明は省略しますが、興味のある方はぜひ調べてみてください。

中級編

グラフの平面性判定

与えられたグラフが平面グラフかどうかは O(n)で判定ができます。これめっちゃすごいですね。アルゴリズムは、いろいろなものが開発されてきましたが、Boyerのアルゴリズムが有名な気がします。

アルゴリズムの説明(アルゴリズムは全然中級じゃないです)

お絵かきをしました。適当に書いたグラフなのでとくにコーナーケースじゃないです(すみません) f:id:xuzijian629:20191215131845j:plain

本質は線形にするための実装と正当性の証明なんですが、手でやる分には比較的簡単にできます。

  • グラフをdfsし、訪れた順にidを振っていく。dfs木と後退辺を覚えておく
  • 各辺の優先度を \min{u, v}とする。つまり両端のidのmin
  • 辺を優先度の大きい順に追加していく。同じ優先度はなんでもいいけどdfs木の辺優先
  • そのときに2連結になるように、頂点を適宜増やしていく
  • 新たなループが生成されるとき、externally activeな頂点を外平面に向けるようにflipする(将来的に処理される辺はすべて外平面に来ているはず)
  • 最後まで追加できれば描画完了。無理なら平面グラフでない

ある頂点がexternally activeというのは、その頂点またはその子孫から後退辺をたどって、今見ている優先度よりもidの小さい頂点に行けるということで、要は今後辺を追加されるときに面に埋め込まれちゃうかもしれない、気をつけなければいけない頂点です。

描画完了できない場合は平面グラフではないんですが、詰むケースは数パターンに場合分けされ、それぞれの場合についてどの部分グラフが禁止マイナーになっているかを調べることができます。

かなり雑に説明しちゃったんですが、 http://www.th.cs.meiji.ac.jp/assets/researches/2007/toyota/index.html に日本語記事があるので気になる方は照らし合わせながら追ってみてください。

Separator定理

えー、一番の本質です。平面グラフで一番うれしい性質です。グラフ Gの頂点集合の分割 A, B, Cで、(1)どの辺も A, Bを直接結ばなく、(2)A, Bの頂点重みは全体の2/3以下にできるとき、頂点集合 C Gのセパレータと呼びます。グラフに o(n)のセパレータが存在するかはかなり重要な関心であり、なぜかというと、 o(n)のセパレータが存在するなら、分割統治アルゴリズムが使えるからです。うれしいことに、平面グラフは O(\sqrt{n})のセパレータをもつことが知られており、 O(n)でセパレータを構築できますLipton & Tarjan。実際多くの平面グラフアルゴリズムはこのセパレータの性質によって高速性が導かれています。

木幅が O(\sqrt n)

この記事ではあまり深く書くことがないです。

たぶん上級編

直線による描画

平面グラフの定義において、平面に描画するときに直線を使う必要はありませんが(曲線でよい)、実は任意の平面グラフは直線のみを用いて平面に描画が可能です。もっと言うと、 O(n) \times O(n)のサイズのグリッド上の格子点に頂点を配置して、かつ、直線のみを使って描画することも可能です。

最大カット

最大カット問題は、一般グラフにおいてNP-Hardであることが知られていますが、平面グラフには O(n^{1.5}\log n)アルゴリズムが存在します

アルゴリズムの説明

これもまたさまざまなアルゴリズムが提案されてきたのですが、シンプルで有名なのがA simple MAX-CUT algorithm for planar graphsだと思います。

f:id:xuzijian629:20191214163537p:plain 平面グラフと双対グラフです。

f:id:xuzijian629:20191214163410p:plain 頂点を K_4に倍加して、最大マッチングを考えます。

  1. 連結な単純グラフ Gが入力として与えられたとき、まず Gの双対グラフ G_Dをとる。双対グラフの辺のコストは、その辺が横切る元のグラフの辺のコストと同じにする。 G_Dの次数5以上の頂点を分割し、分割した頂点同士をコスト0の辺でつなぐ。さらに、 G_Dの各頂点を K_4に置き換えたグラフを考える。 K_4内部の辺の重みは0.

  2. 以上のグラフでmaximum weighted matchingを考える。必ずperfect matchingが存在することが示せ、このとき、各 K_4に着目すると必ず K_4から外に出る辺は偶数本になっていることがわかり、perfect matchingはEulerianになることがわかる。

  3. 双対グラフでのEulerian subgraphと元のグラフのカットには1対1対応があり、この最大重みeulerian subgraphが元のグラフでの最大cutになっている。

計算量についてまとめます。平面グラフの双対グラフも平面グラフであり、頂点数、辺の本数も O(n)で、頂点を4倍加してもオーダーは変わりません。あとは平面グラフのmaximum weighted matchingを考えればいいのですが、これはTarjanによると O(n^{1.5} \log n)なので、そのままmax-cutもこのオーダーで解けることになります(クソ雑)。

最小交差数

A separator theorem for minor-closed classesによると、固定された kについて最小交差数が k以下か判定する線形アルゴリズムがあるそうです。

同型判定

平面グラフの同型判定は線形で可能です 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なグラフは o(n)のセパレータをもつのでは?という話がされていて、実際に K_tをマイナーとして含まないグラフについて O(t\sqrt{n})のセパレータを持つことを証明しています。これは応用範囲が広く、たとえばbounded degreeのグラフが O(d\sqrt n)のセパレータをもつことなどがすぐに導かれます。

ちなみに、bounded average degreeグラフはこの性質を満たしません(証明はErdos)。

 o(n)のセパレータをもつなら、分割統治が回るので、平面グラフ以外にも多くのminor-closedなグラフについて平面グラフの場合と類似する高速なアルゴリズムがあると思います(あまり詳しくありません)

最後に

平面グラフやべーーーーー やべーーーと話題に

非CTF勢によるCTFの解き方

writeupです。

深夜にツイッターを見ていたら面白そうなものが生えていたので暇をつぶそうという気持ちになりました。ちなみに当方、ほぼ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

からフラグをエスパーします。

なんかbase64エンコードっぽく見えます(文字的に)。

しかし、デコードしても意味不明なバイナリなのでああ。。。となっていました。

しかし、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を投げて解決。

これ、結局何の文字コードだったんでしょう…?

DPC広島に参加しました

優勝しました!

これでやっと競プロのコンテスト優勝者を名乗れる…

f:id:xuzijian629:20191117194317j:plain

申し込み

f:id:xuzijian629:20191117194457p:plain

ICPCとかぶっているということで、賞金チャンスがかなり高まったのでモチベがあがります。

Girigiriは仲がいいのでこういう情報はちゃんと隠されずにシェアされてうれしいですね〜〜〜〜〜〜〜

広島へ

会場がかなり山奥にあって電車によるアクセスが困難なので、チームメイトに運転してもらいます(ぼくは免許もってない)

写真を撮り忘れたのですが、会場前の建物に"Ogino"と刻まれていておもしろかった

DPC参加する人を事前チェックしていたのですが、ほぼ知り合いがいなそうだと思った割にはいました。kaitoくんに会ってみたかったのであえてよかったです。

コンテスト

形式

問題例は公式サイトをご覧ください。

コンテストの形式はちょっと特殊で、手元実行した結果をフォームに入力して提出します。テストケースは3つぐらいしかないです。ケースも比較的小さいので手元で計算できちゃうレベルなんですが、一応ルールで埋め込みは禁止されています。実行時間に制限はないので、ルール上は手元で長時間回すことが可能です。

問題の性質上、最後の問題は計算が困難な離散最適化問題がでがちです。残り4題は普通の競プロといったところでしょうか。

入力の受け取りがかなり特殊なんですが、ソースコードへの入力データコピーが可能なので、そのままファイルに貼り付けるのが楽です。

コンテスト中

1, 2, 3, 4問目を大きなミスなく解きました。多分デバッグに使った時間は2分以下な気がします。3, 4問目で多少冗長なコードを書いた自覚がありますが(ちょっと詰めれば短く書けたと思う)、まあ早解きとのトレードオフがあるので、総合するとかなりよくできたかなと思います。

5問目に一時間半を残したわけですが、結局正解することができませんでした。終了後に、実は条件を誤読していた(各トラックが1台まで、ということを知らなくて、何台もトラックを発進していた)ことが判明し、コンテスト時間がもう少し長くてけんしんが5問目を通していたらかなり危なかったようです。

コンテスト中は最適解よりもいい答えを出してしまったのでかなりびっくりしていました(悪あがきでbin packing問題のヒューリスティクス解+乱択で解を出しました)。

結果

4完内ならさすがに一番早いだろうとは思っていたのですが、チームメイト残り2人から最後の問題の正しい設定と解法(荻野とけんしんは別の解法だけどどっちも合ってそう)を聞いて、あ〜〜〜〜〜これなら解けてる人がいてもおかしくなさそう、だと思ってドキドキしていました。受付の人から東京から5人来ている、という情報を聞いていたので自分たち以外に2人謎の人物がいて、隠れレッドコーダーとかやめてくれよおおお〜〜〜〜〜ってなっていました。

結果、初優勝!!!!!!

盾をもらったり取材を受けたりしました。盾は後日配送みたいです。 盾に書いてもらう名前のふりがなを登録時に「じょえにきあ」にしたのですが、ふりがなは振られませんでしたし表彰時は本名で呼ばれました。

けんしんはあと数分あれば1位になっていたようなのですごく危なかったです(けんしんが1位のほうがチームとしての獲得賞金額は多かったのですが)

観光

コンテスト後、フェリーで江田島という島に向かいます。夜遅かったので急いで宿にチェックインすると、かなり豪華な夕食が待っていてテンションが上がりました。

刺し身がめちゃめちゃうまい

次の日、島を観光しました。海上自衛隊術科学校があるみたいで、中を見学させてもらいました。最初90分で、なげーと思っていたのですが、博物館のような建物があって一瞬で時間が過ぎ去ってしまいました。あと、けんしんが一般道と間違えて自転車で術科学校の敷地に突入したところ、警備員に止められていてかなりおもしろかったです。

自転車を借りて島を回りました。さすがに最高

f:id:xuzijian629:20191117201231j:plain フェリーから見る日没。ところでフェリーは船内できっぷを買うことが多いみたいで、駆け込み乗船が可能なのでオタクにやさしかった。

f:id:xuzijian629:20191117201309j:plain 広島焼きをやべて帰国。

最後に

ICPC横浜とかぶっているのが本当にでかすぎた。少なくともここ数年以内は他のコンテストで優勝できる気がしないし、なんなら賞金をもらうのさえ難しい気がするので、今回のこのあまりに運のよかった大会でちゃんと優勝できて本当によかった。

タイ旅行の知見

  • LINE Pay(厳密にはRabbit LINE Pay)が使える。準備していったら普通に便利そう。 【キャッシュレス決済】タイで現地のLINE Payを使ってみた。BTSラビットカードと紐付けてチャージ不要で電車に乗ったり、お店でスマホを使った買物ができたりする

  • Grab(東南アジア版Uber)がめちゃくちゃ便利。クレカ払いで乗る前に値段がわかるので安心。公式サイトにはよっぽどのことがない限りマッチングをキャンセルされないと書いてあるが、(とくに新規ユーザの場合)それなりにキャンセルされる。1回の配車で2,3回リトライすることは珍しくなさそう。

  • アユタヤでトゥクトゥクに乗ったが、かなりちゃんとしていた。思いつきで値段を言うのではなく事前に印刷された紙にいろいろ書かれている。運転手もそれなりに英語コミュニケーションが可能で、ぼくらが観光している間も待ってくれていた(支払いは後払い)

  • バンコク市内のタクシーはぼったくられたという情報をちらほら聞く(すべてGrabを使ったため自分たちは大丈夫だった)。ちなみにぼったくられない場合Grabよりタクシーが安い(メーターを見たけどGrab 170バーツでメーター120ぐらいだった回があった)。

  • 客引きはだらだらしているとつきまとってくるので、真顔でノーサンキューと言うのが一番手っ取り早い気がする。案外英語を理解している。

  • まともな店にいくとかなり日本語が通じる

  • 屋台かなりおいしい。骨付きの鶏肉とフランクフルトを食べた。鶏肉はKFCより断然うまい。ちなみにタイのKFCは日本のよりめっちゃうまいらしい(行きそびれた)

ICPC Bangkok Regional参加記(コンテスト以外編)

コンテスト編はこちら

xuzijian629.hatenablog.com

レジ編

9月下旬ぐらいにレジります。The ICPC International Collegiate Programming Contestから参加したい大会を選び、あとは国内予選と同じです。思ったよりハードルが低かったです。普通はコーチが必要なんですが大会によってはContestantがコーチを兼任できる場合があり、さらにコーチは現地までこなくてもいいようなので、適当に大学の人にお願いするのがよさそうです。

研究室の先輩を騙してにお願いして現地まで来てもらいました。

エアビーで175平米もあるプール・ジム付きの豪邸を借り、テンションが最高になる。

初日

空港にスタッフに迎えにきてもらう予定だったが飛行機が予定より1時間程度早くついてしまったのでかなり暇になる。夕食のレストランを調べたりGrabという配車アプリの登録などをしているとスタッフが来る。

f:id:xuzijian629:20191106190739j:plain

Aobayama_dropoutと合流して日本勢2チームでバスに乗る。こたつがめの語録を聞きたかったがかなりまともだった。

なんか売っていたので買う。服が安い。ナイトマーケット(昼間もやってるけど)ではいろんなブランドの偽物がたくさん売られていた。

夕食

ソンブーンというげきうまタイ料理のお店にいく。宿泊施設から徒歩10分弱だった。 f:id:xuzijian629:20191106190936j:plainf:id:xuzijian629:20191106190953j:plain

写真は空芯菜の炒め物とプーパッポンカリーと呼ばれるカニが入ったカレー。いろんな料理をかなりお腹いっぱいまで食べて一人あたり600バーツ(1バーツ3.7円)程度だった。日本と比べてかなりコスパがよい。

ちなみにコーチセレクション。さっそくコーチの仕事をしていて感動する。

2日目

f:id:xuzijian629:20191106192223j:plain朝食の豚丼タイ米が苦手な人をたまに見るけどこういう料理はむしろタイ米が合うしめちゃめちゃうまい。値段は100バーツだった気がする。安い。

f:id:xuzijian629:20191106192351j:plain ちなみにこの日はPractice Session. 歩いてチュラロンコーン大学へ向かう。タイの下町は電線がすごい。

f:id:xuzijian629:20191106192451j:plain タイではすごくLINEが普及していて現地のスタッフも使っていた。LINE Payが日本よりも普及していて、BTS(電車)のチケット購入やお店での支払いもできる。ただ、厳密にはRabbit LINE Payというやつで日本のものとは別のアカウントが必要になるっぽく、日本のLINE PayでBTSのチケットを買ったところ支払いは完了したのにチケットが出てこなくてかなり焦った。ICPCスタッフの人が駅員に事情を説明してチケットを入手した。

f:id:xuzijian629:20191106192737j:plain バーガーキングのキング感がすごい。

ちなみに街中でかなり日本の店やひらがな、漢字を見る。客引きの日本語もかなり聞こえてくる。

チュラロンコーン大学

ICPCのPractice Sessionをする。1チームに現地のスタッフ1人がついてくれる。スタッフの人当たりがすごくよくて、歓迎されているなあと感じた。日本チームにはついてくれたスタッフはみな日本語が流暢で、日本語でほぼすべての会話が行われた。

f:id:xuzijian629:20191106193228j:plain 写真はチュラロンコーン大学の文学部。伝統のあるタイの建物らしい。ちなみにタイにはめちゃめちゃセブンイレブンが進出しているのだが、理由がわかった気がする。色合いが景観に合う(これマジ?笑)

f:id:xuzijian629:20191106192933j:plain 午後はeiyatonariと現地のスタッフたちでSIAM付近を散策した。実質某ジャーナル。写真の場所、完全に新宿駅〜代々木駅の間の空間だった。

夕食はeiyatonariと合コン。りっきーしーたぷにきあくんが合コン後の僅かな時間でHTTFをサクっとやり入賞していた。やべえ〜〜〜〜〜〜〜。

ゲストハウスに戻り、コーチのセミナーを受講する。

3日目

7時に起床し朝食を食べて大学に向かい、コンテストをやる。コンテスト自体はあんまりうまくいかなかった。

その後、ゲストハウスに戻り泳いだりしてリラックスする。

コーチセレクションで、トムヤムクンを食べに行く。 クイッティアオ トムヤムの最高峰!「ラーン ピーオー」 | 激旨!タイ食堂 コーチの下調べが天才すぎる。

f:id:xuzijian629:20191106193549j:plain

これ一杯で60~120バーツ程度。あまりに安すぎるので2杯目を頼んだ。

食べている間にスコールが降り出して店の前が一瞬にして水たまりになる。

帰宅してAGCをする。けんしんが赤パフォをだしていてやばかった。

4日目

三大寺院ことワットー・ポーに行く。コーチがもろもろのスケジュールを管理してくれていてかなり助かる。 市内からわりと近くてGrabでひょいと行けた。 けっこう広くて見ごたえがあった。

f:id:xuzijian629:20191106194450j:plain

f:id:xuzijian629:20191106194529j:plain 寝転がっている像がめちゃめちゃでかかった。

ホテル

最終宿泊日なのでいいところに泊まろうという話になって、Millennium Hilton Bangkokでエグゼクティブルームを2部屋とった。なんか31階のラウンジチェックインとかいう異常待遇を受けた。これはラウンジトイレからの眺め。

f:id:xuzijian629:20191106194913j:plain

f:id:xuzijian629:20191106194932j:plain 部屋は全室リバーサイドビューで、チャオプラヤ川が見えた。かなり船が行き来していてにぎやかな感じがした。

f:id:xuzijian629:20191106195046j:plain ちなみにホテルにプライベート桟橋があり、川を船で横断することができる。バンコクは一方通行な道が多くてホテルから川を横断するだけでも車で20分弱かかるので船が一番早い。

マッサージ

川を渡ったところにある街のマッサージ店にいった(コーチがめっちゃ検索してレビューのいいところを探してくれた)。90分450バーツだった。ちなみにチップを50バーツ払うのが慣例のようなので実質500バーツ。90分長くないかと思ったけど施術後は全員一致でまだ足りない、だった。めちゃめちゃ快適。

夕食

ホテル内にご飯を食べれる場所が4箇所あるのだが、ビュッフェにした。自分はビュッフェにいくと貪欲法で食事をとってしまい華がないので華がある画像を貼ります。

夕食後はちょっと休んで、ホテル内のジムに行った。次の日もマッサージに行こうということになって、体を疲れさせたほうがマッサージの効きを体感できると思ったのでめっちゃ筋トレをした。

ルーフトップバー

バンコクのルーフトップバーは有名らしく、ルーフトップバーに行ってみたさがあったのでこのホテルを取った。

17:00-19:00の間(ホテルによる)はハッピーアワーといって、メニューが安くなるが、思いっきりマッサージを受けていたので通常の値段で楽しむ。 1杯400バーツ程度だった。

ちなみにこのちょっと前にコーチが外の散歩にいくと行って出ていったがスマホの電池が切れ帰れなくなっていてコーチ以外の3人で飲んだ。コーチかわいそう…

f:id:xuzijian629:20191106200019j:plain

5日目

f:id:xuzijian629:20191106200143j:plain ホテルのレストランで朝食をとる。屋外(チャオプラヤ川沿い)にも座れるが暑そうだったので中で食べる。

アユタヤ遺跡

バンコクから電車で2時間ぐらい行くとアユタヤに行ける。

f:id:xuzijian629:20191106200319j:plain これはタイの電車。ちなみにBTSは10分程度乗るだけでも一人あたり30バーツ程度かかるが、国鉄(?)のほうは2時間の長距離でも20バーツぐらいで非常に安かった。バンコク市内はかなりゆっくりで荻野が走ったほうが速いレベルだった。

f:id:xuzijian629:20191106200502j:plain f:id:xuzijian629:20191106200524j:plain

有名観光地らしく、日本人もかなり多かった。コーチのオタク言葉が移ったせいで語録を話ながら歩いていたらめっちゃいろんな客に見られてかなり厳しかった。 f:id:xuzijian629:20191106200638j:plain ビルマ軍の破壊の痕跡などがあった。

f:id:xuzijian629:20191106200702j:plain

f:id:xuzijian629:20191106200727j:plain 適当に街の屋台で買い食いして、電車に乗ってバンコク市内へ戻る。帰りは人が多かった。ドアは普通に手で開けられてしまうし、普通に開いているのでドア付近に立つとかなり怖い。車内に人が多くて暑かったのでドア付近で涼むなどした。

マッサージ

f:id:xuzijian629:20191106201007j:plain かなりいい店舗をまた検索していったが行き先が思いっきりナイトマーケットでかなりびびった。お店は落ち着いていた。また90分のマッサージを受け、ギリギリのタイミングで空港へ行く。

帰国

空港はすごく空いていて一瞬で出国審査をクリアしたのでレストランで豪遊する。

あ〜タイ旅行最高!(ICPCとは?)

ICPC Bangkok Regional参加記(コンテスト編)

コンテスト編以外は後日書きます。

コンテスト

  • ぼくが環境を構築する。ctrl:nocapsにする。設定から画面スプリットのショートカットを変更、マウススクロールの方向を変更、.vimrcの作成、.bashrcにg++のエイリアスを追記、geditのタブ幅等の変更、テンプレートの入力、テスト用プログラムの作成をする
  • けんしん、荻野が問題を読んでいく
  • 準備が終わってもまだ解ける問題はなさそう
  • 荻野がDの解法を教えてくれるのでDを書く。WA
  • 誤差かと思って精度を改善するもWAが続く
  • けんしんからFはやるだけだと聞くのでFを書く。WA
  • 並列でデバッグしつつ、ぼくがI, J, Kあたりを読んでいく
  • 1時間弱経つのに1問も正解できないのでさすがにジャッジおかしくないかと思ってジャッジが間違っていないかclarする。正常だと言われる(ちなみにスコアボードは1:12まで機能していなくて何も見れなかった)
  • スコアボードが突如現れて、しかもなぜかrandomizedされていなく(予告ではrandomized)、Mがかなり解かれているので荻野が読む。
  • なんかFがリジャッジされてACになった。けんしんが発狂。ジャッジ間違ってたやんけ
  • KがLCAやるだけだったのでけんしんに場合分けを任せつつ、ぼくがライブラリを写経する
  • Kが通る
  • 荻野がMの解法を伝えてくれる。75次方程式の係数の漸化式を伝えてくれたので実装する。ちょっとバグったけど案外すぐ通る。
  • Dのデバッグを詰めなきゃいけなくなってきたのでDを荻野が詰める。Iをけんしんが考察してくれていて、遅延セグ木で頑張ればできることがわかる。
  • Hを読んでみるとかなり数学的には簡単だったのでやることを整理する
  • D、素数列挙が足りなかっただけだったので書いて出す。やっとAC。この時点で4完
  • Hをそのまま実装するもWA。というかd.dddE+dddのフォーマットで出力するのがだるすぎた。printfの仕様を完全理解していなかったのでlog10とかexp10とか使って自分で切り出した。しかし冷静に愚直にやると精度がやばいことに気づく。とりあえず保留
  • ぼくがHを解いている間に荻野がBできたかもしれないと言い出す。
  • 荻野にJのペル方程式についての知見を質問されたがあいにく荻野のサブセットしか知識がなかったので困った
  • Aで調和級数みたいなO(MlogM)を書いたらTL2秒で手元2.1秒で落ちたのでかなり困る。けんしんがいろいろ改善してくれて最初にO(N^2)前計算をすることによって諸々が軽くなって通る。
  • この辺でラスト1時間になり、B, H, Iがキューに溜まっている状態で、2問通せればいいねみたいな話をした。
  • 荻野にグレイコードの構築ができるかと聞かれてかなり困ったが(かなり昔にwikipediaを読んだことがある)、なんか天啓が降ってきてi ^ (i >> 1)思い出した。
  • H, Iが進まないので荻野にBを譲ったらいつの間にか通っていた。やばい。
  • 残り15分ぐらいになった。Hは浮動小数点演算の精度をうんぬんするのではなく、もっと数学的にうまく処理できることに気づいたけどさすがに間に合わない
  • Iもさすがに間に合わないけどぼーっとするのもあれなのでけんしんがIを実装する
  • コンテスト終了。あ〜となる

感想

  • 最初の1,2時間がほぼ虚無だったのでかなり痛手を負った
  • キューに2問溜まったまま終了したのはもしかして初めてだったかもしれない。プログラミングコンテストは実装コンテストであることを痛感した。
  • printfで異常scientific表記を要求されるのはバンコクの過去問にもあったのでちゃんと予習しておくべきだった(過去問のやつだと困らなかったんですが)。ちなみにC/C++のリファレンスは用意されているがごく一部だけでiomanipなどはなかった。
  • 問題はたしかに教育的な問題も多くて楽しかった
  • ワクワクコンテストということで諸々で批判されているがなんか強いチームはやっぱり強いしあんまり関係なさそう、という気持ちになった。

ワクワク要素まとめ(公式)