SecurityFest CTF 2017 [Web 200] Freddy vs json
SecurityFest CTF 2017 に チームHarekaze で参加しました。 チームの総得点は1660点で自分はそのうちの250点解きました。
Freddy vs json
ページを開くとよくあるログインフォームにメールアドレスとパスワードの入力欄があります。
適当に埋めて送信すると
Invalid username or password!
と怒られます。
Exploit
http://52.208.132.198:2999/index.js
を見るとページのソースコードを見ることが出来ます。
ちなみにこれはエスパーして発見しました。(一応ヒント(?)として/static/index.jsがheadでインポートされていることはわかるが……)
ソースコードを見ると
if(req.body.user && req.body.pass){ user = req.body.user; pass = crypto.createHash('md5').update(req.body.pass).digest("hex"); //Query internal login service request("http://127.0.0.1:3001/createTicket/"+user+"/"+pass, function(error, response, body){ console.log(body);
という部分があり、これによりログイン判定をしていることがわかります。
またソースコードのはじめに
require('./local');
local.jsを読み込んでいる記述があるのでそれも見てみます。
以下の記述より、ポート3001で待ち受けているローカルサーバーの処理が書かれていることがわかります。
localapp.listen(3001, '127.0.0.1', function () { console.log('JWT service up!') });
さらに
db = [ {"user":"admin","pass":"9c72256fdb7196d2563a38b84f431491","id":"1"} ]; … … function verify(user, pass){ db_user = db[0]; //TODO: sync with LDAP instead if(user && user == db_user["user"]){ if(pass && pass == db_user["pass"]){ return db_user["id"]; } } return 0; } localapp.get('/createTicket/:user/:pass', function (req, res) { user = req.params.user; pass = req.params.pass; userid = verify(user, pass); if(userid){ res.send('{"authenticated":true, "user":"'+user+'", "id":'+userid+'}'); }else{ res.send('{"authenticated":false, "user":"'+user+'", "id":'+userid+'}'); } })
とあることから、curl -v -d 'user=admin%2f9c72256fdb7196d2563a38b84f431491%3fa%3d&pass=a' 52.208.132.198:299
と送ることでサーバー上ではhttp://127.0.0.1:3001/createTicket/admin/2f9c72256fdb7196d2563a38b84f431491?a=a/というリクエストが送信され
ログインに成功しflagが手に入ります。
(ログイン時に判定されるpassはmd5ハッシュ化されたものであることに気づけばいい。)
{"authenticated":true,"user":"admin","id":1,"response":"Congratulations: SCTF{1nj3ction_5chm1nj3ctioN}"}
flag SCTF{1nj3ction_5chm1nj3ctioN}
いつだってヒーロー
こんにちは、megumishと申します。現在精神的に病んでいて大学休学中の身の一浪二留の学部生です。
もしかしたら自分と同じような悩みを持ったACHD―成人先天性心疾患―患者がいるのではないかと思いこのブログを立ち上げました。
このブログを書くことで少しでもACHD患者精神面でのケアができたら幸いです。
とはいっても素人の所感ですので気休め程度に読んでいただければいいなと思います。
※精神面の話ですがいわゆるADHD―注意欠陥・多動性障害―とは一文字違いであるものの、関係はありません。
まえがき
ACHDについて
ACHDは Adult Congenital Heart Disease
の略で
日本語に訳すと成人先天性心疾患となります。
成人なのに先天性という言葉はおかしな名称だと思うかもしれませんが
ACHDは先天性心疾患を抱えたまま大人になった人たちの病状のことを指します。
そもそも先天性心疾患についてご存知でない人もいるかもしれません。
簡単に説明しておくと、生まれたときから心臓の奇形によって異常を来たしている病状のことを総称して先天性心疾患と呼びます。
(専門家ではないので間違っていたことを言っていたらすみません)
くわしくは下記のサイトが参考になるかと思います。。
https://www.kango-roo.com/sn/k/view/2312www.kango-roo.com
僕の抱えている病気
僕が生まれつき持っていた病気は先天性心疾患のうち三尖弁閉鎖症というものです。
先ほど紹介したリンクの中では三尖弁閉鎖不全症という名称で説明されているものです。
また高校生の頃に(医者曰く)より長く生きるための手術をしたのちに徐脈と呼ばれる
(そのまま生きていくのが困難な程度に)心臓の脈の動きが小さくなってしまう病状も抱えているため、現在ペースメーカーを埋め込み中です。
なぜ僕が精神を病んでしまったか
社会になじむACHD患者
ACHDは一目では普通の人と違いが分からない内部障害です。
そのため、ある意味では普通の人と何ら変わりなく社会と交わっていくことも可能です。
実際、僕は高校生から大学生ぐらいの時期(現在は大学生、精神的な理由により休学中)は心臓の病気を抱えていると
周りに言わなければそれが分からない程度にはなじんでいたと思います。
つまり、僕自身は病気とは分からない程度に活動可能で、周りと比べれば確かに体力や運動能力がない程度の人間だと思ってもらえればいいと思います。
自立と先立つ不安
周りと同じように振る舞えば、一見病気とは関係なく生きていける。しかし、それでも病気は抱えたままですから不安はあるものです。
「病状が悪化したらどうしようか?」「突然、動くのも困難な状況になったらどうなるのだろうか?」
今まで、そして現在も自分は周りに世話をしてくれる家族がいます。
だけど、未来を見るとそうではないです。このように恵まれた環境がいつまでも続くとは到底思えないのです。
現在でも親が年を取って少しずつ身体面でも経済面でも弱っていっていることを感じています。
自分が特に不安なのはペースメーカーを埋めているため、人生のうちに何回か手術が必要なのが確定していることです。
これまでは家族の献身的なサポートにより、入院生活中もとくに困難を感じることなく生活していくことが可能でした。
しかし、これから先を考えていくと決してそうではないです。親自身がサポートを必要とするような状態にもなるでしょうし、自分のことにまで手を回す余裕もなくなっていくのでしょう。
そうした不安は割と小さい頃(といっても中学生ぐらいからだろうか)からありました。
母親から何度もいつかは自分の力で生きていけるようにならないといけないということを聞きましたし
実際自分もそうならなければいけないのだろうと思っていました。現在でもその気持ちは変わりません。
おおよそ、上で述べたようなことはACHD患者の方以外でも考えうることだと思います。
すごい(特別な)人間になりたかったこと
昔から、思っていました。
「どうして僕だけがこんな目に合わないといけないんだろう?」
「周りと比べれば劣っているのにどうしてこんなにも構ってもらえるのだろう?」
これら二つが合体して、もしかしたら自分は特別な人間なんじゃないかと言うおごりが生まれていきました。
でもその時点では特に優れたところもなかった子供でしたから、未来にかけていました。大人になったらきっとすごい人間になれるのだろう…と。
しかし年をとるに連れてそういったものは全く根拠のない幻想だと分かっていきました。
「自分はとくに理由もなく心臓の病気を抱えて生まれてきて
家族と学校側の対応に恵まれて、たまたまチヤホヤされていただけなのだ」と。
そうして、大人になったらきっとすごい人間になれる。いやならなければならないという執着だけが残りました。
前に述べたようなおごりの中生きてきたわけですから、これまでとくに頑張った経験もありませんでしたし
努力するのがとても苦手でした。そうして自分はすごい人ととは到底思えないような生き様のままついに成人してしまいました。
自立するということとすごい人間になるということ
自立するということとすごい人間になるということは別のことです。直交することであり、それらに因果などはないはずです。
しかし自分の頭の中では
「自立するためにはすごい人間にならなければならない。」
という確かな思いがありました。
しかし、先ほども書いた通り自分の思い描いたようなすごい人間になることはできませんでした。
現状と理想との差、それと同時に導き出される自立できないんじゃないかという不安、これらが僕が精神的に参ってしまったことの理由です。
いつだってヒーロー
僕と同じような人生を送ってきたACHD患者の方なら分かると思いますが、死ぬ―人生を悲劇の一幕で終わらせる―チャンスはたくさんあったと思います。
悩んでる人がここを見て実践しては元も子もないので詳しくは書きませんが。
でもこのブログを見ているということは辛いことがあろうとそういうことを実行に移さずに生きてきた人たちなのだろうと思います。
この記事で最後に伝えたかったことはこれからもそうやって生きようよということです。
僕の大好きなバンドにamazarashiというロックバンドがあるのですが、そのバンドの「ヒーロー」という歌の中にこんな一言が出てきます。
「誰だってヒーロー」
そのあとにこう続きます。
「そんなわけはねぇよ」
衝撃的ですね。僕も(世界を救う)すごい人間にあこがれていたわけですから、それがあっさりと歌詞の中で否定されるわけです。
でもよくよく考えてください。今まであなたは誰か一人だけは必ず救っているはずです。現在進行形で。
それが誰かはあなた自身が分かっているはずです。なぜならあなたは今、生きているのだから。
最後に「ヒーロー」の歌詞の一番最後をここに載せておきます。
「いつだってヒーロー」
33C3CTF WriteUp pay2win [200] web
cheapとflagが買えるようです。
まずはcheapから買ってみることにしましょう。
クレジットカードナンバーはcredit card number sample などで検索して出てきたものを入力してもいいですが、
実はLuhnアルゴリズムが通る数字ならなんでもいいっぽいので0でも入力しておきます。
0を入力すると無事にcheapを購入することができ、cheap.txtの中身を見ることができます。
次にflagを購入してみましょう。
flagもcheapを買ったときと同じように、0を入力し購入できるか試します。
おっと、クレジットカードの使用限度を超えていて買えないようです。
おおよそflagを手に入れる方法は次の二つです。
正しいクレジットカードナンバーを入力するか、cheapの購入後画面でをcheap.txtをflag.txtを何らかの方法で書きかえることで手に入れるかです。
答えを先に行ってしまうと正しかった方は、cheap.txtをflag.txtに書きかえる方です。
以下flagを発見した手順です。
まず、cheapを購入する場面でのURLのdataの値と、flagを購入する場面でのURLのdataの値を比較します。
cheap:5e4ec20070a567e03c598eac510b4a85475daa246cb031e03b5b0554edda4f8828df361f896eb3c3706cda0474915040 flag :5e4ec20070a567e03c598eac510b4a85d1d71c0ceb6e8d6d4f75c9736d3b8e0641e7995bb92506da1ac7f8da5a628e19ae39825a916d8a2f
ここでまず、二つのdataの長さが違うことに気付きます。自分はflagのdataの末尾にあるae39825a916d8a2fという文字列をcheapのdataの後ろに引っ付けて試してみることにしました。
すると次のような画面が現れました。
なんとcheapがcheapgになっています。これによりae39825a916d8a2fがflagの末尾であるg部分に対応すると推測できます。*1
しかし、flagやcheapの文字ひとつひとつがハッシュ化されて末尾に固められているという確証はまだできません。
もしかしたらハッシュ値全体にちりばめられている可能性もあるからです。
次に、cheapを購入する前と購入後のdataの値について比べてみます。
cheap購入前:5e4ec20070a567e03c598eac510b4a85475daa246cb031e03b5b0554edda4f8828df361f896eb3c3706cda0474915040 cheap購入後:5765679f0870f4309b1a3c83588024d7c146a4104cf9d2c88d527869fa7bdbef28df361f896eb3c3706cda0474915040
後ろの32文字に注目すると、28df361f896eb3c3706cda0474915040という同じ文字列で構成されていることがわかります。
二つのページで共通する文字列はcheapだけであるため後ろ32文字がcheapを表しているということがおおよそ確定できます。
つまりcheap購入後の後ろ32文字と同じ位置にあるflagの後ろ48文字を交換すれば見事flagがとれるのではないでしょうか、早速試してみます。
はい、とれました。おわり。
フラッグ
33C3_3c81d6357a9099a7c091d6c7d71343075e7f8a46d55c593f0ade8f51ac8ae1a8
*1:まだサーバーが動いてるなら試すことができるが、ae39825a916d8a2fをさらに付け加えると、どんどんgを増やすことができる。
33C3CTF WriteUp try [150] web
ページを開くとHaskellのコードが書かれたテキストボックスとRunボタンが出てきます。
とりあえずRunボタンを押してみることにします。
Log in firstと言われたので適当な名前でログインしてみることにします。
ログインした後に再度試してみると今度はコードを実行することができました。
ソースコードを見ると
<form action="/run" method="post" accept-charset="utf-8"> <input id="run_file" name="run_file" value="fib.hs" type="hidden"/> <input type="submit" value="Run!"/> </form>
となっておりfib.hsの部分を変えれば任意のプログラムを実行できそうです。
ただし、fib.hsは/static/fib.hsにあるようなので何らかの方法で/static下にファイルを置く必要がありそうです。
ログイン後はさらに上部のメニューにUplodeとProfileが増えています。
UplodeからHaskellのコードがアップロードできるのであればとてつもなく簡単ですが、残念ながら使えないようです。
次にProfileを確認してみると、プロフィール画像としてGIF画像がアップロードできるようです。
試しにGIF画像をアップロードすると、/static/33c3_(UUID)/pic.gifにGIF画像が配置されるようです。
ここで/static下のファイルはURLを書きかえることで実行できることを思い出します。
試しに先ほどのソースのvalueの値をfib.hsから/33c3_(UUID)/pic.gifに変えてみると
GIF画像がコードとして認識されて実行されることがわかります。もちろん、実際はコードではなくGIF画像のバイナリであるためエラーが出ます。
ここまでのことから、偽装したHaskellのコードをGIF画像としてアップロードし、それを実行させることでフラッグを得ることができるのだろうと推測しました。
そこで問題になるのは、どういう形式のファイルをサーバー側がGIF画像として認識するかということです。
GIF画像の構造*1を調べると、GIF画像バイナリの特定のアドレスには固定値があることが分かるのでそこをしらみつぶしに消してはアップロードを繰り返し試してみました。
その結果、バイナリの最初の"GIF89a"と番地0x15の0x2Cの二つの固定値*2以外を変えてアップロードしてもGIF画像として判定されることがわかりました。
次に問題となるのは、この偽装GIFバイナリにHaskellのコードを埋めることです。
最初に考えたのはGIF89aという文字を関数として認識させることで、Haskellのコードの一部として使うというものでしたが、Haskellでは関数や変数の最初を大文字でおくことはできないのですぐに断念することになりました。
少しHaskellについて調べてみるとどうやら型や型クラスは最初の文字を大文字でおくことができるようでした。
しかし自分はHaskellのことをよく知らないので、slackに投げて聞いてみるとGIF89aを型(もしくは型クラス?)として後置宣言したコード*3をくれたのでそれをバイナリに埋め込みアップロードしたところ見事フラッグを手に入れることができました。
GIF89a i = GIF89a "aaaaaa" newtype GIF89a = GIF89a String main = putStrLn "Hello, World!"
slackでもらったHaskellのコード
GIF画像にHaskellのコードを埋め込んだバイナリ
以下フラッグ
33C3_n3xt_T1me_idri5_m4ybe
JAG夏合宿2016参加記
JAG夏合宿に参加してきました。
0日目
0日目はコンテストが無かったのでのんびり過ごしました。
自己紹介は緊張しすぎて、他の人の顔とか覚えてませんでした。
そのあと懇親会まで時間があったので、@AlbicillaTさんと@dohatsutsuさんと部屋が同じだった人と人狼をやろうとしたのですが、人が足りなくて出来なかったので怒髪さんのトランプで大富豪やゴキブリポーカーをやりました。
懇親会では寿司とパスタなどを食べました。パスタをもっと食べたかったのですが、気づいたらなくなっていたのであきらめました。
@mayoko_さんや@yurahunaさん、@tubo28さん、@osrehunさんなどプロ各位と話せたのでよかったです。ちなみに今名前を挙げた人たちの大半は合宿終了後に築地市場に行き刺身と化します。
1日目
1日目から@AlbicillaTさんと@startcppさんとチームを組んでコンテストに臨みました。僕がやるだけ問題を一問解いて、他の二人が考察して協力して二問、問題を解いていました。
(もちろん自分も問題の概要を伝えるなどはしました。)
2日目
2日目も自分がやるだけ問題を一問解いて、あとの二人が考察など協力して二問、問題を解いていました。とくにD問題は@AlbicillaTさんの考察がさえていてグッジョブでした。
C問題が単純に実装が面倒くさそうなだけに見えたので、マラソンマッチで鍛えた実装力で何とかしようと思ったのですが、REとTLEとWAの3コンボであえなく撃沈しました。
3日目
3日目はC問題がやるだけ問題に見えたのでやろうとしたのですが、うまくいかなかったので@startcppさんに投げてしまいました。すみません。
そのあとは他の問題の概要を@startcppさんに伝えて解いてもらいました。というか前二日もほとんど@startcppさんが解いてくれました。申し訳ない。
あと@startcppさんが解いてくれている間、H問題のコードをずっと書いていたのですが、最後完成したと思ったら、せぐふぉに見舞われて見事に死にました。
以上です。
運営さん、チーム組んでくれた方、話してくれた方、ルームが一緒だった方、オリセンから六本木に向かう途中に僕が突然クソなぞなぞに答えたのに快く受け入れてくれた方などありがとうございました。
おまけ
刺身と化したプロたち。
@chiwawa_star 集合写真です pic.twitter.com/TfCAOgpEtq
— b+k@数弱黄コーダー (@btk15049) 2016年9月5日
C言語でBMP画像を作ろう!
大学C言語の授業の定期試験で作成したレポート
Generate bmp image with C. · GitHub
1.目的
C言語を使ってファイルをバイナリストリームで開いてbmpファイルを作成しよう。
図1.この画像を生成する。
2.原理
2.1C言語でバイナリファイルを生成
C言語のstdio.hライブラリにはファイルを開く関数があるがそれを使うことで直接機械が読み取れるバイナリデータを書き込むことができる。
これを使うことで一からファイルを生成しよう。
2.2bmpとは?
bmpとは「bitmapimage」の略であり、imageという名前がついている通り画像ファイルだ。一般に使われているpngやjpegといった形式はバイナリデータが圧縮されているためC言語で扱うにはほかにライブラリが必要である。bmpファイルは圧縮しなくても画像ファイルとして作成することができ、バイナリデータを直接いじるのに複雑な操作が(pngなどと比べて)必要でなく容易である。そのため今回はbmpを使う。
3.ソースコード
1 |
//中京と書いてあるbmp画像を生成するプログラムです。 |
2 |
|
3 |
#include<stdio.h> |
4 |
#include"bmpsetting.h" |
5 |
#include”bmpsetting.h” は今のディレクトリからヘッダーファイル「bmpsetting.h」
を探してインクルードするマクロ。
Bmpsetting.hはbmpファイルのヘッダー情報を設定するための構造体と構造体を初期化するための関数が入っている。
7 |
int main(void){ |
8 |
|
9 |
FILE *BMPfp; |
10 |
errno_t error; |
11 |
|
12 |
return error; |
今回のプログラムはVisualStudio2013を使って作成した。VisualStudi2013ではセキュリティの意識が高く、fopenなどの関数が使えない。その代わりにfopen_sなどの関数を使われるように促される。
fopen_sはfopen関数と違い、FILE構造体を戻り値として返す形で開くファイルを設定せずにFILE構造体のインスタンスのアドレスを書きかえてファイルを開く。
fopen_sは戻り値としてerrno_t型の変数を返す。この変数の数値によってerrorが起こったかだけでなくerrorの種類がわかる。
bmpファイルに情報を書き込むためにはファイルにテキストではなくバイナリを書き込まなくてはならない。そのためfopen_s関数の第三引数において”w”ではなく”wb”のように”b”を加えることでファイルをテキストストリームではなくバイナリストリームで開いている。
13 |
int sfsdaf[10][18] = |
14 |
{ { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, |
15 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 }, |
16 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, |
17 |
{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 }, |
18 |
{ 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, |
19 |
{ 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 }, |
20 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, |
21 |
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1 }, |
22 |
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1 }, |
23 |
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 } }; |
配列を宣言する際に(変数名)のように記述すると配列の配列が作成できる。これらの数値をつかってbmp画像に入力するデータを決める。
24 |
BMPFileHeader bmpFH = InitializeFileHeader(); |
25 |
BMPInfoHeader bmpIH = InitializeInfoHeader(); |
26 |
ColorPalette colP[2] = { |
27 |
{ 0x00, 0x00, 0x00, 0x00 }, //Black |
28 |
{ 0xFF, 0xFF, 0xFF, 0x00 } //White |
29 |
}; |
30 |
|
31 |
bmpIH.ImgHeight = 0x0A; |
32 |
bmpIH.ImgWidth = 0x12; |
33 |
unsigned int ByteperImgLine = ((0x12 / 8) + 1) + 1; |
34 |
bmpIH.ImgDateSize = 0x0A * ByteperImgLine; |
35 |
bmpFH.FileSize = bmpFH.DateOffSet + bmpIH.ImgDateSize; |
36 |
|
37 |
|
38 |
fwrite((char*)&bmpFH + 2, sizeof(BMPFileHeader)-2, 1, BMPfp); |
39 |
fwrite(&bmpIH, sizeof(BMPInfoHeader), 1, BMPfp); |
40 |
fwrite(colP, sizeof(ColorPalette), 2, BMPfp); |
41 |
bmpファイルには画像そのもののデータだけでなく、ヘッダデータが存在している。ここではそのヘッダデータを記述している。
ヘッダデータには二種類のヘッダがある。ひとつはファイルヘッダというものでどのような形式のbmp画像にもこれが存在する。もうひとつは情報ヘッダで、このヘッダはCORE型やINFO型などの型があり、INFO型が一般的であるらしい。今回はINFO型を使用した。これらの詳しい構成は付属のExcelファイルに記述した。
42 |
unsigned int num; |
43 |
char zero = 0; |
44 |
for (int row = 0; row < 10; row++){ |
45 |
num = 0; |
46 |
for (int column = 0; column < 18; column++){ |
47 |
num = num * 2 + sfsdaf[9 - row][column]; |
48 |
} |
49 |
fwrite(&num, sizeof(int), 1, BMPfp); |
50 |
} |
51 |
|
52 |
fclose(BMPfp); |
53 |
return 0; |
54 |
|
55 |
} |
BMPfpに用意したデータを書き込む。
fwrite関数はこのソースの記述で言うと、アドレス&numを初期位置としてsizeof(int)バイト分のデータを1個取り出してBMPfpに書き込むという処理をしている。
このソースコードではsfsdafを一番目の配列からではなく最後の配列から入力している。なぜこうするかというとbmpファイルは最初のイメージデータが左下から始まり右方向に進み、改行すると今度は上方向に進むので下から順番に積み上げるようにデータを入力しないといけないためだ
4.結果
図1のような画像を生成するつもりだったが、実際にプログラムを組んだところ画像が反転しさらに謎の黒棒がついた画像が出来上がった。
図2.反転してしまった画像
5.考察
図3.出来上がった画像のバイナリデータ
バイナリデータに数値を書き込む前のint型の数値は「0x3FF6D」だった。しかしこのバイナリファイルで対応する数値(図3で赤丸で囲った部分)では「0x6DFF03」になっている。
この問題をGoogle検索で調べたところ、どうやらCPUの処理による問題らしい。
バイナリデータに書き込まれたデータはリトルエンディアンという配置方法でデータが配置されたらしい。リトルエンディアンは数倍とあるデータを転送する際に一バイトずつ上位バイトを下位バイトに埋めていく方式であるらしい。
これを解決するためには上位バイトは上位バイトにそのまま配置するビッグエンディアンという配置方法を使う、もしくは1バイトずつデータを配置していけばいいらしい。
6.参考文献・参考サイト
6.1bmpのバイナリ構造について
プログラミング/BMPファイル仕様/バイナリ構造 - ルーチェ's Homepage:
URL http://www.ruche-home.net/program/bmp/struct#image-data
6.2fopen_s関数やfwrite関数について
MSDN: URL http://msdn.microsoft.com/ja-jp/library/z5hh6ee9.aspx
C言語標準ライブラリ関数ポケットリファレンス:葛西 朝雄、技術評論社、2009
6.3エンディアンについて
バイトオーダ - ビッグエンディアン/リトルエディアン:URL http://www.ertl.jp/~takayuki/readings/info/no05.html
TCO16 Marathon Match Round1 に参加しました。
今日の2時にTCOMM16Round1が終わったということで、自分の戦略をここにまとめておきます。
最終的な戦略
まず貪欲で初期解を作り、それをもとに遺伝的アルゴリズムでランダムで線を入れ替えて(なぜ削除ではなく入れ替えるなのかというとそれは、NP-1本必ず線を引かなければいけないと勘違いしていたからです。)得点を上げていく手法を使いました。
貪欲にも遺伝的アルゴリズムにもそれを評価するためのスコアが必要ですが、それには(分割できた植物のある領域の数)+(残った根の長さ)/(全体の根の長さ)という評価式を用いました。
(分割できた植物のある領域の数)は一本ずつ線を引くと考えて、それから線の上にあるか下にあるかで二分割するのを繰り返して分けました。
根の長さについては深さ優先探索を使い求めました。まずvector<int>rootsから木を構成します。(全体の根の長さ)を求めるにはこの次に、深さ優先探索を使って葉のスコアは0として、親は子のスコアと親と子の間の距離をそのスコアとするというのをすべての植物に対して行います。そしてすべての植物のスコアを足すと全体の長さがわかります。
(残った根の長さ)は深さ優先探索を使って各線について子と親の間に線が通っていたときに、元の子の座標を交点の座標に書きかえて子の子はすべて消すというのを繰り返します。そうすると、根の状態は切り取られた後の状態になるのでさっき全体の根の長さを求めた方法と同じことをやると残った根の長さがわかります。
この評価方法をそのまま使うと、深さ優先探索の再帰のコストが大きくなってしまうため、NPが多いときには探索する深さを制限して使うようにしていました。NPが多いときに使う理由は、NPが多いときには深さを制限してもある程度本当の得点に相関性のあるスコアが得られるからです。またNPが多いときはとくに再帰のコストが多くかかるからです。
その他に考えた戦略
評価式はそのままで山登り法を使った方法
正直これでもある程度うまくいったのですが、途中で遺伝的アルゴリズムを使ってみたくなり使うのをやめました。
評価式はそのままで焼きなまし法と遺伝的アルゴリズムを使った方法
遺伝的アルゴリズムの本に焼きなましと遺伝的アルゴリズムを合わせたハイブリッド手法には様々な利点があると書いてあったため使いました。しかし本をまともに読まず我流で書いたためか確かな効果は得られませんでした。この手法はコンテスト終了直前に書いていたのでパラメーターの調整が間に合わず提出できませんでした。
評価式に円の半径を使って貪欲法を使った方法
植物の根を植物の中心点から四象限に分けて、根の長さから四つの円を書いてそれがどれぐらい削られたかで判定する方法を使いました。これは得点との相関性がないことから最終的には使いませんでした。
反省
序盤にも書いた通りルールを勘違いしていたとというのが本当に悲しいです。次からは問題文をちゃんと読んでおきたいですね。
Exampleの結果だけ見ていて他のテストケースでのTLEを気にしていなかったのも終了後に気づいた反省点です。あと次は時間内にビジュアライザ作りたいと思いました。