isucon13 参加記（25000点くらい）
isucon13 に参加しました 忘れないうちに備忘的な記録を残そうと思います
zenn か何かに書こうかと思ったけど、そんなに有用な話でも無いので久しぶりにここに書きました
TL;DR
- isucon本読んでモチベが上がったので出てみる、なんやかんやあって結局一人参加
- 最終ベンチが 25000 くらい、再起動試験に通ったかは知らない
- やったのはほぼアプリ + DB改善のみ、サーバー一台構成のままだし dns は何もしてない（できなかった）
- 最後に EC2 落としてから git に commit はしてたけど push してなかったことに気づいたのでソースコードが残っていません、悲しいね
やったこと
免責：ソースコードと commit log を紛失したのでやったことと得点は大体の記憶です、100%一致してないと思います fgprof のスクショがちょこちょこ残っていたのでこれをメインに書きます
最初
- とりあえず fgprof と slow query log を入れます
- nginx, alp 周りは面倒だったのでいっか〜ってなって結局最後まで入れませんでした (fgprof で何となく分かるしね（ほんまか？
getLivestreamStatisticsHandler 周りの N+1 改善, index 貼り
（これ今他のと見比べたらちゃんとログ取れてるかだいぶ怪しくないか？）
まあこれを見て getLivestreamStatisticsHandler が明らかに死んでいると判断したので、コードを見るとどう見ても N+1 で ranking を取得しているのでとりあえずこれを潰します
ついでに user の方もどう見てもN+1だったので潰します
業務で鍛えたSQL力😤
あとは slow-query log を見ながら userId とか livestreamId 周りとかに INDEX を貼ってだいたい 10,000点超えるくらい
fillLivestreamResponse 周りの N+1 改善, index 貼り
統計を潰すとこのへんにボトルネックが移ってそう、 fillLivestreamResponse が怪しそう
よく見るとここもやっぱり N+1 になっている (同一の Livestream の comment を取得したあとに comment ごとに Livestream を取得し直している) ので潰します
これで 16,000~17,000 くらいまで行った気がします。この時 20 位くらいに一瞬入ってて嬉しかった（こなみ）（isucon はベンチ fail した時に 0 点になるので途中順位は全く意味ないんですが）
icon 周りのキャッシュ
sha256.Sum() とかにボトルネックが移ってるな〜という気持ちになります。レギュレーション読んだけどこれが何に使われているかは結局よく分からなかったです、とにかく計算が遅いらしい。
なんとなく user 数はそこまで増えないっぽかったので (これは嘘で高速化していくと最終的にはちゃんと user regist も飛んでくるらしいという話？だがそこまで行ってない） go なので mercari_go_isucon.md · GitHubを参考にさせて頂き雑にインメモリキャッシュをします。 ついでに icon の画像取得も DB だと IO が重そうなのでインメモリキャッシュをしてしまいます。（nginx から静的ファイル配信すればいいんですが、なんかうまく行かないな〜となりました）
これで 21,000 ~ 22,000 点とか
最後
このへんまで来るとアプリケーション側で目に見えるボトルネックはパッと見なさそうになったので、 ベンチ実行時にタイムアウトと言われてた API を見てみて細々とした改善を入れます
- ngWord の登録時のコメント削除周りにあった N+1 っぽいのが潰す
- ngWord 判定をなんか DB でやってるのをアプリケーション側に
- user 取得時のもろもろのクエリを一本化
- reserveLivestream で不要なクエリを削除
など、最終的にログを全部オフにして 25,000 点くらいで終了
反省 & 感想
- 昔出た時はまじで自分は手も足も出なかったが、Isucon本読んだおかげで簡単そうな部分は順当に改善進められて良かった
- 特に計測 -> 改善のサイクルを回すことを意識したおかげでちゃんと正の進捗を生めた、昔は勘でやっていたので改善が効いたり効かなかったりの運ゲーをしていたので
- DNS なに？
- powerdns の thread とか増やすと 水責めレベルが上がり、DNS解決数は増えるがスコアが落ちて何？ってなってた
- subdomain が random で cahce hit しないし、出処も同じ？っぽいので正しい対処方法がよく分からなかった
- サーバー複数台構成はちゃんと練習しておけ（完全に忘れており、今からやっても間に合わんかとなりました）
- GitHub に push しておけ
Python(とPyPy)でAtCoder黄色になりました
この度第二回全国統一プログラミング王決定戦予選で黄色になりました！！！！！！わーい！！
最高パフォ&はいえすと＆黄色＆予選通過確定です！！！！！！！！！！！！！！！！！！ありがとうございます！！ pic.twitter.com/z10Yd5js5X
— しまむむ (@simamumu) 2019年11月9日
のでいわゆる変色記事とか言うやつを書いてみたいと思います
別にこういう勉強法が良いよ！とかこういうことするとレートが上がるよ！みたいな有益な話はそんなないと思います
わりと日記な感じなのでごめんなさい
お前は誰
- 東京の工業な大学のの†土木工学系†に所属している B4です
- 土木についてあまりイメージがわかない人は講義でFORTRANをやらされる学部だと思っておけばよいです
- 土木についてあまりイメージがわかない人は講義でFORTRANをやらされる学部だと思っておけばよいです
- プ歴(≒競プロ歴)は2年くらい
- 一応数学も書いておくと高校数学は得意な方でした(特に整数論のパズルみたいな問題が好き)．大学数学は多分苦手です
- これは人生で唯一できる自慢なのですが数学280/300で合計点では学部内首席でした (くっそまぐれ当たりなので入学後の成績は…
- でも受験数学の範囲は出てなくて数オリとかそういうのは全く触れたことないです
最近の Rated 戦績
令和ABC以降の～700 の (AC提出時間-直前の問題のAC提出時間) でなんとなくなかけた時間表です
こうしてみてみると結構成長が感じられて面白い
400,500 がそこそこの速度で解ける = 600にちゃんと時間をかけて解けるようになった気がします．
定期的に 300 で破滅してるの面白い (JSC決勝もここには書いてないけど300で死んでいたため
持ってるライブラリ
これも良くみるので書いておく
グラフ
- Dijkstra
- WarshallFloyd
- Kruskal
- FordFullkerson (Dinic の理解を諦めたため
- BellmanFord
- トポソ
データ構造
- 数学
- 逆元Combination
- 篩
- なんか高速な素数判定
一応作るときに意識してるのは
- 完全理解して自分で1から書く(これは半分くらい本当だけど半分くらい嘘
- できるだけ早くしとく≒非再帰で書く
- 分かりやすく書く、classとか使って抽象化する
- 自分が 使いやすくする (strをオーバーロードしてデバッグ出力を簡単にするとか
黄色まで(≒ABC) にはこれくらいでそんなに困りませんでした(当然もっとあって悪いことはない
やったこと
やったこと…何やったっけ？
- こどふぉにはほぼほぼ出てない
- 睡眠は大切なので
- あと個人的にあんまり問題が好きじゃない (これは参加した回が少ないせいかもしれなです
- その代わり日本語コンテストには出る
- ほんまか?(割りと用事被って出てないような)
- ぶっちゃけ最近は"競プロの"精進はしてないです．problems がこんな感じなので…せいぜいコンテストと復習くらい
- でもコードを日常的に書く機会というのはかなり増えました
- 8月中旬くらいから某社でバイトを始めた
- 10月にインターンにってました
- 最近は卒論の研究で django を使って自分の卒研用の web アプリを作ったりとか
競プロ自体の精進はしてないのですが，最近の戦績 を見てみるとバイトを始めたあたりから結構成績良くなってて，
コードを書くようになったってのは結構影響してるのかなって思います．
特に私自身情報系の学科じゃないので競プロ以外でコードを書く機会が少なかったので．
ぶっちゃけなんで最近レートが上がったかってABCが6問体制になったからが一番大きい気がします
600前後くらいの問題が個人的には丁度良いと感じるのですが、旧体制だとそこを解けることにそんなに恩恵がないような配点が多かった感
コンテストで意識してること
っていうのを下書きの時点で章だけ作ってたんだけど書くことありますか？っていう気持ちになっています 一応なんとなく思い浮かんだことを書いておくと
- ABCの~500 はわりとパターン認識だと思ってる （それより上とAGCは知らない
- 似たような問題設定見たことあるなー，きっとこういう見方をすると嬉しいんだよなみたいな思考はわりとするし，わりと使える
- なので過去問梅は大事 (しかしそんなにやってない気がしますが
- 制約とサンプルからエスパーする
AtCoderをやってて良かったこと
ここが一番書きたかったところです
- 楽しい
- やっぱり競プロはネトゲなんですよね
- 解けなかった時の悔しさもあるけど，その分上手く解けた時の脳汁がドバドバなので
- プログラミングの楽しさを知れた
- これがほんとにめちゃくちゃでかい
- 競プロ楽しい！から一般的なプログラミングにはまった
- ので，そのきっかけになった AtCoder で人生変わったは過言じゃなくわりと事実
- 将来の進路にまで割と影響してきている (これは某土某通省のせいで土木に対する熱が冷めたのもだいぶある
- 情報分野のバイト/インターンに繋がった
- 交遊関係は広がらない
- コミュ症なので仕方ないですね
- 日経コン本選行くのでこの記事を読んでる奇特な人がいたら是非話しかけて下さいお願いします！
何でPythonを使うのですか
AtCoderをPythonを使ってる理由
— しまむむ (@simamumu) October 1, 2019
競プロでPythonを使うことによって生じる損失と他言語の学習コストを比べると，自分には他言語を学習するコストの方が圧倒的に高いため
単純にPythonが好きというのもだいぶある(むしろこれがすべてでは？
— しまむむ (@simamumu) October 1, 2019
まあ結局何で？って言われると好きだからなんですね
じゃあ何で好きかって言われると困っちゃうんですけど，まあ好きってそういうもんじゃないですか (ここJpopの歌詞っぽい
今後について
最初は青を目標にしてたのですが，いつの間にか黄色になってました． 橙なりたいと思わないわけではないのですが，橙より上は人外だと思ってます．人外になりたいですね？？
でもこれより上はいわゆる高度典型と言われるものを抑える必要があると思うのでちゃんと精進しなきゃなんですね． まあとりあえずはAGCでレート配ってABCで黄色復帰する人にならないようにまずは黄色キープを目標にしていきたい
それと maspy さんのブログを読んで思ったのですがやっぱり Python で競プロやってる勢が(特に上位では)少なく，Python 勢にとって上位問題の解答/解説が多くないっていうのはあると思います
自分でも割と上の方(国内黄色↑が10人くらい)らしいので，他の競プロ Python 勢に貢献できるように記事とか解法とか残していけたらいいですね (多分めちゃくちゃ苦手な分野ですけど頑張っていきたい
FIXSTARS のインターンに参加してきました
10/7 ～ 11/8 の計5週間(ゼミとかの兼ね合いで正味19日)でFIXSTARS さんのインターンに行ってきました．
ので忘れてしまわないうちにその参加記を書いてみようかなって思ったので書く．
読むのがめんどくさい人向けに最初に要約を書いておくと
- 楽しい
- 勉強になる
- お金が貰える
で大満足のインターンでした．本当に全学生競プロerに行って欲しい
これは何
- 自分の備忘録という部分が大きいです
- なのであまり技術的な話よりも感想とか主観多めの日記です（業務内容は言ったらまずそうなこともあるので
FIXSTARS のインターン参加記たくさんあるし別にいらなくないですかお世話になったしめっちゃ楽しかったので書きたかった
お前は誰
- 東京にある工業な大学の †環境社会理工学院 土木環境工学系† のB4
- 研究室は構造系(特に振動分野)で，微動を使って固有振動解析をして構造物の同定とかをしたりしてなかったりする
- 最近機械学習に足を突っ込み始めたらしい
- AtCoder のレートが 1970 (11/8 現在)
- 主に Pythonを書いていて， C(++) はまあググれる環境があれば Python の 5~INF倍くらいの時間を費やして書けなくもないくらい
行くまで
申し込んだ背景
- 某土某通省の本省(霞が関)を今年の春受けてたんですが，採用担当があまりにも嫌いすぎて無理だった
- 採用担当が嫌いだったので，まあその採用担当が選んだ人が集まるところって考えると無理だよねって
- これはどうでもいいけど国家総合職の選択科目の情報(ソフトウェア)は競プロ死ぬほど役に立つのでお勧め．
- で，まあ落ちたんですが土木に対する熱が完全に冷めてしまったので，競プロ楽しいし情報系もいいかなーと思って
- しかし自分にとってプログラミング≒競プロのため実務経験が皆無
- なのでどれくらい通用するか，逆にどういうところが足りないかっていうのを知りたくて，AtCoderJobs経由で応募しました
FIXSTARS を選んだ理由
- 結構競プロ界隈ではインターン参加記とか多くて元から知ってたし評判もよさげだなって思ってた
- 通年募集してた
- 時給が良い(前述した某省の試験勉強とか某人間コンテストとかで全然バイトしてなくて財政難だったので)
- 業務内容が結構競プロに近そうで楽しそう
面接
- 担当の方(インターンではメンターをしていただいた)が分野は違うけど土木出身でめちゃくちゃビビった
- そのためか，わりとちゃんと研究内容のことを話したし結構深掘りされた気がします．
- コーディング試験はまあ書いたら怒られそうなので割愛．
- 現職エンジニアの方に見られながら書くのは結構緊張します
- これは公開情報だった気がするので言っても大丈夫だと思うのですが，試験はC,C++ 限定なので普段書かない人は簡単な書き方くらいは勉強していこうね．
- 私は入出力できなくて3分くらい一人で？？？ってやってました
- まあなんやかんやで無事に通ってインターンに参加させていただくことに
- 某省の選考の後申し込んだので当然夏はもう締め切られてて，10月に行くことに．
業務内容
何個か提案を頂いて，その中から一番面白そうだったDSP向けのソースコードの高速化をやりました． ちなみにこれは実際のお客様のコードで，本当に実際の業務でやっていることに近いことをやらさせて頂きました．
SIMD
過去一分かりやすいSIMDの説明 pic.twitter.com/EsMlMvfMrm
— まんてら@技術系(V)Tuber (@manntera) October 31, 2019
これめちゃくちゃわかりやすくて感動したので載せさせて頂きます
DSP 向けということで結構特殊な環境下だったのですが，SIMD命令が使えたので主にSIMDを使うことで高速化をした．
で，これが普通に楽しかった．具体的には書けないのですが
- 今あるものと動作自体は変えずに SIMD で書き直す
- SIMD で使える命令は限られてるのでうまく使う必要がある
- でも結構特殊なのもあって 4つ単位で sum をとるとか，
(A*B+C*D+E)>>Fを一発でやるとか - こういうのをうまく組み合わせて，やりたいことを実現させる方法を考えるのが楽しかった．
- SIMD 命令は基本 256bit 単位で演算処理が行われる．
- つまり整数値でも可能な限り小さいサイズに抑えられると嬉しい
- なので
#define int long longじゃなくて型のサイズとかうまく小さい値で扱うように工夫したりとかする
まじで競プロみたいな(?)パズルって感じなのでやっててめっちゃ楽しかったです．
メモリ削減
これも面白かった．外部メモリへのアクセスコストが高いので，チップ内部の速いメモリから変数を確保したい．
けどその内部メモリがちっちゃいので無駄な変数を削除したり次元を減らしたりしようねという話で何個かやりました．
これも具体的には書けないけど
- 計算順序をうまく工夫して同時に持つ必要がないデータを削減する
- 適当なデータ構造を使って，計算領域に使うメモリを減らす
とかしてました．メモリの削減っていう視点はあまり持ったことが無かったので新鮮で楽しかったです．
報告会
最終日一日前にここまでやったことをまとめて発表するという機会がありました．
自分が学んだものを改めて見返してまとめるっていうのがわりと自分の身になったのと，
報告会は緩い感じかと思ったら結構人が多くてわりと技術的な質問が飛んできたりして辛かった勉強になりました．
(実際自分が今回やったことをまとめて，それに対して足りないこととか，改善できることとかを色んな人から指摘頂ける貴重な機会だったし色んな視点を学べたのでありがたかったです）
学んだこと
- 複数人での開発作業
- やらないのでね，複数人でやって初めてgit/gitlabがどれだけ偉大か理解しました
- コミュニケーションの取り方とか，作業内容だけじゃなくて目的自体もちゃんと意識するとか(まあこれは何に対しても言えると思うのですが)
- SIMD
- 高速化についての基本的な概念
- レイテンシとかパイプラインとかその辺全く知りませんでした
- 機械語に近い部分もちゃんと学びたいなって思った
- C言語
- これも今回初めてがっつり書いた．
- まずポインタを理解してなかったレベルだったので…完全理解とまではいかないけど結構慣れた
- 整数除算が0方向に丸められる(負数だと切り上げになる)の罠過ぎませんか
- わかりやすいコードの書き方
- 一過性が高い && 自分しか読まない みたいなコードし書かないので，普段全く意識しないけど大事
- 最初のコードレビューは酷いものでMRのコメントが3桁のるくらいまで行ってたけど，その分色々学べました．
感想
- 純粋に業務内容がめちゃくちゃ楽しかった．
- これはお世辞とかじゃなくて本当に純粋な感想
- 8時間/日を週4かーって最初思ってたのですが，やってて楽しいので全然時間の進みが早く感じる
- 最終日は19時退社を徹底してくださいって言われてたのに18:57くらいまでコード書いて push したりしてた．それくらい楽しい
今日インターン最終日だったんですが
— しまむむ (@simamumu) November 8, 2019
天才的な改善案を思い付いてしまって勢いで書ききって退勤5分前に一発で出力一致確認できてプッシュする
というコンテスト終了間際みたいなことをしていた
- 勉強になった
- 貴重な経験になった．
- 今進路にどの分野に進むかレベルで迷ってるので，IT分野の会社の実務に携われたっていう経験が有難いです．
- 当初の目的であった自分の実力で通用するのか，何が足りないのかっていうのもなんとなく掴めた気がしたので良かった
- 同時期のインターン生が全然いなかった．
- これをメリットと取るかデメリット取るか人に依るかもしれないけど
- 夏はmax3週間で，同時に2~30人くらい来るらしくてメンターの方も手が回らなかったりするので，こういう時期の方が手厚い待遇で長くできる．
- 実際4週目くらいから作業環境に慣れてきて，業務に専念できるようになってきた気がするので
- でもやっぱりインターン一人はちょっと寂しいかなとも思いました．
- まあ申し込んだ時期が遅くて長期休みからずれたせいなので私が100悪いですごめんなさい
あとがき
ということで，本当に大満足なインターンでした．
楽しくコード書いて，勉強にもなって，お金までもらってしまって良いんですか？ってなる．(貰えるものはありがたく貰う)
今回のインターンでお世話になった FIXSTARS さんと，そのきっかけになった AtCoder さんには本当に感謝しています．この場を借りてお礼をさせて頂きます．
本気でお勧めできるとこなので全学生競プロer に行って欲しい
あ，これはどうでもいいのですがインターン期間中に(直接の原因かはわからないけど)背中の筋肉(?)を痛めた． やっぱりデスクワークを仕事にするなら運動しなきゃなって思ったので最近リングなフィットのアドベンチャーを買いました．結構楽しいのでお勧めです．
python -> C++ 対応メモ
これはpython使ってると意識しないところとかではまってググったこととか備忘録用につらつら書き連ねる予定 c++何もわからないので間違ってるかもしれません．もし間違ってたら指摘してくれるととても嬉しい
入出力
少数出力(桁数指定)
何も書かずに出力すると6桁とかになるので精度ガバではじかれたりする
cout << fixed << setprecision(15);
これを最初に一回書くと以降の標準出力は全部指定した桁数(15)になる
宣言，初期化
二次元配列の宣言
例えばH*Wの二次元配列(初期値0)が欲しいとき
dp = [[0]*W for _ in range(H)]
int dp[H][W] = {}; // これはNG (arrayは変数でサイズを宣言できない) int dp[3003][3003] = {}; // これはOK(予めサイズが分かれば最大値+3くらいとかで宣言しとけばよい) vector<vector<int>> dp(H,vector<int>(W,0)); // vectorなら変数で宣言できる vector<vector<int>> dp; dp.assign(H, vector<int>(W, 0)); // assignで後から割り当てたほうがわかりやすそう
vectorで後から割り当てるのが一番使い勝手も可読性もありそうな気がする
便利なの
範囲for文
配列を直接回すやつ
for a in aa: print(a)
for(auto a: aa){ cout << a << endl; }
for x,y in xys:みたいのはできなそう
でっかい値
INF = float('INF')
#include <climits> INF = INT_MAX \\ int の最大値 LLINF = LLONG_MAX \\long long int の最大値
ABC109参加記
AtCoder Beginner Contest 109 - AtCoder
コンテスト時間: 2018-09-08(土) 21:00 ~ 2018-09-08(土) 22:40
20:30で全完0WA全体39位でした．unRatedだけど全体順位は今までで一番良かった．
A - ABC333
かけたら奇数になるのは奇数×奇数だけなので，A*Bが奇数かどうかだけ見ればよい
A,B = map(int,input().split()) if (A*B)%2 == 0: print('No') else: print('Yes')
B - Shiritori
しりとりをします．
同じ単語が含まれているかどうかはset()で持って配列長が変化するかどうか見ればよい(これ昨日のyukicoderで同じことした)
pythonなら文字列や配列の末尾はS[-1]で指定できる
import sys N = int(input()) ww = [input() for i in range(N)] if len(set(ww)) != N: print('No') else: for i in range(N-1): a = ww[i] b = ww[i+1] if a[-1] != b[0]: print('No') sys.exit() print('Yes')
C - Skip
何をすればいいかは見ればわかったけど改めてなんでって言われると難しい…
全ての都市と出発点をx座標でソートした時隣り合う都市間の距離がDで割り切れれば全ての都市に行けるので，隣接二点間の距離全体の最大公約数を求めればよい．
最大公約数はユークリッドの互除法を使えば十分高速に求まる
N,X = map(int, input().split()) xx = sorted(list(map(int, input().split())) + [X]) dists = set() for i in range(N): dists.add(xx[i+1]-xx[i]) dists = sorted(list(dists)) def gcd(a,b): while b: a,b = b, a%b return a ans = dists[0] for d in dists: ans = gcd(ans,d) print(ans)
D - Make Them Even
こういう問題すき
奇数マスを2つずつになるように上手くペアを選んでそれぞれ結んであげれば，
その結んだ線上の経路をたどって一枚のコインを一方からもう一方に動かせばよい．
問題は同じマスを2回選べないのでこの経路が被ってはいけない．
ではどうするかというと，一筆書きとなるようにマス全体を辿っていき，辿っていく中で隣接する二つの奇数マスの間でコインを動かせば経路が被らない．
コインを動かすという動作をコインを拾い，持ち歩き，落とす，と言い直して凄くざっくり書くと
if 奇数マスにいる: if コインを持っている: コインを落とす else: コインを拾う
として，コインを持って歩いたところがコインを動かすところとなる．
また，全マスなめるように一筆書きするのはS字に辿ればよい．
[0,N)ひっくり返した区間が欲しいときはrange(N-1,-1,-1)とかよりはreversed(range(N))の方が簡単だし，辺に足し引きしなくて済むので楽です
def inpl(): return list(map(int, input().split())) H,W = inpl() MAP = [inpl() for i in range(H)] flag = False #コインを持っているか ans = [] for y in range(H): if y%2 == 0: xx = range(W) else: xx = reversed(range(W)) for x in xx: if flag: ans.append([by,bx,y,x]) if MAP[y][x]%2 == 1: flag = not flag bx,by = x,y print(len(ans)) for a,zu,nya,n in ans: print(a+1,zu+1,nya+1,n+1)
最後の出力が一行に複数出力するタイプの奴，出力用の変数で遊びませんか?
問題文上は1indexなので出力する時は+1を忘れずつけましょう
手数の最小化という条件が付いたら一気に難しくなりそう
感想
unratedだったけどABConlyで全体39位はなかなか健闘したのではー？
情報系の学部じゃないのでソースコード書き慣れてないせいか，やっぱり手が止まるのは実装の方って感じがする．(精進して
D問題はとても好きですって感じでした
