サークルで開催されたISUCONに参加した

サークルのOBであるdyumaさんがGWにサークル内でのISUCONを企画してくれた。 運営は、dyumaさんとbgpatさんにやって頂いた、ありがとうございます!

最近は、数学しかやっていなくて1ヶ月位コードを書いていなかったのでリハビリという目的と、世間は"Go"lden Weekらしいので、僕もGo書けるようになっておくか〜というモチベーションで参加した。 あと、忘れっぽいので、今回得た知見をどこかにぼちぼちまとめていきます。


問題

showwinさん作成の問題を解かせていただきました、ありがとうございます。

github.com


書いたコード

github.com


競技中のLog

思い出しながら書いたのでタイムスタンプは不明です。

  • とりあえずルールを確認してみると、点数が(status code 200 * 1点) - (status code 4xx * 20) - (status code 5xx * 50) で計算されていて、見た目でわからない範囲ならDOMだったりを変更していいらしいということがわかった。

  • いきなりやらかす。開始前に登録しておいてねと言われていた鍵を登録していない。平謝りしてインスタンスを作り直してもらう。

  • webappを動かさないことには始まらないので起動して、ブラウザでアクセスしてみる。他のページに比べてindex pageの表示がとても遅いことがわかる。画像を大量にDLしていたのでとりあえずNginxで直接配信するように設定した。(score微増)

  • webappのコードを読みに行くと案の定index pageで重い処理が走っていた。こいつがボトルネックなので、静的配信してもスコア伸びないよね…という感じ。 具体的には、50件の商品に対して最古のコメント5件をとってくるみたいなのをやっていた(俗に言うN+1)。これに関してはpageごとにメモリに載せておけばokなので載せる、ついでに商品説明の短縮とかも予めやっておく。

  • どうせならコメント件数とかredisに余裕で管理できそうなので、やりたいな〜と思いながらコードを読むと、commentがviewに使われておらずコメントの件数だけ管理すれば良いことに気づく。comment.goの内容を消し飛ばしてredisで件数のみ管理することにした(INCAR)。ここまででindex pageの表示は、そこそこ速くなった。

  • 次にコードを流し読みしてお手軽に改善できるところを探すと、current userを取得するのにselect文を投げていたのを発見、loginした時点でuserNameとかもクッキーに埋め込むことにした。ついでにLastLoginがどこにも使用されていなかったので消し飛ばした。

  • webapp中で使用されているクエリを変動のあるテーブルに着目して眺めると、userとproductは変化しないことがわかる。また、rowの数を見てみるとuser=5000, product=10000と余裕でメモリにのるので、sliceで持っておいた。ついでにlogin処理をmapで実装しなおしておいた。

  • ここらへんで鍵の権限がおかしくなって鯖から締め出される、外は寒い

  • インスタンスを作り直してもらって再参戦

  • ここまでで2万点くらいに達した。同期のkitakoukitoriaaaに負けているので次の策を考える。

  • コードを眺めたところもう一箇所ヤバイところを見つけたのでそちらの改善に乗り出す。購入履歴を取得するクエリなのだがjoinしてるしめんどくさそう… パット見でuserに商品がぶら下がっているデータ構造だと効率が良さそうな印象を受けた。joinしたあとにまあまあテーブルが大きいので、そのなかにuserが散らばっているという構図になっているので、やっぱりuserが鍵になっているぽい。あとexplainを見た感じ、ここらへんの予想が刺さりそうな雰囲気を受けたので、historyにuidでインデックスを貼ってやる。再度explainを見ると、うまくインデックスを使ってくれていることを確認した。

  • ここで10万点に到達した。あからさまなボトルネックを潰したので、序盤の改善が大きく生きて大幅に点数を伸ばすことに成功した。

  • 次は、購入合計金額だとかをredisで管理したり、購入済みかどうかをメモリで管理することにした、あとは簡単にメモリで管理できるやつをメモリで管理するようにした。ついでにMySQLとredisをUnixDomainSocketで通信するようにした。

  • 購入履歴を眺めてみると、なんか件数が少ない気がした。試しにtemplateを読んでみると30件しかとってきてないことに気づいたのでlimit30をつけてやる。template中で無駄なloopが回るのを阻止できたので点数アップ。ついでに、sqlで文字列操作したいなと思ってググると左から何文字とるみたいな操作ができるらしいのでやる。

  • logoutしたときに200返せるんじゃね?と思ってリダイレクトじゃなくてlogin pageをレンダリングするようにしたらうまくいった(微増)。 悪乗りして、セッションをクリアしないでみたらベンチマーカーにバレなかったので、そもそも/logoutをNginxで直接うけとってlogin pageを返すだけにした(こっちは目に見える効果があった)。

  • ここらへんで20万点にのった気がする。

  • ここまでくるとselect投げるのをやめたくなってくる。redisで管理するのもなんかな〜と思っているとgolangでは排他的制御がサクッと実装できることが判明、とりあえずチャレンジ。 購入履歴(history table)を触っている箇所を確認して実装した。次に、ここのlockを利用して管理できるやつをredisからおろして、まとめてやってしまうように改善。 (購入履歴の実装は、queueぽい実装を採用した。sliceへの理解が深まったのでいい経験になった。)

  • このあたりでworkload 10を超えると挙動がおかしくなる問題に悩まされる。top叩いてみると、cpuの使用率が大変なことになっているのでredisで管理していたものを全てメモリで管理して、redisを使用しないようにした。 リソースが空いたのでworkload 40でもちゃんと動くようになった。

  • 見た目でバレなければokというルールがあったので、画像を問題ない範囲で荒くしたり小さくしてサイズを小さくした(そもそも元の画像がでかすぎる)。

  • どうせならginとNginxをsocket通信させたいなと思って設定していたけれど全然うまく行かない。Discordで質問するとkitakoudyumaさん,bgpatさんが教えてくれた。どうやらパーミッションで死んでいたらしい。教えてもらったとおりにNginxの実行者を変更して無事設定完了。みなさんありがとうございました。しかし、微増(まあ、なんとなくわかってたけど)

  • ここらへんで30万点達成。

  • このあたりでfonoさんが参戦してきた。そろそろやめようかな〜と思っていたけれど、抜かれそうで怖いので継続することに決定。 しかし、「やることがわからなくて、わからないよ〜」と言っていたらdyumaさんとbgpatさんに計測することを勧められたのでkataribeを入れてみた。 kataribeの設定でいい感じに/user/:uidとかをまとめられることを教えてもらったので正規表現書いて色々まとめて出力させると、user pageへのアクセスが多いことがわかった。 あと、templateのfile readが遅いということを教えてもらった。

  • とりあえず教えてもらったところを改善しようと思ったので、io.WriteStringでhtmlをbufに入れてbyteに変換した後、それを配信するように設定した。 これに関しては、一番効果が期待できるuser pageに対してやってみた。

  • kataribeのログを見ると、購入履歴のread(user pageへのアクセス)件数 >>> 購入履歴のwrite件数 となっていることが読み取れるので、user pageをキャッシュすることにした。 これに関しては、「そのページに対してupdateがあったか」と「user page」という配列を持ってあげることで管理した。lockは、元々あったやつを流用することにした。

  • 最後に、パフォーマンスがあがるところだけ、templateをやめてioに切り替えた。

  • ここでフィニッシュ、37万点


結果

最終スコアは372,738点で、OB含めて3位でした!!! (実質1位) f:id:kadomachi_noiri:20210510022913p:plain


反省

計測を怠っていた。
なんとなくヤバそうなところを改善するアイディアを手当たりしだいに実装していったのが良くなかった。
勘でやるのは正直scientificじゃないので、計測に基づいてボトルネックを洗い出してピンポイントに改善するべき。
逆に、最後のuserpageへのアクセス件数と、buyの件数が大きく離れているからキャッシュという判断は良かったと思う。
ともあれ、次の機会があるなら、まず初手は計測ツールを導入することにする。


感想

研究したりISUCONしたりでめっちゃ有意義なGWになりました!企画&運営してくださったdyumaさんとbgpatさん、問題を作成してくれたshowwinさんありがとうございます!

めちゃ楽しかったので、また機会があったら参加したいです。

3年くらい前にdyumaさんに準備してもらってISHOCON1に触ったときはコマンド叩くのもおぼつかないレベルで、なんとかググって総当りでインデックスを張って試して3000~5000点くらい出して満足して(当然webappはよくわからんので触れなかった)、解法聞いても、そもそもNginxってなに?、キャッシュ?みたいな感じで何一つ理解できなかった思い出があります(念の為に言っておくとまじで解法とか、どこにインデックスを張ったかとかは忘却の彼方でした)。

今回、全然慣れてないGoで参戦して、「配列どうやってとるん?」とかからスタートして排他制御使ってキャッシュ実装できるようになったり、苦手意識のあったNginxの設定とかも(簡単なものだけど)できるようになりました。3年前の自分に比べて地力が成長していたり、色々な概念が身についていることが実感できて素直に嬉しいです。また、いろんな知見を得ることができてとても楽しかったです。

まあ、その、数年前に出会った解説すらよくわからなかった問題に対して、37万点をとって、過去の自分に大勝できたのでとても嬉しいということです。

高速な素因数分解

解説

まず、ある数字Nが持つ最小の素因数pを持つ配列sieveを作成します。
つまり、sieve(N) = pとなっています。
このような配列は、最初に昇順に数字を入れておいた配列sieveに対して、インデックスNと、その要素pが等しいところからエラトステネスの篩の要領でループを回すことで作成できます。

次に、上で作成した配列sieveを用いて、ある数字M素因数分解することを考えます。
これは、今現在の値のもつ最小の素因数で割り続けることで実現できます。
この方法だと高々logオーダーで計算することが出来ます。

計算量は、最大の数をNとすると篩を準備するフェーズでO(NloglogN)となります。
また、素因数分解する数をMとすると、O(logM)素因数分解出来ます。

コード

ABC177Eでverifyしました。
この問題では、k個の数を素因数分解しているので最大の計算量は、 O(NloglogN + klogM)となります。
Submission #18055027 - AtCoder Beginner Contest 177

struct SmartPrimeFactorize {
    vector<int> sieve;

    SmartPrimeFactorize(int Max_N) : sieve(Max_N + 1, 0) {
        //コンストラクタ中で篩を構築
        for (int i = 0; i <= Max_N; i++) sieve[i] = i;

        for (int i = 2; i * i <= Max_N; i++) {
            if (sieve[i] == i) {
                for (int j = i + i; j <= Max_N; j += i) {
                    sieve[j] = i;
                }
            }
        }
    }

    
    vector<int> prime_factorize(int n) {
        vector<int> fact;
        while (n != 1) {
            fact.push_back(sieve[n]);
            n /= sieve[n];
        }
        return fact; //素因数を列挙した配列を返す
    }
};

[C++]競プロのためのファイル入出力

はじめに

ICPCなどの大会ではファイルを提出する必要があります。
この記事は、とりあえずファイルの入出力をやりたい人に対して書かれています。
なので、細かい説明はしません。

mac/linux の場合

一行で出来てしまいます。

$ ./a.out < input.txt > output.txt

実行可能ファイルに対して<, >でファイルを渡してあげれば良いです。
こうすることで標準入力(cin)にinput.txtの中身を渡せます。また、標準出力(cout)の内容がoutput.txtに書き込まれます。
いつも通りに解答を書けばokです。

Windowsの場合

Visual Studioをお使いの方などは、おそらく上の方法が使えないので真面目にfstreamを使います。
例として、ファイルから

n
x y
n
x y
...

の形式で整数が渡されて、n = 0 の時に入力の終了を表すような入力を受け取り、
出力にxとyの和をファイルに書き込むようなコードを示します。

#include <fstream>

//ファイル入出力
ifstream ifs("input.txt"); 
ofstream ofs("output.txt", ios::app);

void solve() {
    int x, y;
    ifs >> x >> y;

    int ret = x + y;
    ofs << ret << endl;
}

int main() {
    while(ifs >> n) {
        if(n == 0) break;
        solve();
    }
}

上の例を見れば分かる通り、cinの代わりにifscoutの代わりにofsとするだけで良いです。

[a, b]の区間和を求める

基本

 1以上 x以下の整数の和は、 \frac{x(x+1)}{2}で求められる。

本題

上の公式で求めた後に、累積和の要領で差を取れば良いです、小さいほうの区間の右端が開いていることに注意します。
 S_A = sum(1 \leq x \lt A),  S_B = sum(1 \leq x \leq B) とすると、  sum(A \leq x \leq B) = S_B - S_Aのように差を取れば良く、 \frac{B(B+1)}{2} - \frac{A(A-1)}{2}となります(再三ですが、Aの右端が開いている事に注意してください)。

ICPC模擬国内2017D : ゲームバランス

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2826&lang=jp

問題

 N種類のモンスター s_iが昇順に与えられる。
主人公はレベル1からスタートし、自分のレベル+ X未満の敵を倒すことが出来る。
敵を倒すと max(1,\ X - |Level - s_i|)だけレベルが上昇する。
このゲームでは、 N番目の敵を倒すとゲームクリアとなる。
主人公が出来るだけ少ない戦闘回数でクリアするようにプレイしたとき、戦闘回数が M回以上になるようにパラメータ Xを求めよ。

解法

Xとクリアに必要な戦闘回数を適当にグラフにしてみると単調なことがわかります。これは、 Xが増えたからと言って戦闘回数が増える訳ではないことから明らかです。
単調性を確認できたので、 Xを2分探索することを考えます。
以下、判定部分に関して考えていきます。
効率の良いモンスターの狩り方は、自分のレベルに近いものを狩るのが良いです。このようなモンスターを高速に求めるには、lower_boundして、得られたインデックスとその次のインデックスを見れば良いです。
レベルごとにインデックスを求めておくとより高速ですが、制約が8秒と長いので今回はサボりました。
また、初手で積む場合 s_0 > 1 + Xは、1匹目のモンスターさえも狩れないときです。このときはNGを返せば良いです。

以上、考察でした。案外簡単目ですが、実装で沼ることが多いので注意です。(1敗)

実装

2分探索です。通るときは通りますが、バグるときはバグります。
という訳で判定関数の判定結果と、範囲の動き方をしっかりと確認しておきます。(コード書いてるとだんだんわからなくなってくるので)
縦軸が、戦闘回数、midが現在の Xです。

戦闘回数がm回以上の時です。最大にしたいので左側をmidに動かして、より大きなXについて調べます。

f:id:kadomachi_noiri:20201021002800p:plain

戦闘回数がm回未満の時です。これ以上Xを大きくしても仕方がないので右側をmidに動かして、より小さなXについて調べます。

f:id:kadomachi_noiri:20201021003151p:plain

今回、クリア不可能なときは戦闘回数をINFとして、より大きなXを調べています。(クリア出来ないときはXが小さすぎるので)
また、最後に求めたXがvalidかどうかの確認もしています。これは、求めたが下限や上限になってしまい条件を満たさない時を排除するためです。

コード

提出です。
AIZU ONLINE JUDGE: Code Review

vector<int> s;

int n, m;

const int INF = 1e7;


int check(int X) {
    int count = 0;
    int L = 1;

    //初手詰み
    if (s[0] >= 1 + X) {
        return INF;
    }

    while (L + X <= s[n - 1]) {
        //敵1と敵2のインデックス
        int e1 = lower_bound(s.begin(), s.end(), L) - s.begin();
        int e2 = e1 - 1;

        //out of indexでない かつ 倒せるならdiffを更新
        int diff = 1;
        if (e1 >= 0 && e1 <= n - 1 && s[e1] < L + X) {
            diff = max(diff, X - abs(L - s[e1]));
        }
        if (e2 >= 0 && e2 <= n - 1 && s[e2] < L + X) {
            diff = max(diff, X - abs(L - s[e2]));
        }
        count++;
        L += diff;
    }

    //ボスへのラストヒットを忘れない
    count++;
    return count;
}


int binary_search() {
    int left = 0;
    int right = INF + 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;

        if (check(mid) >= m) {
            left = mid;
        }
        else {
            right = mid;
        }
    }

    return left;
}


void solve() {
    s.assign(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    //クリア不可能でないならok
    int ans = binary_search();
    if (check(ans) != INF) {
        cout << ans << endl;
    }
    else {
        cout << -1 << endl;
    }
}


int main() {
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        solve();
    }
}

ICPC模擬国内2016b:D 夏合宿の朝は早い

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748&lang=jp

問題

各頂点が確率 pを重みとして持つような N頂点からなる有向グラフが与えられる。
また、各頂点は確率 1-p_iで状態Aとなる。状態Aとなった頂点は、隣接する頂点の状態をAに変えることが出来る。
何も状態が振られていない状況を考えて、次の瞬間に割り当てられた確率で状態Aに遷移したとする。
このとき、全ての頂点が状態Aとなっている確率を求めよ。ただし、頂点Aが隣接する頂点をAに変化させる処理は一瞬で終わるものとする。

(追記)AはAwakeということにしておいてください。

解法

まず、自明でない最も簡単な場合について考えてみます。(下の図参照)

f:id:kadomachi_noiri:20201020183609p:plain

このような場合は、入次数が0の頂点がAに遷移すればその下流の頂点はどんな状態でも良いです。
実際に確かめてみると
 ans = (1 - p_v) \times p_u + (1-p_v) \times (1-p_u)
 \Leftrightarrow (1 - p_v) \times (p_u + 1 - p_u)
 \Leftrightarrow (1 - p_v)
となるので確かめることができました。(確率であることに注意すれば容易にわかります)

次に、誰かがAに遷移しなくてもなんとかなりそうな場合で、最も冗長性が高い場合を考えましょう。(これはサイクルです、強連結成分と言ってもいいです)

f:id:kadomachi_noiri:20201020183330p:plain

どれかがAに遷移すれば良いので、この強連結成分がAに遷移する確率を求めるには、どれもAに遷移しない場合の余事象を取ればいいです。
上の図については、 ans = 1 - (p_v \times p_u \times p_w) で求められます。

さて、上の考察をあわせて考えてみます。1つ目の図の頂点vを強連結成分と思うことにしましょう。すると、強連結成分の確率だけが答えに影響します。
つまり、強連結成分を頂点と見立てて構築しなおしたグラフの入次数が0の頂点に付けられた確率のみが答えに影響します。
入次数が0の頂点は、自力でAに遷移しないと条件を満たさないので、そういった頂点が同時にAに遷移すれば良いです。
 p_iを入次数0の頂点に付けられた確率とすると
 ans = \prod (1-p_i)
とすれば答えが求まります。

実装

強連結成分分解をして、頂点に彩色します。
同じ色に彩色された頂点は、同じ強連結成分に含まれるので、強連結成分内にある頂点の確率の総積をとれば構築しなおしたグラフに含まれる頂点の確率が求まります。
次に、構築しなおしたグラフの入/出次数を調べます。最後に、入次数が0の頂点に付けられた確率の総積をとれば答えです。

因みに、強連結成分分解をする際に使用したコードはこれです。
強連結成分分解 - yrfw

コード

AIZU ONLINE JUDGE: Code Review

int n;

void solve() {

    vector<vector<int>> G(n);
    vector<double> p(n);

    for (int i = 0; i < n; i++) {
        cin >> p[i];

        int friend_n;
        cin >> friend_n;
        for (int j = 0; j < friend_n; j++) {
            int to; cin >> to;
            G[i].push_back(to-1);
        }   
    }

    
    StronglyConnectedComponents scc(G);
    scc.color_graph();
    vector<int> color = scc.nd_color;
    vector<vector<int>> H = scc.build();

    //彩色数
    int color_n = 0;
    for (auto c : color) color_n = max(color_n, c + 1);


    //強連結成分内での確率
    vector<double> group_p(color_n, 1);
    for (int i = 0; i < n; i++) {
        group_p[color[i]] *= p[i];
    }


    //in/out
    vector<pair<int, int>> degree(color_n);
    for (int v = 0; v < color_n; v++) {
        for (auto nv : H[v]) {
            //v -> nv
            degree[v].second++;
            degree[nv].first++;
        }
    }

    double ans = 1;

    for (int i = 0; i<color_n; i++) {
        int in = degree[i].first;
        int out = degree[i].second;
        if (in == 0) ans *= (1 - group_p[i]);
    }


    cout << fixed << setprecision(9) << ans  << endl;  
}


int main() {
    while (1) {
        cin >> n;
        if (n == 0) break;
        solve();
    }
}

強連結成分分解

次のサイトを参考にさせていただきました。
一応自分で使いやすい感じにカスタマイズさせていただきました。
強連結成分分解(Strongly-Connected-Components) | Luzhiled’s memo

解説

トポロジカルソートの要領で各頂点からdfsして、帰りがけに頂点を追加していきます。
次に、追加した頂点を始点として、辺を逆に張ったグラフ上でdfsをします。このとき、その頂点から行くことの出来た頂点は同じ強連結成分に含まれます。
詳しい証明などは他のサイトにまかせるとして、メインアイディアは、「連結成分なんだから、辺を逆に張ったグラフ上でも行き来できる」というものです。
かなり多めにコメントを書いたのでそちらを読んで頂くとわかりがいいと思います。

コード

verifyは、下記のaojの問題で行いました。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C&lang=jp

提出コードです。
AIZU ONLINE JUDGE: Code Review

using namespace std;

struct StronglyConnectedComponents {

    //受け取るグラフ, 順方向に辺を張ったグラフ, 逆方向に辺を張ったグラフ
    vector<vector<int>> g, ng, rg;

    //頂点の色, 帰りがけ順, 訪問済みかどうか
    vector<int> nd_color, tp_order, visited;

    //コンストラクタ
    StronglyConnectedComponents(vector<vector<int>>& g) : g(g), ng(g.size()), rg(g.size()), nd_color(g.size(), -1), visited(g.size()) {
        for (int v = 0; v < g.size(); v++) {
            //ng, rg を構築
            for (auto nv : g[v]) {
                ng[v].push_back(nv);//順方向
                rg[nv].push_back(v);//逆方向に辺を張りなおす
            }
        }
    }

    //頂点vから開始して帰りがけに頂点を追加していく
    void dfs(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (auto nv : ng[v]) dfs(nv);
        tp_order.push_back(v);
    }


    //逆方向のグラフに対してdfsして、強連結成分をcolorで塗ります
    void rdfs(int v, int color) {
        if (nd_color[v] != -1) return; //既に彩色されてたら取りやめる

        nd_color[v] = color;
        for (auto nv : rg[v]) rdfs(nv, color);
    }

    //強連結成分ごとに彩色します
    void color_graph() {

        //順方向のグラフにdfs(トポロジカルソートの要領で全点から)
        for (int i = 0; i < ng.size(); i++) {
            dfs(i);
        }
        //得られた順序は逆順なのでreveseします
        reverse(tp_order.begin(), tp_order.end());

        //帰りがけ順にrdfsします
        int color = 0;
        for (auto ord : tp_order) {
            if (nd_color[ord] == -1) {
                rdfs(ord, color);
                color++;
            }
        }
    }

    //強連結成分を1つの頂点に見立てたグラフを構築します(多重辺が含まれるので注意です!)
    vector<vector<int>> build() {

        //グラフの彩色数を求めます。
        int color_n = 0;
        for (auto c : nd_color) {
            color_n = max(color_n, c);
        }

        vector<vector<int>> ret(color_n + 1); //彩色数が頂点数になっています


        //隣接する頂点v,uについて考えたとき、両者の色が異なれば異なる強連結成分です
        for (int v = 0; v < g.size(); v++) {
            int v_c = nd_color[v];
            for (auto nv : g[v]) {
                int u_c = nd_color[nv];
                if (v_c != u_c) ret[v_c].push_back(u_c); //vの色からuの色に対して辺を張ります
            }
        }

        return ret;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> G(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    StronglyConnectedComponents scc(G);
    scc.color_graph();

    auto color = scc.nd_color;

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << (color[u] == color[v]) << endl;
    }
}