tatsumack blog

エンジニアによる雑記です

ISUCON10予選にチーム「カレーおじさん」で参加して16位で予選通過しました

ISUCON10予選に「カレーおじさん」(@tatsumack, @sugaret, @masakingp)というチームで参加しました。
最終スコアは2608で、16位で予選通過することができました。

isucon.net

@sugaret の振り返りはこちら
sugaret.hatenablog.com

予選問題の解説と講評はこちら
isucon.net

チーム「カレーおじさん」

前職の社内ISUCONをきっかけに組んだチームです。昨年、本家ISUCONに初参戦したものの予選で惨敗していました。

事前準備

前回はチームで集まって練習したりしたものの、今回は特に練習する時間を取らずに当日を迎えてしまいました。
チーム練習はしませんでしたが、個人的には、前回のISUCONに参加するときに作っておいた秘伝のタレの見直しやツールの素振り、チームの役割分担の確認を前日の夜に行っていました。
GitHub - tatsumack/isucon-tools: ISUCON秘伝のタレ

こんな感じのスクリプトを用意していました。

  • install.sh
    • alp, pt-query-digestなどの計測ツールのinstall
  • deploy.sh
    • 各サーバーに入って、nginx/mysql/go serverのrestart、git pullしてbuild、access_log/slow_logの退避を行う

使用言語

Go

計測

計測には以下のツール/コマンドを使っていました。

いつもはpprofも使うのですが、今回アプリケーションはボトルネックにならなかったので使う機会がありませんでした。

当日の流れ

レポジトリはこちら
github.com

9:00集合
12:20~
  • 全員でレギュレーションを読みつつ、@sugaretがアプリの挙動確認、@masakingpがローカルでの環境構築、@tatsumackが各種計測ツールを使えるように整えていた
  • ベンチが使えない状態だった
13:15~
  • ベンチが使えるようになった
    • 初期スコアは371
  • nginx、mysqlカーネルパラメータの秘伝のタレを投入 @tatsumack
    • なぜかmysqlのslow queryが吐かれず、原因調査
  • alpによるアクセスログの解析で /api/estate/search・/api/chair/searchのエンドポイントが支配的だということが分かったので、改修に取りかかる @masakingp
    • 検索条件を組み立ててLIKE検索をしてるところが遅そうだから、正規化するなりして上手いこと回避したいですね、という話をしていた
  • botからのアクセスを弾く実装もまあ必要でしょうということで、echoのMiddlewareで弾く処理を実装する @sugaret
    • 実装したものの、botからのアクセスが少ないし、スコアがあまり上がらないなあという話をしていた
    • のちに実装ミスがあることに気付く
  • この頃のスコアは450前後
15:00~
  • slow queryが吐かれない原因を突き止め改修する @tatsumack
  • pt-query-digestで解析したところ、検索条件を組み立ててLIKE検索するクエリは全然なかったので撤退 @masakingp
    • やっぱり計測は大事
  • dstat, topコマンドを叩いて、CPUが100%に張り付いていてmysqlが支配的だったので、slow queryを潰していくところから着手することに
    • indexを貼るだけで解消できそうなクエリがいくつかあったので、indexを貼って回る @sugaret
    • 物件がpolygonに含まれるか判定するクエリはアプリ側で計算できそうだよねという話になり、実装に取りかかる @masakingp
    • Prepareもそこそこ支配的だったので、interpolateParams=trueを入れて、アプリ側でプレースホルダ置換するように変更 @tatsumack
    • order by popularity desc, id asc は昇順・降順が混在していてindexが効かない。実は id asc いらないんじゃね?っていう話になり、@sugaret が id asc を外した修正を入れてみるとなんとベンチが通る
  • スコアが900まで伸びる
17:00~
  • 椅子が物件のドアを通過できるかを判定するクエリが全然index効いてないので改修に取り掛かる @tatsumack
    • (door_width >= ? AND door_height >= ?) OR (door_width >= ? AND door_height >= ?) OR ... となっていた条件を1つの (door_width >= ? AND door_height >= ?) で取得できるようにする
    • 実装はすぐにできたがベンチでFAILして頭を抱える
  • ベンチがFAILしたときに、エラーメッセージが何も表示されないという事象がしばしば発生する。 @sugaret が運営に問い合わせるとエラー内容を教えてくれた
    • 以降も何回か表示されないことがあったので、問い合わせをした
  • select count(*)系のクエリは、件数をカウントする別テーブルを作れば良さそうだよねという話になり実装に取り掛かる @sugaret
    • この改修は結局取り込まれず
  • @masakingp が実装していた物件がpolygonに含まれるか判定する改修が入ってスコアが1095まで伸びる
    • 予選突破圏内に入ってテンションが上ってスクショを撮ったりしていた
f:id:tatsumack:20200916003349p:plain
記念スクショ
  • そろそろ複数台に分けた方が良さそうだよねという話になり、まずはweb1台・mysql1台の構成に変更する対応に取り掛かる @tatsumack
    • 椅子がドアを通過できるか判定の改修は @masakingp にお願いする
18:00~
  • web1台・mysql1台の構成に変更する @tatsumack
    • スコアが1321まで伸びる
  • ベンチが不安定になってきていて、もしかすると id asc を外したのが原因かもということになり、id ascを外した対応をrevertする @sugaret
  • 椅子がドアを通過できるか判定の改修が終わる @masakingp
    • ベンチでFAILしていたのは件数を絞り込む処理が抜けてしまっていたのが原因だった
  • botを弾く対応が不十分だったことに気付いて、修正を入れる @sugaret
    • スコアが1622まで上がるが、ベンチのステータスがCANCELLEDで終わってしまう
    • その後何回かベンチを回すが、スコアは1200~1350で止まってしまう
  • webはリソース余裕あるけど、mysqlはCPUが100%で張り付いているので、3台目はmysqlが良さそうだよねという話になる
  • chairとestateでDBを分割するのが良さそうだということを思いつき、mysql2台構成に取りかかる @tatsumack
  • 最終的なサーバー構成は以下のような形になった
    • 1. nginx / app
    • 2. mysql (estate)
    • 3. mysql (chair)
20:00~
  • mysql2台構成にしたものの、/initializeでベンチがFAILしてしまう
    • ベンチの不具合を疑って、何度かベンチを回すもFAILしたままで頭を抱える
    • 残り時間も少なくなってきたので、3人でデバッグを始める
    • 1台目のmysqlサーバーに/initializeを飛ばし、 1台目の/initialize内で2台目のmysqlサーバーの/initializeを呼ぶという実装を入れていたが、2台目の/initializeで自身の/initializeを呼んでいて無限ループが起きていることに気付く
    • これは今思い返すと、1台目の/initializeから2台目のmysqlサーバーに向けてmysqlコマンドを流すようにすればよかっただけだった
  • 「この修正が間に合わなかったら確実に戦犯だな…」と思いながら、なんとか終了10分前に改修が完了する @tatsumack
  • スコアが2608まで上がる!歓喜
    • ここからベンチガチャをして上振れを狙うか、ここで止めておくか議論になる
    • ボーターは2000くらいだと予想して、ベンチを回さないという判断をする
    • 結果的にはこれが正解だった。僕はベンチを回す方に傾いていたが、2人が冷静だった。感謝!
f:id:tatsumack:20200915223540p:plain:w400
終了直前の奮闘の様子
21:00~
  • 競技終了
  • 最終スコア的には通過していそうだけど、再起動試験を全くしていなかったのでとても不安
24:00
  • 帰りの電車の中で予選通過したことを知る

感想

  • めちゃめちゃ楽しかった
    • 中盤からボーダー近辺をウロウロしていたので、もしかすると予選突破できるかもしれないという緊張感の中で競技を楽しめた
    • 残り1時間は暗雲が立ち込めてたけど、終了直前にスコアが爆増して本当に気持ちよかった
      • 心臓にはとても悪かったし、とても疲れた
  • 良い問題だった
    • 「何をしたらスコアが上がるか全く分からない」みたいなストレスフルな状況になることがなかった
    • 愚直に計測して愚直に課題解決をしていくとスコアが上がっていったように思う
  • タイムマネジメントは大事
    • 今回はギリギリ間に合ったから良いものの、再現性のある勝ち方ではないと思う
    • 競技終了の時間から逆算して、複数台構成への移行/再起動試験/ベンチガチャなどをいつから始めるかは整理しておきたい


ISUCON運営の皆様、ありがとうございました。
本戦もよろしくお願いします!

シュッとGoにコントリビュートした話

この記事は Go7 Advent Calendar 2019 の 19日目の記事です。

今年の7月に1ヶ月ほど有給休暇を取得し、時間があるのでせっかくだから何か大きめのOSSにコントリビュートしたいなと思い、Goにコントリビュートすることにしたときの体験談です。
それまでGoでがっつり開発した経験はなかったのですが、無事にGoにコントリビュートすることができました。

issueを見つける

コードを読み込んでバグを発見したり、新たな言語仕様を提案して取り込んでもらうのはハードルが高いので、 Goのレポジトリのissuesから自分でも直せそうなバグを見つけてみることにしました。
Issues · golang/go · GitHub

このとき、 help wantedNeedsFixというタグのついたissueから探すようにすると、解決方針が比較的自明なissueを見つけることができます。

僕は↓のissueに取り組むことにしました。
github.com

バグを直す

Goのレポジトリをcloneするなりにして、手元でコードを読みつつ、バグを直します。
このとき、issueのタイトルに x/... と記載されている場合、Go本体のレポジトリではなく、サブレポジトリにコードが置かれています。
僕が扱っていたissueは x/website と記載されていて、 https://github.com/golang/website にコードが置かれていました。

手元で環境を構築し、バグを再現することができたら、あとは直します。
今回のバグfixの差分は これ だけでした。
差分が小さいのでめっちゃ簡単な修正だったかというとそうでもなくて、この差分で問題ないか確認するために周辺のコードをそこそこ読み込む必要があるので、時間はそれなりにかかった記憶があります。

パッチを送る

手元でバグの修正が確認できたら、パッチを送って、レビューをしてもらいます。
アカウントの登録やレビューツールが必要になるので、 Contribution Guide - The Go Programming Language を読みつつ、用意します。
今回はサブレポジトリへのコントリビュートでしたが、cloneするレポジトリが異なる以外は、通常のフローと同じで問題ありませんでした。
パッチを送るには、GithubもしくはGerritを使う必要があります。今回はせっかくなので普段使わないGerritを使ってパッチを送ってみましたが、特に詰まることなくスムーズにレビューに出すことができました。

https://go-review.googlesource.com/c/website/+/187897

パッチを送ると、 botから「Congratulations on opening your first change. Thank you for your contribution!」というコメントがついて、ちょっといい気分になります。

Goのプロジェクトはsix-month development cycleを採用しており、7月はDevelopment Freezeの期間だったのでマージされるのはもう少し先になるかと思いきや、レビューに出した翌日にはレビュワーにOKを貰い、パッチを取り込んでもらいました。

後日談

Goのレポジトリには CONTRIBUTORS というファイルがあり、コントリビュートした方の名前が掲載されています。
今回直したバグはサブレポジトリの小さいバグだったので名前が載ることはないかなと思っていましたが、2ヶ月後くらいの更新のタイミングでCONTRIBUTORSに自分のアカウントが掲載されました。

プログラミング言語へのコントリビュートはものすごく高いハードルがあると思っていましたが、思っていたよりも簡単にコントリビュートできました。
この体験談がGoにコントリビュートしてみたいけれど手が出ないと思っている方の参考になれば幸いです。

CLionの競技プログラミング用プラグイン「JHelper」の紹介

最近、競技プログラミング界隈でCLionユーザーが増えてきている気配を感じたので、CLionのJHelperという競技プログラミングに特化したプラグインを紹介しようと思います。
plugins.jetbrains.com

JHelperは、
・サンプルケースの取得
・取得したケースに対するテストの実行
といった競技プログラミングをする際の典型作業をCLion上でいい感じに自動化してくれます。

使用例

1. 問題ページを開いて拡張機能のボタンをポチっと押す

f:id:tatsumack:20190718154549p:plain

2. CLion上で問題のConfigurationの作成&cppファイルの作成が自動で行われる

f:id:tatsumack:20190718160105p:plain

3. Runするとサンプルケースのテストを実行することができる(もちろんデバック実行もできる)

f:id:tatsumack:20190718160143p:plain

上記の使用例はAtCoderですが、Codeforcesなど主要なコンテストはだいたい対応しています。
対応コンテスト一覧

その他の機能

Configurationの自動切り替え
CLion上で開くファイルを切り替えるとConfigurationも自動で切り替わります。
複数の問題を解いているときに、Configurationを切り替え忘れていて別のファイルを実行してしまった、というありがちなミスを回避することができます。

コンテストごと丸っとダウンロード
コンテストページ上で拡張機能ボタンを押すと、そのコンテストに含まれる問題すべてをパースしてくれます。

自作テストの追加
もちろん自身が定義したテストケースを追加できます。

自作ライブラリの埋め込み
わざわざコピペしなくても、自作ライブラリをソースコードに埋め込んでくれます。
(私自身あんまり使っていない機能なので使い勝手はよく分からない)

他にもいろいろな機能があるので、興味がある方は JHelperのWiki を見てみてください。

インストール方法

1. JHelperプラグインをインストール
JHelper - Plugins | JetBrains

2. ブラウザの拡張機能をインストール
Chrome
Firefox

3. ToolBarにJHelperのアクションを追加
Preferences > Appearance & Behavior > Menus and Toolbars > Main Toolbar
を開いた状態で +ボタンを押して、
Add Action > Plug-ins > JHelper
で表示されたアクションをすべて追加します。
f:id:tatsumack:20190720002850p:plain

↓のようにツールバーにJHelperのアクションが追加されます。
f:id:tatsumack:20190723111119p:plain

4. サンプルプロジェクトのダウンロード
GitHub - AlexeyDmitriev/jhelper-example-project: Example project for JHelper
git cloneするなりして、上記のサンプルプロジェクトをダウンロードしてください。

簡単にディレクトリ構成を説明すると、
library/ ... 自作ライブラリを置くディレクト
tasks/ ... 問題ごとのcppファイルが追加されるディレクト
testrunnner/ ... テスト実行用のファイルが生成されるディレクト
output/ ... 提出用のファイルが生成されるディレクト
となっています。

tasks/配下の問題ファイルにコードを書き、Runすることで testrunner/配下にテスト実行用ファイル、output/配下に提出用ファイルが生成される、という仕組みになっています。
ディレクトリ構成はJHelperの設定から変更することも可能です。

5. お好みでテンプレートを修正
task.template ... 問題ごとのcppファイルのテンプレートです。私はよく使うマクロを定義しています。
jhelper-projects/task.template at master · tatsumack/jhelper-projects · GitHub

testrunner.template ... テスト実行ファイルのテンプレートです。私は出力結果に色をつけたりしています。
jhelper-projects/run.template at master · tatsumack/jhelper-projects · GitHub

submisiion.template ... 提出用ファイルのテンプレートです。私は特にいじってません。

6. 実際に使ってみる
上記で作ったプロジェクトをCLionで開いて、AtCoderCodeforcesの問題ページを開いた状態でブラウザの拡張機能のボタンを押してみてください。
CLion上にConfigurationが生成されて、問題のファイルが生成されます。

ファイルには↓のようにclassとsolveメソッドが定義されています。
f:id:tatsumack:20190723105347p:plain
solveメソッドにコードを書いていきます。
入出力はsolveメソッドの引数で渡されたものを使う必要があるので注意してください。

実装ができたら、f:id:tatsumack:20190723105636p:plain ボタンを押してテストケースを実行します。
問題なければ、output/配下に生成されたmain.cppファイルを提出します。

ここまで問題なくできれば、設定完了です。

あとは簡単にツールバーの各アクションの説明をすると、

f:id:tatsumack:20190723103109p:plain … Configurationの削除を行う
f:id:tatsumack:20190723103123p:plain … テストケースの編集を行う
f:id:tatsumack:20190723103125p:plain … Configurationの追加を行う(ブラウザの拡張機能から追加できるのであんまり使わない)
f:id:tatsumack:20190723110455p:plain ... JHelperの設定を変更する。生成ファイルの出力先を変更できたり。
f:id:tatsumack:20190723103128p:plain … 提出用のファイルをクリップボードにコピーする。
f:id:tatsumack:20190723103130p:plain … コンテストごと丸っとパースする(AtCoderは未対応。ブラウザの拡張機能から実行できるのであんまり使わない)
といった感じになっています。

まとめ

JHelperはいいぞ。

ちなみにCLion自体は有料の製品です。(学生は無料)
サムライズムというJetBrainsの公式代理店で購入する場合、↓の紹介リンク経由で購入すると少し安く買えるので良かったらぜひ。
JetBrains製品 紹介リンク

2018年に読んだ技術書たち

年の瀬ということで、日々の往復2時間の通勤時間を活かして読んできた技術書たちを備忘録としてまとめておく。

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

購入したのは2014年くらいだったと思うけど、途中で挫折して積んでいた本。
今年競技プログラミングを始めたこともあり、また気合入れ直して読んでみた。
読むには読んだけど、理解できていないところも結構ある。

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

CTF出てみたいなーと思って買った本。CTFビギナーが雰囲気を掴む上でとても参考になった。
ということで、今年は夏にあった初心者向けのCTFにも参加してみた。


http://blog.hatena.ne.jp/tatsumack/tatsumack.hatenablog.com/edit#preview

プログラミングC# 第6版

プログラミングC# 第6版

プログラミングC# 第6版

C#を書くことになったので、とりあえず体系立てて学びたいと思って買った本。
リファレンスとしてたまに読み返したりしている。

Unityゲーム プログラミング・バイブル

Unityゲーム プログラミング・バイブル

Unityゲーム プログラミング・バイブル

Unityの実践的な知見がまとまってる書籍ってあまりないので、発売前から気になっていた本。たしかUniteかCEDECの物販で買ったと思う。
各章独立しているので、気になるところをつまみ食いする感じで読んだ。

ふつうのLinuxプログラミング

最後の章のhttpサーバーを作るところが面白かった。
これを参考にしつつ、自分でも簡単なhttpサーバーを書いてみた。
github.com

[試して理解] Linuxのしくみ

[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識

[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識

Twitterで話題になっていたので読んでみた。
説明が丁寧なのと図も分かりやすく、エンジニア初心者の方にも読みやすいと思う。
社会人1年目くらいにこの本が欲しかった。

詳解UNIXプログラミング

詳解UNIXプログラミング 第3版

詳解UNIXプログラミング 第3版

[試して理解] Linuxのしくみを読んだあとに、Unixに関して体系立った深い知識を得たいなと思って読んだ本。
900ページ超あり、読み終わるのに3ヶ月くらいかかった気がする。

プログラミング言語Go

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)

Goを書くことになったので買った。
練習問題を全部解くかーと思ったけど、結構問題数が多くて途中で飽きてしまった。
github.com

とりあえず全体をサラーッと読んで、Goを書いていて気になることがあれば読み返したりしている。

みんなのGo言語

みんなのGo言語【現場で使える実践テクニック】

みんなのGo言語【現場で使える実践テクニック】

Goを書く上での実践的な知見を知りたくて買った。
Goプロジェクトのディレクトリ構成とか、マルチプラットフォームのツールを作る上で気にすべきこと、テストの書き方あたりが参考になった。

やってみようGoでISUCONパフォーマンスチューニングーISUCON7の予想問題を試してみる本ー

booth.pm

技術書典5に行けなかったのが悔しくて、後日電子版を買い漁ったときの本。
ConoHaでisucon環境がサクッと生成できること、pprof, alpあたりの使い方を知れたのが良かった。
今年は社内ISUCONに参加して非常に楽しかったので、来年はぜひ本家のISUCONにも参加してみたい。

Ryzen SEGV Battle

https://www.dlmarket.jp/products/detail/619213

これも技術書典5の電子書籍を買い漁っていたときの本。
このレイヤのバグを検証するのはめちゃめちゃ大変そうで読み応えがあり、かなり面白かった。

DNSをはじめよう ~基礎からトラブルシューティングまで~

mochikoastech.booth.pm

この本も電子版を買い漁っていたときに見つけた本。
そういえばDNSってちゃんと知らなかったし、説明が分かりやすかったのでとても良かった。

コンパイラ: 作りながら学ぶ

コンパイラ: 作りながら学ぶ

コンパイラ: 作りながら学ぶ

Turing Complete FM を聞いたりしていて、僕もCコンパイラ書いてみたいなと思って、買ってみた本。
思ったよりもとっつきやすくて、初学者でも読みやすかった。
で、これを読んでCコンパイラを書こうと思ったけど、競技プログラミングにハマったこともあり、四則演算を書いたくらいで頓挫している。。

低レイヤを知りたい人のための Cコンパイラ作成入門

低レイヤを知りたい人のための Cコンパイラ作成入門

Turing Complete FMのRui Ueyamaさんが書かれているCコンパイラ作成入門本。
まだ執筆途中だけど、読みやすくて僕でもセルフホストCコンパイラがかけそうなので、完成版が本当に待ち遠しい。

Go言語でつくるインタプリタ

Go言語でつくるインタプリタ

Go言語でつくるインタプリタ

Goの勉強しつつ、インタプリタもかけるなんて最高じゃんと思って買った本。
Goに関しての言及はあまりなかったけど、簡単なものであればインタプリタって意外と作れるもんだなと思えた。
github.com

自分で構文を追加してみたりもした。
qiita.com

同じ作者によるコンパイラ本も買ったので、早く読みたい。

Writing A Compiler In Go (English Edition)

Writing A Compiler In Go (English Edition)

マスタリングTCP/IP 入門編

マスタリングTCP/IP 入門編 第5版

マスタリングTCP/IP 入門編 第5版

そういえば、体系立ててネットワーク周りの勉強をしたことがないなと思って買った本。
淡々とプロトコルの仕様を説明するのではなく、どういう経緯で今の仕様になっているのかをきちんと説明している点が良かった。

実践パケット解析

実践 パケット解析 第3版 ―Wiresharkを使ったトラブルシューティング

実践 パケット解析 第3版 ―Wiresharkを使ったトラブルシューティング

Wiresharkを使いながら、パケット解析を実践してみる本。
深い知識を得られるかと思いきや、結構浅い感じだった。ネットワーク入門本としてはアリだと思う。

エンジニアのためのマネジメントキャリアパス

エンジニアのためのマネジメントキャリアパス ―テックリードからCTOまでマネジメントスキル向上ガイド

エンジニアのためのマネジメントキャリアパス ―テックリードからCTOまでマネジメントスキル向上ガイド

今はマネジメントから離れているが、またマネジメントとしてのキャリアを考えることもあると思い買ってみた本。
まだ自分にはピンと来ない部分もあったので、マネジメントに軸足を置く機会があれば、また読み直したい。

エンジニアリング組織論への招待

個人的には2018年に読んだ本の中で一番良かった。
特にこの一年は新規開発をしていたこともあり、不確実性を減らす動き方ができているか自問自答していた。
一見エンジニア向けっぽい本に見えるが、企画職やプロダクトマネージャーにもオススメ。

ドラゴンクエストXを支える技術

長期運営かつ複数プラットフォームを対応する上で、意外と泥臭い問題解決をしている点があるところも包み隠さず書かれていた点が良かった。
コラムも面白くて「TCPチェックサムは合っているけど、データが壊れていることがあった」とかそんなことあるのかーという感じ。

まとめ

来年も気の赴くままに技術書を読み漁っていきたい。

AtCoderの拡張機能を3つ作った話

これは AtCoder関連サービス Advent Calendar 2018 - Adventar の9日目の記事です。
今年の3月くらいから競技プログラミングにハマり初め、精進していく過程で、AtCoder拡張機能が3つ生まれたので紹介します。


AtCoder-ACer


これは、AtCoderの問題一覧ページにコンテスト中にACした人数を表示する拡張機能です。
AtCoder-ACer【Chrome拡張】

なぜ作ったの?

たまに配点の高い問題の方が多く解かれていることがあり、Codeforcesのように問題一覧ページに現在ACしている人数が表示されていると、コンテスト中の立ち回りを判断する上で役立つだろうなーと思って作りました。

作った後に、順位表の最下部に同じような情報が出ていたことに気付いたのですが、どうせ作ったのだからということで、公開しました。
ありがたいことに、40人くらいの方に使っていただけているので、公開して良かったですね。

どうやって作ったの?

AtCoderのjsのコードを眺めていると、https://beta.atcoder.jp/contests/[コンテスト名]/standings/json というAPIでコンテスト情報のjsonが取得できることが分かったので、問題一覧ページでこのAPIにリクエストを投げて、返ってきたjsonをパースして表示しています。
(ちなみに、ちょっと実装をサボっていて、部分点もAC扱いにしちゃっています。)


AtCoder-Video


これは、AtCoderのコンテストページに解説放送へのリンクを追加する拡張機能です。
AtCoder-Video【Chrome拡張】
AtCoder-Video【UserScript】

なぜ作ったの?

YouTubeで解説放送を探すのが面倒だったので作りました。

どうやって作ったの?

YouTube APIを使って、AtCoderチャンネルの動画の一覧を取得しています。YouTube APIを使うために必要なAPI keyはクライアントに置くことはできないので、サーバーを用意する必要がありました。
が、真面目にサーバー管理するのが面倒だったので、今回はGoogle Apps Scriptを使用しました。サーバーレスな感じで開発することができ、今回のような用途では非常に便利でした。

Cronのように定時実行することもできるので、10分毎にYouTube APIを叩き、取得した動画情報をスプレッドシートに保存しています。

あとは、このシートからデータを取得しjsonとしてレスポンスを返すAPIを用意して、拡張スクリプト側からはそのAPIを叩いています。
Google Apps Scriptは無制限に呼び出せるわけではないので、クライアント側では一度取得した結果をlocalStorageに一定期間保存するような実装にして、APIを呼ぶ回数を抑えるようにしています。

ちなみに、YouTubeの放送タイトル名にtypoがあったりすると、うまく動きません。

あと、現状、企業コンには未対応です。
今後、企業コンが増えてきそうな流れなので、ぼちぼち企業コンにも対応しないとなーという気持ちはあります。

[2019/05/17追記]
AtCoder本家のサイトに解説放送へのリンクが追加されるようになったので、AtCoder-Videoは削除しました。


AtCoder-TestCase-Extention

f:id:tatsumack:20181208232400p:plain
これは、AtCoderのテストケースへのリンクを追加する拡張機能です。
個人的には一番気に入っている拡張機能で、今回作った3つの拡張機能の中でも一番利用者が多いです。(160人くらい)
AtCoder-TestCase-Extention【Chrome拡張】
AtCoder-TestCase-Extention【UserScript】

なぜ作ったの?

AtCoderはテストケースを一部Dropboxに公開しているのですが、Dropbox上で探すのが面倒だったので作りました。
また、ABCとARCが同時開催された回は、ABCのテストケースがARCのディレクトリ配下にまとめて格納されているので、ABCがどのARCに対応するのか調べる必要がある、という点も面倒でした。

どうやって作ったの?

開発当初はサクッと作れると思っていたのですが、なかなか骨が折れました。。

各テストケースへのURLを取得する必要があり、DropboxAPIからサクッと取得できると楽だったのですが、ドキュメントを調べた限りそれは難しいようでした。
そのため、Dropboxのページをスクレイピングする必要がありましたが、DropboxのページはJavaScriptで動的に生成されているページだったので、単純にレスポンスをパースするだけではうまくいきません。

そこで、PhantomJs Cloudを利用しました。スクレイピングしたいURLをパラメータとしてPhantomJs CloudのAPIを叩くと、JavaScriptで動的に生成した後の結果を返してくれます。
公開されている全てのコンテストの情報をスクレイピングしようと思うと、無料枠だと3ヶ月ほどかかる計算だったのには頭を抱えましたが、諦めて課金しました。

また、AtCoderのテストケース名から公開されているファイル名を判定する必要があるのですが、コンテスト毎に規則が異なっていたことにも困りました。
当初、テストケース名にファイル拡張子がついていない場合は、.in / .out 拡張子で保存されていると決め打って実装していたのですが、いくつか例外があったことが後ほど発覚しました。

あと、この拡張機能もサーバーサイドはGoogle Apps Scriptを使用しています。
サーバーを用意せずにやりたいことに集中できるのは楽ですね。

こちらも現時点では企業コンは未対応です。


AtCoder Beginner Contest 102 振り返り

3回連続で400点問題を落として水色チャレンジに失敗していたので、今回は久々の4完でホッとした。

初めて600点問題でACできたので、解説記事でも書こうかと思ったけど、他の方の非常に分かりやすい記事があったのと、他の人の思考過程を知りたいと思うことがよくあるので、今回は自分が解答に至るまでの思考過程を記してみようと思う。

今回のABCの配点は100-200-300-600で、明らかにC速解き勝負だったので、なるべく早く解くことを意識した。

A - Multiple of 2 and N

パッと問題文を読んだときは2*Nを出力すれば良さそうだと思ったけど、サンプルを見て、Nが2で割り切れるときはNを出力すれば良いことに気づく。
Submission #2765392 - AtCoder Beginner Contest 102

B - Maximum Difference

問題文を読んだ時点で、配列要素の最大値と最小値の差を引く、という方針が浮かんだので、そのまま実装する。
Submission #2765973 - AtCoder Beginner Contest 102

C - Linear Approximation

問題文を読んだ時点では、方針が全く浮かんでこなかったので、「C速解き失敗」が脳裏をよぎる。

落ち着いて、問題を簡単に考えることはできないかと、式を眺める。
 A_i - (b+i) は、 B_i = A_i - i とすると  B_i - b として考えることができることに気付く。
よって、配列内の各要素からの距離の総和が最小となるような bを考えれば良くなり、少し単純になる。
まあそれでもまだ分からない。

簡単に考えるために、要素数が2のケースで考えてみる。すると、 bは2要素の間にあれば良いことに気付く。
次に、要素数が3のときを考えてみる。このとき、真ん中の要素と bが一致すれば良いことが分かる。

ということで、 bは配列の要素の中央値を選べば良さそう、という気配が濃厚になったので、実装してみる。
サンプルがすべて通ったので、ちょっと不安はありつつも、提出してみる。

ジャッジサーバーが詰まっていたのか、なかなかジャッジが走らなくてそわそわしたが、無事ACが出たので、一安心。
Submission #2767475 - AtCoder Beginner Contest 102

目標がC速解きだったのと、Dの600点問題は解けるわけないと思っていたので、ちょっと集中力を切らしてtwitterを眺めたりする。

D - Equal Cut

この時点で順位表を見ると、1位だったのでびっくりした。(スクショ取っておけば良かった)
Dも頑張って解いてみるかと思い直し、問題文を読み始める。

部分和を求める必要があるので累積和を使いそうだなーとは思ったが、方針は全く浮かんでこない。

簡単に考えるために、切り口を1つだとして考えてみる。
このときは、配列内のすべての切り口の位置を調べれば、 O(N)で簡単に切り口の位置を求めることができる。

ということで、「切り口1つの位置を考えれば良い」という状況にどうにかして落とし込めれば、この問題は解けそうだと思い始める。

ここで、切り口3つのうち真ん中の切り口を固定すると、左右の切り口の位置は切り口1つの問題に落とし込めることに気付く。「3つあるうち真ん中を固定すると、残りが決まる」というのはよくある形だったこともあり、気付くことができた。

無事にサンプルが通ったので提出するも、TLE。
Submission #2771181 - AtCoder Beginner Contest 102

計算量を落とせる場所がないか考えてみる。
真ん中の切り口の位置を更新するたびに、左右の切り口の位置を全探索して調べるのは無駄なことに気付く。

よくよく考えると、左右の切り口の位置は右にずれていくだけなので、真ん中の切り口を移動する際に、前回の左右の切り口の位置を覚えておいて、そこから計算すれば良さそう。(尺取法的なアプローチ)
Submission #2771925 - AtCoder Beginner Contest 102

サンプルが通ることを確認して、提出して、祈る。。
AC!初めて600点問題を通すことができた。

Dの提出直後は3位だったが、1WAだったこともあり、最終的な順位は4位だった。


振り返り

C問題もD問題も、パッと見よく分からないので、問題を簡単にして考えてみる、というアプローチが上手くいった。直近のコンテストで400点問題が解けないときは難しく考えすぎていたので、その反省が活かせたと思う。

次こそ水色!

はりぼてOSをNASM・GCCで動かす(Mac OSX)

「30日でできる!OS自作入門」を読んだ。

30日でできる! OS自作入門

30日でできる! OS自作入門

この本で開発する「HariboteOS」は作者の独自ツールを使って動かしているが、GNUのツール群で置き換えてビルドできるようにしてみた。

環境

Mac OSX El Capitan(10.11.2)

NASM(Netwide Assembler)に置き換える

作者独自ツールのNASKをNASMに置き換える。
主要なアセンブラとして、NASMの他にGAS(GNU Assembler)が挙げられるが、GASの構文はNASKと大きく異なるので、NASMで置き換えることにした。
参考: Linux のアセンブラー: GAS と NASM を比較する

下記のページに記載のある通り、置き換えをすればアセンブラできるようになる。
http://hrb.osask.jp/wiki/?tools/nask

対応コミット
Replace nask with nasm · tatsumack/HikariOS@877ec9d · GitHub

GCC

C言語で実装されたファイルも作者の独自ツールを使ってコンパイルされていたので、GCCに置き換えてみた。

GCCのビルド

hrb形式のファイルを作成するためには、リンカスクリプトを作成しリンカに渡す必要があるが、
Mac OSXのデフォルトのリンカ(ld)はリンカスクリプトを受け付けるオプションがないので、クロスコンパイラなGCCをビルドする必要がある。
ビルド手順についてはQiitaにまとめた。
qiita.com

その他にやったことの箇条書き

・nasmの出力形式をwin32からelfに変更
・.hrb形式のリンカスクリプト作成
・naskfunc.nasの関数のシンボル名のprefixの_を削除
・色々とライブラリがないので、自作OS本付属のomake/tolsrc/go_0023s/golibcから静的ライブラリを作成し、リンクする
・__builtin_stdarg_startを__builtin_va_startにrename

対応コミット
Replace gocc with gcc · tatsumack/HikariOS@ab4b5d4 · GitHub