math314のブログスマートフォン用の表示で見るmath314のブログ主に競技プログラミング,CTFの結果を載せますこの広告は、90日以上更新していないブログに表示しています。DISCOさん主催のオンサイトコンテストに参加しました。太字で書かれているのに見逃して、一般の場合を解いていた。置いて、無理なら別のものを置くというのを先頭から貪欲に繰り返せば解けることが多い。O(n2)では通らないが、明らかに残っているものの中で最大の数と最小の数以外を考えなくてもいいことが分かるのでO(n)で出来る。まで構築済みの時、aiの候補として、残っているものの中で最大の数と最小の数のみを考えれば上記の式でやれるよねという感じになのだが、自分の頭の中では逆順に思いついていった。5が最初に出てくるのは経験だと思います。Aで複雑な解き方をした分Bの方が簡単だった。(提出なし)幾何は失敗すると時間が解けるので後回し決定。BをACした時点でDを解いている人もいるしDに突撃。Treeに乗せると解けるやつということが分かるので実装する。個人的には一番簡単だった。codechefで見かけるイメージ。乗せるとMLEやTLEが発生する気配を感じるので固定長のarrayを乗せることにした。CとEを見比べたところ、面白そうだしワンチャンあるのでEにチャレンジすることに。青とオレンジの層の間で直積をとる感じで必要な数を生成。最後の層のノードは3つ固定だが青とオレンジは分からない。パターンは同じオレンジ層のノードに乗せることは出来ない。(11:55)4つ毎に分ければどうなるだろう?ということでリファクタリングと改造を施しつつ粘る。(12:02)これが駄目なら5つ毎パターン、参照のないノードの削除、オレンジ層と緑層の頂点の一部をマージするなどを考えていたが不要だった。8分でCが実装出来るはずもないので終了。装置実装部門MM形式にも関わらず予選が30分なので、読解&シンプル解法高速実装コンテストということが想像できる。20分程度で書き上げたもののWA、最後までWAが取れなかった、残念。機械を範囲外に動かしたのが敗因だった様子。装置部門の決勝がめちゃくちゃ楽しかったので次回参加出来れば勝ち上がりたい。CTFだとそこそこの順位は何度も経験しているがこれらは全て団体競技。味方が強ければ、例え優勝出来たとしても自分単体はそこまで強いわけではないのかもしれないという気持ちが拭えなかった。今回の個人大会では多数の強い人々が参加している中での2位なので本当に嬉しい。これまで参加していた大会の中でも一番かもしれない。社会人となってしばらく経ち勉強や練習出来る時間も減ってしまった(スプラトゥーンが多大な影響を及ぼしている)。同時期に競プロをしていた人々と同じようにそのうちゆっくりとフェードアウトしていくかもしれないが、いい思い出になった。競プロが出来なくなる前に、ゆったりと参加出来て健康に良いらしいとされているKaggleにも参加してみたいですね。帰る時にプレートも一緒に持って帰ろうかと思ったけど、冷静に考えると置く場所に困りそうなのでかわりに写真を撮っていただくことにした。快く引き受けてくださったスタッフの皆さんありがとうございました。chibiegg日誌ISUCON8の決勝で準優勝しました、優勝できず非常に悔しかったです。競技終了直前では50,000点を超えていたものの、再起動後のチェックで31,000点程度と大幅に下げてしまいました。github.com時系列順10:00chibieggがansibleを書いている、sshの設定とかをしているようだが問題が公開されたので見る。マニュアルが結構長い。misodengakuと同時に読み始めて、マニュアルを読み次第goのコードを読み始める。SNSで拡散という項目をマニュアルでもコードでも見つけるが忘れる。logとnginxのアクセスログを出してもらう。アクセスが大半の様子。CPUは200%ガッツリ使っている。帯域を頑張る問題には見えない。本戦でオンメモリ戦略をやるのはしんどいだろうということでMySQLは引き続き使うことにする。1が必要なコードを見つけたのでつける。proをMySQLの本番環境に繋げると落ちて辛い。proの最新buildを使ってみると無事繋がる。支配的であることはわかる。ロウソクチャートを作るためのSQLが重たい事はわかるので、計算の仕方をちゃんと理解し始める。コードを読むと分かるのだがそこはボトルネックではない。途中で気づいたものの、害はないのでそのままマージすることにする。ここでEXPLAINした時にtableがpartitioningされていることに気づくがスルーする。実際はここでスルーすべきではなかった。講評にかいてあるので詳細はこちらをどうぞ。分からないけどGoLand上でisucoinが動かない、listenはしているようだが全てのリクエストにたいして404を返している様子。パソコンが何もわからない...最終的にはロードバランシングが必要でしょうということでchibieggが準備し始める。この時点でサーバ01でNginx+App、サーバ02でMySQL、サーバ03と04でApp、という構成に。Initializeが全台に対して行われるための仕組みを作っていなかったので、いつでもロードバランスできる状態にはしておきつつ、一旦サーバ01だけで処理するようにしておきました。requestを挙げた、間違いなく8時間以内に上限に引っかかるので、今やっても後でやっても変わらない。結果6,000点になった。分からないけどGoLand上でisucoinが動かない、listenはしているようだが全てのリクエストにたいして404を返している様子。くなって構成がスッキリしたと前向きに捉える。ロードバランスするとこの初期化リクエストは1つのアプリケーションプロセスにのみ届きます。全てのサーバの初期化を行うように実装しました。設定をsettingテーブルから都度参照するようになっていたのをやめ、グローバル変数に持つように改修することでDBへのアクセスを減らしています。動作はするようになったものの、数百程度のスコア上昇しかおきませんでした。tableを見ていたら不要なlockがあるので消す。までみそでんがSNSシェアを有効にするフラグがあると発言。ともに負荷が少なくて不思議に思っていたところだった。あまりにもtrueを返しすぎると、ユーザー増加に耐えられずタイムアウトが増えてしまうので、とりあえず1/8の確率でtrueを返すようにする。まで実装が重たそうなので敬遠していたが、どうしても必要に見えたのでローソクチャートのキャッシュに着手した。fixをコミットしていることが分かる。いう性質もと、私が雑にレスポンス丸ごとメモリにキャッシュする実装、まーす先生が丁寧にロウソク足をメモリにキャッシュする方法をそれぞれ実装しました。私の雑なキャッシュでも特に問題はなく、一気に25000点弱に。まーす先生の丁寧なキャッシュもバグ無く動作したため、両方をマージしました。30,000点弱になる。GitHub編集がコンフリクトしないであろうUserのアプリケーション側でのキャッシュをchibieggにお願いする。多少改善したがやはりRunTradeのSQLが重たそうに見える。なんとなくだがRunTradeが走った回数と約定が発生した回数に大きな開きがあるのではと感じ始める。実際にログを仕込んだところ、精々10%ほどしか実際に約定処理が行われていないことがわかった。Appのプロファイリングを行ったところ99%がbcryptの処理であることが分かった(もう少し早めにプロファイリングをするべきかもしれない...?)bcryptを外すと怒られるのでbcryptのコスト(回数)を10から4に落としたものの大差なし。37,000点程に上昇する。までここまで終わったところ、どうも/orderの高速化は頭打ちで/infoのアクセス回数も多いことからなんとかならないかと頭を捻る。50,000点を超える。までようやく再起動テストを始める。アプリに問題が発生する要素はないのでMySQLの対策。MySQLを再起動するたびに35,000~40,000点になるのでMySQLを温めるコードをchibieggが書く。実際にサーバーの再起動して確かめる時間は無かったのでこれは行わず。実際はサーバー再起動が大きく影響を与えたようで、結果論になるがこちらに力を入れるべきだった。結果30,000点程度に落ちて2位、無念。MySQLを温めるスクリプトが足りていないだけでなく、MySQLの使うファイルがキャッシュに乗っていないのが大打撃となった模様。していれば100,000点は本番中でも超えられたと思うので無念。Banは実装していなかったがこれも実装すべきだった。講評より一方、競技時間中に最大スコアを記録し、惜しくも2位となった「takedashi」は上記で言うところの完全クリアまでたどり着いているようでした。codeが400で返ってくるという事態が発生し減点により結果を伸ばすことができませんでした。(htmlが返ってきていたのでアプリケーションの問題ではなさそうということしか原因はわかりませんでした。100,000点を超えていればエラー多発でも完走すれば50,000点は出ていただろうと思います。こちらも結果論ですが、userのbcrypt以外はmySQLは不要な問題だったと思うので、ISUCON名物のオンメモリ戦略を取るべきだったかなとも少し思っています。00:51ISUCON8で準優勝したTweet広告を非表示にするもっと読むコメントを書く2018-09-17ISUCON8予選をオンメモリ戦略で通過したISUCON8の予選に参加しました。運営の皆様お疲れ様でした、今年はオーソドックスな問題だった気がします。44,295点で全体8位、予選通過のようです。今年もよろしくお願いします。以下箇条書きGoは速いだろうということでGoを選択。pythonの方が慣れているがCPU勝負になったときに不利...MacbookにGolandを入れていたが、Debuggerが起動せずに苦しんだ。なんか色々インストールする必要があるらしいが時間がないのでDebuggerなしでやることにGoのアプリのプロファイリング用にpprofというものがあるらしい、でも結局使わずmisodengakuはリモートで参加。keyを置いてもらうgitリポジトリを用意してもらう。MySQLのシンプルなもの。フロントはjsで触るところはなかった。APIと何個かのhtmlを返すエンドポイントをいい感じにする取りあえずベンチマークを走らせる。レスポンスが遅いため負荷レベルを上げられませんでした。レスポンスが遅いため負荷レベルを上げられませんでした。レスポンスが遅いため負荷レベルを上げられませんでした。レスポンスが遅いため負荷レベルを上げられませんでした。レスポンスが遅いため負荷レベルを上げられませんでした。レスポンスが遅いため負荷レベルを上げられませんでした。レスポンスが遅いため負荷レベルを上げられませんでした。以下になんかある?"/"以下と同じくらいの実装量のページ?table多い"/"がすごい量のSQLを吐き出している。本番サーバー上のMySQLで動かすとなんとレスポンスに40s+かかる。トンネルを作って接続していた。1GBメモリ少ないっぽいMySQLとGoがCPU/Memoryを食べあうことになりそうなので早めに分離。(合計時間的な意味で)MySQLに格納されているデータを見る。アプリケーションを1つしか起動しなくてもパフォーマンス十分出るよね?ISUCONだからねINSERT/UPDATEのないテーブルは改造するのに難しい点はない。nil}SELECT/INSERT/UPDATEは全てreservationStoreのデータを参照/追加/更新するINSERT/UPDATEは、アプリ/マシンの再起動に備えてMySQLにもデータを流す。}()メリット実装途中でも負荷が少なければそれなりに動く。SELECTはメモリ上のreservationStoreを参照、INSERT/UPDATEはSQLを同期的に発行しつつreservationStoreも更新という実装でも一応動くでもtransactionとか消えてるから死ぬときは死ぬ。ベンチマークは通らないGoだとSQL発行の同期/非同期の切り替えがとても簡単。非同期にしてバグったら最悪同期に戻すことでベンチマークを通すことが出来る完成してしまえばMySQL依存は無くなる。場合によってはN+1問題が発生していた箇所は放置しても爆速になっている可能性すらあるので他の改善に時間が使えるデメリット全部実装し終えないとベンチが通らないMySQLにindexを貼ったりcolumnを整理した方が早くなる場合が大半なので慎重に考えるgoroutine内(非同期)でSQLを発行することに気をつける。}()ISUCON以外でやろうとすると怒られる。みんなで着手し始めたこのあたりでsheet関係のSQLが無くなったのでベンチマークを走らせたら"座席がランダムではありません"と怒られる。ランダムじゃないとだめなのか...Fisher-Yatesのシャッフルを実装したら通った。スコアは変わらず13:30くらいになってreservation周りの半分くらいSQLを消す。全部reservation周りのSQLが全部消えたのでテストするけどfailする。UPDATEが悪さしてるなんかuserもバグってるらしい。30000点を超えて1位になったので喜ぶGoがだいぶ分かってきたのでこの調子でeventも剥がすことに。eventを剥がし終わったのでもっかいベンチを走らせるも25000点。最高得点(44295)が出る。何も変えてないのに2万点弱ブレてびっくりする目標は予選突破であって1位ではないのでこれで撤収。ホワイトなISUCONだった感想MySQLからデータを剥がしてスコアが上がるのは面白い、結局今回はindexを使わなかった気がするちゃんとindexを貼ってもスコアは上がったらしい?こっちの戦略でも良かったかな...プロファイリングが必要な段階まで行けなかったのは心残りデータ全部剥がした後適切なデータ構造で管理すればスコアは軽く倍になりそう。}).ToSlice(&reservations)Goでlinq辛すぎ問題。}).ToSlice(&eventIds)普段使わないlaptopで苦戦した。IDEのインストールとかは事前にするとよさそうbranch名を間違えてreserveのつもりがreverseになっていた。なってこれを満たすことがわかります。呼ばれているそうです。受験で出てきそうな見た目をしていますが、この問題は凶悪なのか解法は見たことがないです。あることを証明します。要約したものとなっています。昔、箱庭XSSという問題がSECCONで出題されました。どのような問題だったかは他の方のブログを見て頂ければ分かるかと思います。nash.hatenablog.com問題作者のスライドはこちらです。VB.Netのコードに変換出来ない(大体落ちたり例外が発生する)デバッガでattachすると挙動が変わったり、答えが変わるバイナリを書き換えると、checksum一致処理に引っかかるという特性があります。webの問題として解いてほしいらしく、作者さんのスライド曰くとのことなので、チートで解こうと考えました。今回要求される要件はdebugger検知に引っかからない実行ファイルを書き換えないchecksumが変わるための二つです。disassembleしてみると、「正規表現で文字列を置換している処理さえ潰せればフラグを取れるのでは?」と思ったので、「Regex.Replaceの挙動を変更する」ことを目標にしました。箱庭XSSのみに特化したプログラムを書いても面白くないので、もうちょっと大きく出て「.Netアプリケーションのメソッドを、実行ファイルを書き換えずに挙動を変える」ということにしましょう。(なおこれ以降箱庭XSSは出てきません、手段と目的は往々にして入れ替わります)実装github.comに置いてあるのでご自由にどうぞ。ダウンロードして試してみてください。動かし方はreadmeに書いてあります。ついてのスライドとコードを載せておきます。Hacking追記3:yosupoが最新版の解説を書いたようです。yosupo.hatenablog.com以下は旧記事です。解説はコードに埋め込みました。Conjectureだそうです。3000まで正しい事は確認しましたが、気になる方がいるようなので追記します。magicを使わなくても解けたようです。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。