kotamanegiの取り扱い説明書

のんびり趣味の事を書いてます。

ISUCON11予選 kotamanegiの参加記

概要

ISUCON11予選にチームkotamanegiとして一人で参加し、学生枠で本選に出場できることになりました。 主要な改善点・工夫は

  • DBのindexをきちんと構築する
  • SQLのうちLIMIT句が効きそうなところに追加する
  • 自動デプロイスクリプトを書く
  • POST /api/condition/:jia_isu_uuid に対する実装の、確率でリクエストを破棄する処理を削除

の4点でした。 結果は全体40位/学生4位となり初参加でしたが本選に出場できるほどの好成績を残せました。

開戦前

チーム編成について

初参加なので他人に迷惑をかけたくないという気持ち & 本選に行けると思っていなかったのがあって今回は1人で参加しました。 今年のISUCONに参加してみて、僕の実力で戦えそうな雰囲気だったので来年はぜひチームで出てみたいです。

事前準備

複数台与えられた時のシステム構成だけを考えていました。 DB1台+Web2台で、Web2台間はnginxでいい感じに振り分けるつもりでした。

作業のタイムライン

メモを取っていないため時系列は適当になっています。

開戦 ~ 3時間経過地点まで

  • 0:00 当日マニュアルが開かなくて焦る。 とりあえずAWS Cloud Formationにダウンロードしてきた設定ファイルを投げて環境構築してもらう。
  • 0:05 当日マニュアルが開けるようになる。 初回のベンチマークを実行する。
  • 0:30 scpでファイルの転送が出来るようになる。 ホームディレクトリの内容を全て(！)ダウンロードする。
  • 0:40 ダウンロードしてリポジトリにpushしようとしたが、~/localディレクトリが異常に大きいことに気づく
  • 1:30 ~/localディレクトリのGoコードは外部ライブラリであることに気づく
  • 2:00 各サーバに置いてあるレポジトリについて自動でgit pullするデプロイスクリプトを書く
  • 2:30 ~/webapp/go内のコードを読んでいる最中に、ポータルの質問コーナーを見てアプリケーションマニュアルの存在に気づく
  • 3:00 Goコードを書き換えて実行ファイルを送り込むが、変更が反映されなかった

3時間 ~ 5時間経過地点まで

  • 3:05 ps -axでプロセスを見てみると~/webapp/go/isuconditionを実行しているプロセスを発見する
  • 3:30 サービス名がisucondition.goであることを突き止める
  • 4:00 デプロイスクリプトを書いて改造Goサーバが動作することを確認
  • 4:05 topコマンドでMySQLサーバがボトルネックになっていることを発見、別サーバに分離する作業を始める
  • 5:00 別サーバに分離が完了、ついでにPOST /api/condition/:jia_isu_uuid も分離

5時間経過 ~ 最後まで

  • 5:05 DBにindexを張る作業を始める
  • 5:30 EXPLAINを付けてSELECT文を実行してもindexが使われず、原因究明を始める
  • 5:40 DB系ファイルの転送を忘れていたことが発覚しデプロイスクリプトを修正
  • 6:00 ボトルネックが解消しMySQLサーバのCPU使用率が130%前後に落ち着く、この時スコアが3.5万程度になる
  • 6:30 POST /api/condition/:jia_isu_uuid に対する実装の、確率でリクエストを破棄する処理を削除
  • 7:00 MySQLサーバのCPU使用率が200%に再び戻る、スコアが変化しないことから他のエンドポイントの改善を始める
  • 7:10 SQLにLIMIT句を付ける作業を行い、ベンチマーク実行
  • 7:15 ポータルに障害発生しアクセスできなくなったが、一瞬7万点までスコアが上昇したことが確認できた
  • 7:16 DBを見ているとisu_conditionだけがカラム数80万に達しておりここがボトルネックと判断
  • 8:15まで 障害が発生している間にPOST /api/condition/:jia_isu_uuid をバッチ処理に切り替える実装を書いていた
  • 8:15 競技再開、ベンチマークを実行するが点数が変化せず困惑する
  • 8:30 サーバ側のgitレポジトリ内の内容を操作した結果pullが正常に行えず変更が反映されていないことを確認し、再度ベンチマークを実行
  • 8:32 スコアが1000になりPOST /api/condition/:jia_isu_uuid が動いてないことがわかる
  • 8:35 変更をrevertして元の7万点コードに戻す、何回か実行していると7.5万点までは上がった
  • 8:45 コンテスト終了

分析

自動デプロイスクリプトを初手で書いたのは後半の作業効率の向上にとても効いたと思っています。 万が一環境を破壊したとしてもすぐに環境再構築が出来るというのは精神的にもメリットが大きかったです。 再起動スクリプトも仕組んでいたので再起動試験にも安心して対応できました。

DB的な面では、EXPLAIN句を知っていたおかげでindexが使われていないという致命的なミスを発見できたのが嬉しかったです。 知らなかったらスコアが低いままだったのを考えるとEXPLAIN句は重要な役割を果たしてくれました。

アプリケーション的な改善は後回しにしていたらほぼ改変する暇がなくなってしまいました。 DBの改修で手一杯になっていたのでサーバ構築の事前準備をしていたら時間が取れたのかもと後悔しています。

感想

インフラ系の環境構築コンテストは初めてだったのですが、高速化の様子がうまく可視化されていて楽しかったです。 本選はもうちょっと対策して賞金を狙っていきたいと思います(強欲)

ICPC 2020 Asia Yokohama Regional 参加記

2021年3月16~17日に開催されたICPC2020 Asia Yokohama Regionalにチームonionsで参加しました。 メンバーはjupiroさん・kuhakuさん・kotamanegi、コーチはbadlyluckyさんです。 最初に結果を書くと、ABCEGHIJKの9完で4位でした。

コンテスト前

8時まで寝ていました

コンテスト中

jupiro -> A, kuhaku -> B, kotamanegi -> C以降を眺める という役割分担でスタートしました。 A,Bの実装に苦戦する姿を見ながらC以降を流し見すると、Cがとても解きやすそうに見えたので初手として着手しました。 迷路の解き方の一例である左手法は実装が簡便なので、命令を愚直に書くと6行で書けたのでACを確信。 左手法が適用できる条件が必ず満たされることを確認してから総当たりを実装して提出するとFAの表示が出たので脳汁ブシャー。 普段バイトで実装している量子回路シミュレータqulacsの設計を参考にしてポリモーフィズムっぽく実装すると綺麗に書けました。

次の問題を探して遊覧している間にjupiroさんがJをACして一気に上位入り。 問題を眺めている内にG問題で天啓が降りて書き下すとAC。これでさらに順位が上がりました。

解法が思い浮かんだらしいkuhakuさんとjupiroさんにE問題を投げ、並列考察していたIはどうせ動的計画法でしょと決めつけて実装してみたら本当にACしてしまい、嬉しい反面困惑してしまいました。こんな上位を維持したままICPCで走り続ける事になるとは想像すらしていなかったので入賞が頭にチラつき始めたのはこのタイミングからだったと思います。普段大口を叩いていますが自分の実力は自分が一番よく知っているので、まさかこんな上位争いをする事になるとは正直思っていませんでした。 ここまでくると着手できる問題も少なくなったので、苦手ですが文字列問題Kにチャレンジすることにしました。 ローリングハッシュを書くのが面倒かつ怖いと思って後回しにしていたんですが、(僕の中では自明だった)動的計画法を書いてバグらせながらもAC。 Kに夢中になっている間にkuhakuさんとjupiroさんもEをACして、残りDとFの時点で4位になっていた事に驚きました。しかし同時にWF枠獲得必要条件がDまたはFのACだったので何がなんでもどちらか通さなければならないという思いが勝っていて険しい気持ちでいっぱいでした。 問題を何回読み直してもどうせ正解法では今の実力では解けないと思ったので嘘解法を錬成して提出しましたがやはりダメでした。

感想

予選では11位だったので10位以内を目標にしていましたが、結果は4位入賞で去年の21位から大躍進でした。 チームメイト、応援してくれた皆様、そして裏で支えてくれた猿渡先生に感謝しています。 来年度の阪大チームも上位争いできるよう精進を続けていきます。引き続きよろしくお願いします。

P.S. 西尾総長見てますかー？？？？？阪大がICPCでまさかの4位ですよー！阪大を全世界に向けて宣伝したので褒めてください！！！ワニ博士バンザーイ！！！！！

ICPC 2020 国内予選 参加記

2020年11月6日に開催されたICPC2020 国内予選にチームonionsで参加しました。 メンバーはjupiroさん・kuhakuくん・kotamanegiです。 最初に結果を書くと、ABCDFの5完で11位でした。

コンテスト前

今年はリモートでの参加だったので、恐怖に打ち震えながら寝そべっていました。

コンテスト中

今年は並列コーディング可だったので、jupiroさんがA、kuhakuくんがB、僕がCを解くという役割で挑みました。 コンテストが始まってCを見ると(実際はDを間違って開いてました)、ガチガチの構文解析ゲーだったので解き始めてしまいました。 AとBのAC報告が上がった所で、Cにしては難しいなと思って他の問題を読もうとしたところで、ようやくDを見ていたことに気付きました。 本来のCを見ると、愚直解で通りそうな問題だったので書いてACを取りました。

その後Dに戻って書いていると、誤読している事が発覚。 ちゃんと問題を読んでみると不等号が、不等号ではなくmin,maxに近い働きをしていると気付きます。 どこかで見たことがあるなと思っていたら、O(n * 2n)の全探索である事に気づいてAC。

続いてEを見ると、4分割できる所までは気づきましたがそこから先が分からず断念。 諦めてFを見ると、Link-Cut木を持っていると簡単に出来そうな事に気づきます。 Link-Cut木は持っていないのでmergeの時に頂点を追加するUnion-Findを書いてAC。

ここで残り時間がわずかになっていたので、Eを書ききれる気力もなく順位表を眺めていました。

コンテスト後

いい生活は今年で20周年で賞を受賞したかもしれません。 横浜のカタログギフトが楽しみです。

反省

F問題に時間をかけすぎました。 もっと実装ゲーを早く通せるようになりたい。

第6回 Asprova プログラミングコンテスト

はじめに

第6回Asprovaプログラミングコンテストで提出回数部門と得点部門でダブル優勝しました！ 1位を維持するのに必死になっていたため最終的に109回提出しました。

解法

高速化のため、下準備として処理の単位として864秒などの3桁秒ごとで動作を決めていく事にする。

基本的には、粗利/(納期遅れ許容時間数量かかる時間) をオーダの評価関数として貪欲に割り当てていく。 納期遅れによるペナルティが発生中のオーダーは評価値にさらに4を掛ける。

最初に段取り時間が発生しないオーダーは優先的に割り当てる。 次にまだ割り当てがないパン焼き機にオーダーを割り当てていく。 最終的にパン焼き機にオーダーがある程度貯まった場合のみ実際に稼働させる。 オーダー分割については、できるだけ大きい個数が取れるように適切に分割していく。 雑に分割するとオーダー分割の個数の最小要件を満たせずに詰みになるケースが存在するので注意する。

乱数ガチャ要素として、単位秒の設定とパン焼き機を見る順番と採用する評価値の下限の3つを加えた。

工夫

手元で実際に動作させると、特にオーダー数10000のケースでTLEの危険性がかなり高い事がわかる。 そこで安全策を取ってオーダー数10000の場合は試行回数は2回に抑えた。

評価関数を調整していると、1000ケースでテストした場合に一部のケースが0点になる事に気づいた。 そのようなケースは評価関数を安定寄りに設定すると減るが、逆にプレテストの結果が悪くなってしまった。 結局妥協して安定性を取ったせいで朝起きるとプレテスト4位になっていて本当にこれで良かったのかと自問自答していた。 システス後の結果を見るとこれで良かったらしい。ビビらせやがって。

ソースコード

https://atcoder.jp/contests/abc166/submissions/12949813

ICPC 2019 Asia Yokohama Regional 参加記

2019年11月16~18日に開催されたICPC2019 Asia Yokohama RegionalにチームTrumpetで参加しました。 メンバーはfineさん・snow39さん・kotamanegi、コーチはfuruya1223さんです。 最初に結果を書くと、ABGHの4完で21位でした。

 

Day1

関内駅でチーム集合だったので、早めに行ってトンカツを食べました。  

f:id:kotamanegi:20191129191033j:plain
トンカツうめえ

(覚書ですが僕のTシャツのサイズはLです。初日にチーム写真撮影があるので厚着しすぎるとTシャツがピチピチになってかっこ悪いぞ！)

夜は北九州高専チーム+阪大チームで横浜中華街に行きました。適当にキャッチに捕まって流れていくと中華食べ放題の店にたどり着きました。 食事をとりながら親睦を深めている最中に隣の部屋から「この問題はオーダ〇〇〇〇で解けます」等の聞きなれた台詞が聞こえてきて明らかに競プロerというのを確信。乗り込むとJAGの方々がいました。

ベルリンの壁(隣の部屋との仕切り)が崩壊し、グループがmergeされました。 熱烈なJAGへの勧誘を受けながらその夜が更けていきました。

Day2

朝早起きした後、急いでコンテスト会場に行きました。

コンテスト前

入場して座席に座った後は役割分担の最終確認をしていました。fineさん・snow39さんでAとB問題を解き、私が環境整備&全問題をざっと目を通す事に決定しました。(今更)

9:20ぐらいに "Do you want to go toilet now? If you want, please raise your hand." とアナウンスされたのでトイレに行こうとしました。 すると "Since everyone is ready, contest will begin at 9:25."と再度アナウンスが入りました。

すぐに席に戻りました。

コンテスト中

まずコンテストシステムにログインを済ませた後、問題ごとのファイル作りなどをしました。 その後問題をとりあえず簡単に流し読みすると、G,H,Iの3問は問題文を見ただけで解けますオーラが漂っていたので考察します。

考えているとHが分かったので次にIを見ます。 一瞬意味が分からなくて読み直してみると何を実装すればいいのかはすぐに思い浮かびました。(実装できたとは言ってない) そうこうしている内にPCが空きました。Hを実装して一発Correct。 この時、阪大は2位だったみたいです。

次にIを実装しようとしますが、実装しきれずにWA。泣く泣く交代。

実装してみてIはやっぱり実装難と思ってG問題を見に行きました。 オートマトンみたいだなと思って図を書くとBitDPじゃーんと気づきましたが、Iの失敗もあって慎重に考察をしていました。 すると、2進数のand演算で上手くできる事に気づき、Eの実験が終わるのを待って交代しました。 実装も終わり、サンプルを実行してみると最後のケースが通らずに印刷してまた交代しました。 なぜかなあと思ってよく見てみると、条件分けが一つ足りない事に気づいてコピペで実装しようとしました。 微調整をして提出するとこれも一発Correctになりました。 その後はコンテスト終了までIのバグで時間を溶かしたりしていました。

コンテスト後

EとI問題が解けなかったのでチームで反省をしていました。Eはともかく、僕が担当していたIを解けなかったのは相当痛かったです。

全て終わった後観光に行きました。赤レンガきれいだなあ。 f:id:kotamanegi:20191129210924j:plain

Day3

最終日の企業見学はグループBでしながわ水族館からスタートだったのですが、満員電車には乗りたくないという意見で一致したのでアニソンカラオケをしました。その後の企業見学にはきっちり参加しました。

感想

大学生になったらICPCに出るんだという夢というか憧れみたいなものがあったので、1年生のうちからアジア予選にも参加する事ができて嬉しかったです。来年度もまたアジア予選に参加できるよう、これからも精進を続けたいと思います。

ICPC 2019国内予選 参加記

2019年7月12日に開催されたICPC2019 国内予選にチームTrumpetで参加しました。 メンバーはfineさん・snow39さん・kotamanegiです。 最初に結果を書くと、ABCDEの5完で14位でした。

コンテスト前

開催場所に集合した後もしばらく時間があったので、お茶を3L買いに行くなどしました。(競技中めちゃくちゃのどが渇くため） チームで戦略の再確認もしました。Aは僕の担当というのが決まって、あとの問題は問題を見てから担当を考えようみたいな感じだったと思います。

コンテスト中

序盤は提出時間の勝負みたいな感じになると予想できていたので問題文の印刷を終える前に早速A問題に取り掛かりました。 こんなところでWAを生やすわけにいかないんだと心の中で叫びつつA問題を提出しました。無事にACできました。

B問題とC問題は軽く見るとこれは絶対にチームメイトが解いてくれると思ったので全て託して僕はD問題を見に行きました。 D問題を見て1秒でstackを使った解法が思いついたので書いてみましたがSampleすら合いません。 やはりD問題は険しいなあと思いながら考察を続けていきます。 考えている最中にチームメイトがどちらも1発でB問題とC問題を通し、嬉しい反面焦りを感じました。 sampleを見てみるとカウンターを1周以上押した方がよいケースがある事に気づき、とりあえずDPを書きます。 遷移を適当に調整しているとsampleが一致します。通らないだろうなあと思いながら、縋るような気持ちで提出するとACしました。 未だに解けた理由はよくわかっていません。まさに天啓。

チームメイトに状況を聞いてみたところ、E問題は幾何問題という事で解けないと判断したらしくFの考察に入っていました。 個人的にはE問題のほうが自明だったので実装を始めます。 実はこの時に誤読をしており、ブロックの表裏を問題文の図通りに設置する物だと思ってそのまま実装したところ、当然sampleは通るもののWAが出ます。 「はーーなんで通らんの？」と泣きそうになりながら問題文を読み直すと、表裏も自由にできると気付きました。終了時間も迫ってきていたので慌てて実装します。 愚直に実装したものの、プログラムの速度がかなり遅かったので、枝刈りも実装していきます。 最終的に5分ぐらいの実行時間になったのでそれを出すとACして5完。 体感ではそのあとすぐ時間切れになってコンテスト終了でした。

コンテスト後

打ち上げめっちゃ楽しいｗ（本当にこれ以外の感想がない）

反省

解説を見たところF問題は難しい問題ですが、観賞用問題ではありませんでした。 僕は絶対に解けるようになっていなければならないと反省しました。 また、今回E問題で時間を予想以上に潰してしまったのでアジア予選までにもっと実装力をつけなければならないなあと痛感しました。

猛精進をします。

katagaitai関西med#5のwriteup

ebCTF 2013 – Bin400 – md5collidingのWriteupです。

 

とりあえずMD5のハッシュ値が同じで、出力は異なる5つのPEファイルを作るのが課題なので、まず出力をハッシュ値と関係ないデータを使って変化させなければなりません。そこで、実行ファイル名を使って分岐させます。c言語ではargv[0]に入っている筈です。

次にMD5の性質について調べてみます。

なので、1つのファイルから2つのMD5のハッシュ値が同じファイルを作り、それと最初のファイルの差分を取ってほかのファイルにつけていくという動作を行えば、倍々ゲームでMD5のハッシュ値が同じファイルが増えていきます。

 

というわけで、C++でコードを書きます。

#include <iostream>
using namespace std;
int main(char *argv[]) {
if (argv[0][0] == '1') {
//ファイル名が1で始まるとき
cout << "All Eindbazen are wearing wooden shoes" << endl;
return 0;
}
else if (argv[0][0] == '2') {
//ファイル名が2で始まるとき
cout << "All Eindbazen live in a windmill" << endl;
return 0;
}
else if (argv[0][0] == '3') {
//ファイル名が3で始まるとき
cout << "All Eindbazen grow their own tulips" << endl;
return 0;
}
else if (argv[0][0] == '4') {
//ファイル名が4で始まるとき
cout << "All Eindbazen smoke weed all day" << endl;
return 0;
}
else {
//ファイル名が5で始まるとき
cout << "All Eindbazen are cheap bastards" << endl;
return 0;
}
return 0;
}

 これをコンパイルしてPEファイルに変換した後、

github.com

というツールを使ってMD5の値を衝突させます。

ファイルと一緒に実行すると、MD5が同じ値になっている2つのファイルが生成されるはずです。

あとはそれと元のファイルとの差分を取ってそれをほかのファイルにつけていけば、1 -> 2 -> 4 -> 8　とファイルが増やせ、結果5個のファイルを作ることができます。そして、ファイル名を適切に変更してサーバーに送信すればFLAGがゲットできます。(現在はサーバーは停止しています)