2023-11-26

ISUCON13参加記

当日

チーム MONOS で参加

github.com

開始前

朝早すぎる、9:40 なんか間に合わなかったが、開始時刻には間に合った

11時まで

ベンチがうまく回らない。計測結果が出なかった。とりあえず規則熟読、サイトを触ってみて、コードを読み始めていた。

午前中

NG word

計測が出ていなかったので、NG word 職人をしていた。NG word の判定をアプリ側で行うようにしたり、必要のない実装を消したりした。

中盤戦

計測結果が出た。できるだけ上位のものに取り掛かる

予約機能

いらない Select を削除

fillUser の修正

これがやばかった。fill~という関数の依存関係がかなり密で、fillUser を呼んでいるところも多かった。全体の高速化は煩雑になるためあきらめ、特にボトルネックとなっていた、GET /api/livestream/:livestream_id/livecomment と GET /api/livestream/:livestream_id/reaction から、fillUser までの部分が早くなるように修正を行った。この呼び出され方では livestream_id は一意であることをドメイン知識として入れ込むイメージでの実装。ここで点数が倍の 3 万くらいまで伸び、瞬間 2 位になった。

終盤戦

search の修正

fill 関数のループ削除をしようとした。しかし、逆に点数が落ちた。noe くんの助言を受け、一部のみを適用したところ点数が少し上がった。

結果

最終結果としては 11 万点ほど、700 人中 13 位。これまで 3 回ほど出てきたが、ようやくまともに戦えるようになったなと思う一方、キャッシュ化、nginx、インフラ周りといった知識のない部分が多すぎるため、これから学んでいきたい。

その他

saza くんは、ansible 含むインフラ周り、分散+今回一番難しい DNS 改善に挑んでいた。私にはよくわからない部分をやってくれていたので、感謝。 noe くんは、icon 含むデータのキャッシュ化、SQL, アプリ改善に挑んでいた。割と近めな部分+私が怪しい部分をやってくれており、ISUCONらしいワイワイ感を感じていた。感謝。

2021-11-01

バックエンドアプリを AWS 上に乗せたい

AWS にアップロード

EC2 インスタンスの作成

最初なのでおすすめされた amazon linux にして、t2.micro にした。セキュリティは HTTP、HTTPS を任意、SSH を自分の IP のみとした。

Elastic IP を作成、グローバル IP を固定。1 つ目は無料っぽい。

SSH config をいじって ssh aws で通信できるようにした。

IAM ダッシュボードで MFA(多要素認証) すべきといわれたのでやる。連続する 2 つのコードは、30 秒前のコードと今のコード(更新前と後) の 2 つを入力する。

ec2 に Name=app1, Env=dev のタグをつける。 IAM ユーザー作成、アクセスキー作成、aws configure でアクセスキー、シークレットアクセスキー、リージョン設定。インラインポリシー追加より下記の JSON を追加。

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Effect": "Allow",
            "Action": [
                "ssm:PutParameter",
                "ssm:DeleteParameter",
                "ssm:GetParameterHistory",
                "ssm:GetParametersByPath",
                "ssm:GetParameters",
                "ssm:GetParameter",
                "ssm:DeleteParameters"
            ],
            "Resource": "arn:aws:ssm:(リージョン):(アカウント ID):parameter/app1/dev/*"
        }
    ]
}

これで ssh して aws ssm put-parameter などで Parameter Store が使えるようになった。

mysql インストールしようとしたら、glibc-2.28 の libc.so.6 がないと言われた、どうしようもなさそうなので、EC2 再構築、mariadb をインストールすることにした。 CURRENT_TIMESTAMP が使えない、バージョンが 5.5 のせい。【Amazon Linux 2】MariaDBを5.5から10.5にバージョンアップ｜IT石ログこれに沿ってアップデートすれば使えるようになった。

sudo vim /etc/environment で環境変数を設定。port が 1024 以下の時は sudo が必要。root ユーザーでも aws configure の設定する。

エラー: address already in use 、前に動かしたものが残っている。 ps ax | grep go からプロセスを見て、kill する。

gmail 送信でエラー(認証系)が出る。安全性低いアプリを許可していたが、これを機にやめてみる。二段階認証、アプリパスワード生成して解決。

以上により AWS に上げることができた。

nohup で常に起動ができる。

次は AWS VPC とか使ってみたい。

2021-10-30

タグ付けアプリについて

タグ付けする Web サイト(ブックマーク機能)を製作している。そのサイトのバックエンドを担当した。

GitHub - moririn2528/tagtagyeah: 文献にタグをつけ、検索する web アプリを作る

概要

何かしらの Web サイトを作りたいと思い、友人にどのようなサイトが欲しいか聞いたところ、タグ付けサイトが上がったため製作することとなった。このサイトのフロントエンドは別の友人が製作している。

基本的な機能は、ユーザー登録、ログインして、文献、URL にタグをつける、そして、タグを与えると、そのタグが付いた文献を表示する、というものである。

以下話すことがある部分について書く。

検索機能について

タグの検索機能を付けた。

最初は prefix が一致するものをすべて返す、という実装。

これだと 1 文字間違えると候補として出ない。また、真ん中の単語だけを覚えていたとしても検索できない。

これらの対処法として、2 グラムを用いた。また、検索単語、タグ名の 2 グラムで一致するものの数を類似度とし、類似度が大きいものから順に出力することにした。

用いた理由

文字の並びの情報をある程度保持している
検索単語とタグ名が同じの時、類似度は文字列の長さを n とすると n-1 になる。そして、類似度 n-1 のタグは、文字列が小さいとき文字列内で同じ文字が使われることは少ないので、多くの場合で検索単語と同じといえる。
編集距離 1 (1 文字削除、追加、置換) による類似度の減少は高々 2 であるので、類似度が高いものは検索単語に近いと示される
タグ名、検索文字列は数文字から十数文字と考えられる。よって、3 グラム以上にすると検索効率が落ちると思われる (例えば、検索単語 5 文字で真ん中の単語が違うとき検索結果は意味がなくなるため)

今回、データベースから検索するユーザーが登録したタグすべてを取ってきて、それぞれのタグに対し類似度を調べ、ソートしている。計算量は検索単語文字列長 m、タグ名の平均文字列長 n、タグ数 t とすると O(nmt)

タグ名をランダムなアルファベット 20 文字とし、10 万個のタグを登録した上で検索する。

検索結果

3 文字以上の連続部分文字列であれば、上位 3 つのうちに正しいタグが出る。また、5 文字の連続部分文字列の 3 文字目を置換して検索しても上位 3 つのうちに正しいタグが出る。

これらから、検索機能はうまくいっているといえる。

計算時間

検索文字列が 5 文字のとき、データベースからタグ名取得、上記アルゴリズム、それ以外の処理、それぞれの時間を計測し平均すると、0 ms, 365 ms, 1 ms になった。

高速化を行う。

検索文字列の 2 グラムを map に保存する、これで計算量は O(nt) となる。実際、時間を計測すると 110 ms になった。

タグ名の 2 グラムをテーブルに保存すると、アルゴリズムの計算時間はさらに小さくなるが、データの大きさが増える上、取ってくるときの時間がさらにかかる。データベースの無料枠が小さいのも相まって、この方法は取らないことにした。

ログイン機能について

ログイン機能を付けた。ID、パスワード、メールアドレスを登録すると、そのメールアドレスに認証メールが届く。その後、認証メールに記載されたリンクに行くと認証されて、ログインすることが可能となる。

ログインすると、一時的な ID を発行、その ID で他の関数を使うことが可能となる。

こういう機能を付けるのが初めてだったので、どういう構造にするべきかかなり悩んだ。JWT 認証とかも考えたが、結局使わなかった。

まとめ

これらによって、Go 言語、MySQL に慣れ、バックエンドに触れることができた。しかし、このアプリはまだ多くのユーザーに使われていない、同期処理などもしておらず、実際にたくさんの人に使われたらどうなるのかわからないという問題点がある。

2021-01-10

xor convolution

数列 A から数列 B を以下で生成

$b_k = \sum_{i \oplus j = k} a_i a_j$

( $\oplus$ は bitwise xor とする)

まず、数列 A を多項式

$f(x) = a_0 + a_1 x^1 + \dots + a_n x^n$

と表す。 $x^i \times x^j = x^{i \oplus j}$ となれば、FFT を用いて $O(n \log n)$ で計算可能。

ここで、 $bit(i,j)$ を $i$ の $j$ ビット目とし、

$x^i = \prod_j x_j^{bit(i,j)}$

とする。例を挙げると、 $x^3 = x_0^1 x_1^1$ 、 $x^5 = x_0^1 x_1^1 x_2^1$ となる。これは、xor がビットごとの計算である性質を表している。

次に、 $x_k^i \times x_k^j = x_k^{i \oplus j}$ と $x_k^i \times x_k^j = x_k^{(i+j) mod 2}$ は同値である。 $x_k^2 = 1$ 、つまり $x_k = -1, 1$ のとき、 $\times$ を乗算とすると上記の性質を持つようになり、 $x^i \times x^j = x^{i \oplus j}$ となる。これによって計算可能。実装は高速メビウス、ゼータ変換に似た形で可能。

参考

説明

Fast Walsh Hadamard Transforms and it's inner workings - Codeforces

実装

色々な畳み込み - kazuma8128’s blog

2021-01-10

HAL研究所プログラミングコンテスト2020

HAL研究所プログラミングコンテスト2020 に参加した。課題や競プロなどによって、3 日ほどしかできなかった。

実装

地形の境界に注目した。境界で、かつ格子点上の点と、巻物、最初のウサギの位置の点すべてを頂点とし、そのなかの任意の 2 つの頂点間の距離を、地形に応じた距離(砂地なら 10/3 倍、池なら 10 倍にする)として計算する。これは、通過するマスを 1 つずつ見ていって計算した。

その後、巻物の点、最初のウサギの位置の点からダイクストラを回し、巻物の点と最初のウサギの位置の点を頂点とする完全グラフを作成する。2 点の距離は、ダイクストラによって得られたパスに沿って実際にウサギが飛んで行った時の飛ぶ回数とした。これは、二分探索を改良した形で実装した。

この完全グラフを得た後、巡回セールスマン問題を解いた。(2^N)*(N^2) かかる方法で実装した。

そして、得られたパスに沿って進む、という風に書いた。

高速化

実装にかなりの時間がかかったうえ、実装すると全体で 140 秒かかってしまい、制限時間 6 0 秒を超えてしまった。二分探索の部分を高速化することで 100 秒まで落としたが、この時のボトルネックとなった、巡回セールスマン問題の部分と地形に応じた距離を調べる部分を高速化することができなかった。

やりたかったこと

二分探索みたいにすることで、よくなる時と悪くなる時があった。悪くなる時は、平地から少し先の池の部分に飛んでしまうようなパターンであった。この時に平地のぎりぎりで止まる、みたいなことをしたかった。

また、巻物を境界付近に持ってくる(巻物がある地点を踏んだらすぐ次に行く)実装もしたかった。

反省点

実装力が足りない。

また、定数倍高速化を今まであまりしてこなかったので、それほどできなかった。

2020-11-16

以前の出来事(競プロなど)

競プロ

高校~大学 2 回前期までの出来事(競プロなど)

中学 3 年

春頃、不登校になった。それにより、もともと真面目に行ってなかったバスケットボールのクラブをやめることとなった。

その後、友達から、ゲームが作れるクラブ、数学研究部があると聞き、当時ゲーム(wot blitz) にはまっていたので、クラブに入ることとなった。

最初は HSP を教えられ、ゲームを作ってみることとなった。しかし、自分はあまりゲームをした経験がなく、作りたいゲームの案が思い浮かばず、因数分解などをする、数学的なコードしか書くことができなかった。これを見かねた顧問が、JOI(情報オリンピック)を勧めてきた。

JOI 本選まであと 2 か月 + 今まで JOI 本選に行った生徒はおらず、顧問に「JOI 本選には行けないだろうけど、予選 B ランクを頑張って目指そう」といわれた。当時自分は自分にかなりの自信があったので、この言葉にカチンときて、絶対に JOI 本選に行ってやると心の中で誓った。

当時、競プロという言葉すら知らないので、練習は JOI 過去問のみであった。顧問から、DP、BFS、DFS のやり方を聞き、予選問 1~4 までは埋め、5 も最近のものは埋めていた。

予選で A ランクは取ることができなかったが、指定校推薦で本選に行くことができた。本選の次(代表合宿)には全く手が及ばなかったが、競プロ、atcoder、PCK、スパコンコンテスト、あり本など、競プロをするのに必要な情報一式を手に入れることができた。

余談ではあるが、指定校推薦をたたく気持ちはわかる一方、上記のように指定校推薦がなかったら JOI は知ってるものの競プロを知らず、練習量の差から本選に行けず、ずっと成長できないクラブ、学校が存在すると思っている。

高校 1 年

夏、先輩と同輩と自分の 3 人のチームで、スパコンコンテストに出た。当時、コンテストは C 言語しか提出できず、自分は C++ しか使えなかった。よって、map や queue など、内部のアルゴリズムを調べて C で実装した。予選通過はできたものの、本選が学校のセミナー期間と被っていた。

自分はもちろん本選に行くが、ほかのチームメイトはセミナーを休むことはできず、先輩は最後 3 日間、同輩には最初の 1 日来てもらって、チームの条件を満たすようにした。これは、主催の人たちの意図をガン無視しているので非常によくないと思い、今後のスパコンコンテストには出なかった。

スパコンコンテストは阪大で行われ、自宅からはそこそこの距離があり、さらに 4 日間同じ問題を考え続けるので、ものすごく大変だった。しかし、後々振り返るととても楽しかったうえ、いい経験ができたと思っている。セミナーを休んでくれる部員がいたら次年度も出たかったが、現実はそう甘くない。

秋、PCK に同輩と自分の 2 人で、チーム名「Moririn」で参加した。地域枠で本選に参加することができた。本選は友達と泊りがけだったので、とても楽しかった。本選の後、色々話過ぎて夜更かしをし、解説の会場までのバスで携帯をなくした。予選は 27 位、本選は 11 位だった。

冬、JOI 予選 A ランクで通過、本選は 600 点満点中、部分点の 5 点を取ることができず(その問題は最後の問題だったので、見ていなかった)、春合宿に行くことができなかった。これほど悔しいことはなかった。これによって、詰まったときにほかの問題もみるようになった。

数学オリンピックも受けたが、1 点足らず予選落ちした。

高校 2 年

夏、数学甲子園に参加したが、数学ができる人を集めることができず、予選通過できなかった。このために自治医科や防衛医、甲子園の過去問などを解いていたので、かなり悔しかった。

JOI の夏合宿にも参加した。そこで Haskell を学び、遅延評価を学習した。当時かなり難しく、進みは遅かったが、チューターのおかげで夏合宿後には遅延評価のやり方を理解できていた。発表はスプレー木についての解説をした。

秋、PCK に同輩と自分の 2 人で、チーム名「それはちがうよね」で参加した。これは、ある先生が言った言葉であった。今回こそは 10 位以内に入りたかったが、かなわず、地域枠で本選に参加することができた。本選は、ある問題を嘘解法で通してしまった(解説中に自分の解法を落とすケースが作れてしまった)。本選の結果は 5 位であった。表彰されるときにチーム名を言われるのだが、その時笑いをこらえるのに必死だった。

冬、JOI である。予選 A ランクで通過。本選は去年ギリギリ落ちたので絶対に通過してやると思っていた。しかし、前日泊まった部屋(JOI で用意された部屋)、が全室禁煙であるのに部屋の中がものすごくヤニ臭かった。管理人に行って普通の消臭剤で何とかごまかしていたが、深夜になってごまかしがきかず、寝れなくなってしまった。この時間は管理人がおらず、また、玄関はかぎが閉められており外に出ることができなかった。これによって寝ることができたのは、玄関が開いて、コンビニでヤニ用消臭剤を買い、使った後の 20 分ほどであった。基本的に徹夜をしない人なので、コンディションは最低であった。

しかし、本選通過したいという執念が勝ったのか、部分点を取りまくったことで何とか春合宿(日本代表候補合宿)に参加することができた。

春合宿は 5 時間コンテスト × 4 日間であり、とても大変だった。上位との差を一番肌で感じた瞬間であった。結果は 13 位であった。

数学オリンピックは、予選通過したものの、JOI の本選とこの本選の日程が被ってしまい、本選に出ることができなかった。

高校 3 年

春、受験対策において、英語、国語に重点を置いていたので、物理化学の勉強がずっと後回しになっていた。さすがにやらないといけない一方、近い目標がないとやれない性格であったので、物理チャレンジ、化学グランプリを受けることにし、予選までに受験対策を完璧にすることにした。実際、することができ、おまけに予選通過した。一応受けるからには過去問もいくらか解いていたが、予想外であった。

夏、物理チャレンジ、化学グランプリの本選に出た。過去問を解いていた上、詰まったときに後ろの問題も見ることができたので、筆記はかなりできた。しかし、実験は授業でしかやったことがなく、それも中学で少しやった程度であり、化学では蒸留水でうまく洗えなかったり、瓶をこかしたり、物理ではアルミの棒と鉄の棒を間違えたことで棒を曲げてしまったり、巻き尺を壊したりしてしまった。ただ、解く順番がよかったので、ある程度点数を取ることができ、物理チャレンジ、化学グランプリともに金賞を得た。

京大工学部情報学科を目指していた。志望学科内で、第一回京大実践は 6 位、第二回京大実践、京大オープンは 2 位を取っていた(第一回京大オープンは物理、化学オリンピックと被っていて受けていない)。A 判定でも落ちるということを無限回聞いていたので、いい成績を取ると嬉しい一方自分が知らないうちに慢心して本番落ちてしまうのではないかという不安を増大させた。

京大実践の医学部は B 判定、東大実践の理3 は C 判定であったので、医学部行くやつはすごいなと思っていた。

いろいろなオリンピックでいい成績を取っていたので、特色入試も受けた。ワンチャン受かればいいなと思っていたら、これで受かった。

その後、全国統一プログラミングコンテスト王決定戦を予選通過し、本選のオンサイトで京大の競プロer と会うことができた。本選 83 位

大学 1 回

様々な本選に参加した。

夏、Google code jam 2019、Round 2 で 2443 位、敗退

秋、第一回日本最強プログラマー学生選手権、予選通過し、決勝で 32 位

冬、全国統一プログラミングコンテスト王決定戦、予選通過し、本選で 52 位

大学 2 回前期

春、NOMURA プログラミングコンテスト 2020 で、全体順位 27 位、学生順位 10 位となり、賞金 1 万円を獲得

夏、Google code jam 2020、Round 3 で 272 位、敗退

Facebook Hacker Cup、Round 2 で 535 位、敗退

2020 Topcoder Open Algorithm Competition (TCO20) Round 3B 32 位でアジア大会(Round 4) に出場、68 位で敗退

大学 2 回後期

秋、PGBattle にチーム名「焼肉食べ放題」( heno さん、yamunaku さん、僕)で参加、大学生のチーム内で 4 位となり、賞金得れず

大学 3 回前期

Google Hash Code、チーム名「KUPC」( suibaka さん、yamunaku さん、nxteru さん、僕) World Final 出場、24 位

2020-11-16

ICPC2020予選

競プロ

ICPC参加記

heno さんと yamunaku さんと自分の 3 人で、Heno_World として出た。

本番までにやったこと

最初 AOJ-ICPC の 600 点あたりの問題を埋めようとした。1 か月ほどかかったが、600 点の問題のほとんどを埋めることができた。解いた後、自分の考察順序を

https://kuiss.sakura.ne.jp/wiki/AOJ-ICPC にまとめた。

AUPC や、HUPC、JAG-ICPC などにチームで参加した。これらのチーム練習によって、自分の実装能力のなさが迷惑であることに気づく。JAG-ICPC のとき、問題 C を無限にバグらせて、ペナをはやした上、最終的に heno さんに解いてもらう形となり、特に実装力を上げる必要があると感じた。

しかし、ICPC までの時間は少なく、とりあえず簡単な問題でペナを生やさずに解けることが大事だと思い、AOJ-ICPC の低難易度の問題で早解きの練習をした。

本番

そして、本番はできるだけ実装しないことを心掛けた。実装は問題 A しかしていない。ほかに担当したことは、D の突っ込み役、F の考察、G の考察とデバッグである。G は実装出来たものの回す時間がなく、提出できなかった。(G は皆で解いていた感じがかなりあったので、提出できなかったのは悲しかった)

結果は 6 完 0 ペナ、2 位となった。安堵と嬉しさでいっぱいになった。

感想

自分に変わったことで、へのわが予選通過できなかった、といわれるのが怖かった。次の横浜での本選でも、よい順位を残したい。

当日

開始前