memo46

競プロの精進記録その他。

The 2024 ICPC Asia Pacific Championship 参加記(コーチ視点)

2024/2/29 〜 2024/3/3 に開催された所謂 ICPC playoff (https://icpc.asia/) に、早稲田大学のチーム「hot-k-k1」のコーチとして参加しました。

選手としてではなくコーチとして参加した記録になります。

出発前までの作業

参加意思の確認

ICPC Asia Yokohama Regional が終わってすぐ辺りから、Regional と WF の中間に位置する、通称 playoff と呼ばれる大会の存在が囁かれ始めたと記憶しています。

早稲田大学のチーム(KKT89, hot-k-k1)はどちらもYokohamaでそれなりに好成績を収めており、出場出来る可能性が高いことが分かっていました。

ICPC Asia Pacific 2023-2024 will have a Playoff Contest - Codeforces

ICPC 2023-2024 Asia Pacific - Google スプレッドシート

この時点では渡航費等が運営から支援されるかどうか、playoffの日程などが不明でしたが、選手たちに参加意思を確認した所、仮に運営や大学から支援が無かったとしても参加する意欲がある、ということだったので、コーチとして事務作業をバリバリやることにしました。

また、Yokohama にコーチとして参加した際に1日目とISUCONが被っていたのでISUCONの方に出たのですが、1日目に現地に居なかったことで選手や運営に少し迷惑をかけてしまったことがあり、慣れない海外でまた迷惑をかけるのは申し訳ないと思ったので、コーチを引き受けた以上、私もなるべく現地に参加する方向で考えることにしました。

渡航費・宿泊費の支援の有無の確認・大学への支援のお願い

そして年末にplayoffの日程が公開され、年始に運営から、hot-k-k1にplayoffへの参加権があることと、参加意思の確認をするメールが届きます。

参加しますという内容のメールを送信したついでに渡航費や宿泊費の有無について質問すると、「渡航費 + 宿泊費 + 参加登録費 は大学に負担してもらってね。それ以外（食事、excursion、etc...）は運営が負担するよ。」という内容の返信が来ました。

残念ながら運営から渡航費等に関する支援は受けられないと分かったので研究室の先生に相談してみた結果、所属学科の関係上支援を受けられる人と受けられない人が発生してしまいました。研究室の先生も親身に相談に乗ってくださり色々動いて下さった結果なので、これは仕方ありません...（支援を受けた人も全額補助して頂いた訳ではありません。難しいですね...）（今回のplayoffの他大の支援内容によっては今後改善される可能性がある、との言葉を頂いたので、来年以降は変わるかも？）

また、参加登録費に関しては IISF から支援を頂けることになりました。こちら非常に有り難かったです。

入国に必要な書類の準備

ベトナムは短期間の滞在であれば入国にビザ等は必要なくパスポートがあれば十分でした。（パスポートの有効期限が6ヶ月以上残っている必要がありますが）

ベトナム出入国情報 | 在ベトナム日本国大使館

今後別の国での playoff の参加を検討する場合は、その国の日本国大使館のサイトから入国に必要な書類等のチェックをした方がよいでしょう。

また、パスポートの取得には少なくとも1週間以上かかるので、早めの準備を心がける必要があります。（私は現住所と本籍地が遠く離れていたので戸籍謄本を郵送で取得しなければならず、とても大変でした）

ベトナムに渡航するにあたり、選手にパスポートの早めの取得を促しました。

偉そうに早めにパスポート取れと選手に言いながら自分はパスポートに関する作業をめちゃくちゃ面倒くさがっていたので、パスポートを取得するのは私が圧倒的に遅かったです。選手たち偉すぎる...

飛行機の予約

今回私は事情があり京都からベトナムに向かう必要があったので、選手たちと別の便でベトナムに向かう必要がありました。

そのため飛行機の予約は完全に選手たちに任せてしまいました。（これも主体的に行ってくれたのがとても有り難かったです）

飛行機はLCC（ベトジェットエア）で向かいました。補助が出る訳ではないので抑えられる費用はなるべく抑えようと考えたためです。

日本からベトナムまでは5~6時間で着くため、オプションは機内食などは付けずに受託手荷物預かりのみ付けました。

座席が狭すぎるなどの問題はありつつも、概ね問題なく過ごすことが出来ました。

ホテルの予約

ホテルに関しては、ICPCの運営が別の会社に委託しており、その会社経由で予約する形になっていました。

こちらも費用を抑えたいので最も安いホテルを予約することにしました。1泊の値段が同じホテルが2つ用意されていた（Western Hanoi Hotel と Western Hanoi Boutique Hotel）のですが、google map の口コミを見て若干評判な良さそうな Western Hanoi Boutique Hotel を選択しました。

代金は海外送金するように指示されていたのでSMBCダイレクトで送金しました。海外送金の手数料（3500円）が痛すぎましたが、Wiseなどの手数料が安い海外送金サービスは手数料が途中で引かれてしまい正しく全額届かないなどの問題があることが分かったので諦めて手数料を負担することにしました。

後で分かったのですが、ゴネれば現地支払いも許されたらしいです。そんな...（これは事前にメールで確認してみるべきだった）

ホテルに関しては、お湯が出にくすぎる（長時間待たないといけない上、出てもほとんど冷たい水）という欠点はありましたが、それ以外は日本のホテルとあまり変わらないサービスで、そんなに困ることはありませんでした。

参加登録費の支払い

参加登録費は現地で支払いを希望するチームが多いと聞いていたので、日本でUSDに換金して現地で支払いました。

現地でクレジットカードが使えるかどうか分からないので、念の為現金を用意しておいた方がよいと思います（一応クレジットカード使えたと聞きましたが）

IISF から支援を受ける関係で領収書が必要だったので、事前に運営にメールして領収書を現地で発行して貰えるかどうかの確認などを行っていました。

現地での作業

1日目(2/29)

この日は運営が用意して下さったバスに乗りホテルに移動するだけでした。

選手と一緒にバスに乗るつもりでしたが、選手が乗っている便が遅れていたので自分だけ先にバスでホテルまで移動しました。

その際ホテルでICPCグッズ等を受け取る予定でしたがホテルの方から何も渡されなかったため（多分ホテル側のミス）、困惑します。

選手が到着するまでかなり時間があり暇だったので、ホテルから徒歩15分ほどのコンビニ(サークルK)で選手の分まで水を買ったりおやつや酒を買ったりしていました。流石に知らない国の夜道を1人で歩くのはヤバかったので真似しない方が良さそう

途中で通った公園

2日目(3/1)

この日は参加登録、Opening Ceremony、Practice などを行う日でした。

Opening Ceremony

コンテスト会場

ここで参加登録費を払い、昨日受け取り損ねたICPCグッズなどを受け取り、チームの記念撮影などを行いました。ICPCグッズを受け取れてないことに関して必死に運営と会話し揉めた結果、運営がホテルまでICPCグッズを取りに行ってくれました。多分僕たちは何も悪いことをしてないと思うのですがちょっと申し訳ない気持ちになりました。運営の方々本当にありがとうございます...

Opening Ceremony は ホスト校のVNU-UETのおもてなしの気合の入り方が凄かったです。なんとしてでも他国の優秀な留学生をウチに入れたいという気概を感じました。

Practice 中はコーチはやることがないので適当に待ちます。

待機中に大学内のコーヒーショップで買ったベトナムコーヒー。とても美味しかった

Practice後、バスで食事会場まで向かうのですが、かなり色々なトラブルがあったのでこちら↓を御覧ください...

togetter.com

ちなみに参加登録費の支払いを済ませた時点でコーチの仕事は99%終わりです。

3日目(3/2)

コンテスト当日です。

選手は会場に入場し、コーチは選手の貴重品などを管理しながらコンテスト会場の外で待機します。ハノイは寒いので外で待機するのは中々アレなのですが、まぁ仕方ないです。Wi-Fiが提供されたのは有り難かったです。

コンテスト中は、KKT89チームのコーチのsuta、現地でdiscordで通話しながらかっつ君とplayoffミラーコンテストに参加していました。

コンテスト後はチャックオック寺を観光した後、近くのPan Pacific Hotelにて Closing Ceremonyが行われ、恒例のYes/Noと共に結果発表が行われました。

チャックオック寺

Closing Ceremony

早稲田のチームは、KKT89は43位、hot-k-k1は32位と健闘しました。お疲れ様でした！

夕食は同じホテルで食事が出ました。コーチは選手とは別の会場で、偉い人たちが沢山いる会場で食べました。飯もワインも全部美味しかったです。

Pan Pacific Hotel のご飯

グラスの中を空にしても無限に注がれるワインでかなり気持ちよくなりながら食事してたらバスに置いていかれたので、コーチ陣で2軒目に行ってからタクシーで帰ることになりました。めっちゃ心配されてたみたいだけどかなり楽しんでしまった。ごめんなさい。

バスに乗り遅れた後に行ったバーで頼んだベトナムビール

バー（24階）からの夜景

4日目(3/3)

この日は Ha Long Bay Excursion となっており、運営が用意して下さったクルーズに乗ってハロン湾観光をしました。

世界遺産をタダで観光出来たし、ハロン湾の洞窟探検もとても面白く非常に満足した1日になりました。

弊チームは翌日朝に運営が用意して下さったタクシーに乗って空港まで送って頂き、無事帰国しました。

タクシーの中で運営の方と同席させて頂いたのですが、作問作業のお話などを伺うことが出来て楽しかったです。

（余談ですがチェックアウトしようと早朝にロビーに降りたらホテルマンがロビーのソファーで寝ててびっくりしました。ベトナムは最後までベトナムだった。）

感想

行く前まではコーチって現地で何するんだろうと思っていましたが、実際に行ってみた所ICPCの偉い人と美味しいご飯を頂いたり、魅力的な観光をさせて頂くことが出来てビックリしてしまいました。

ICPCのコーチはやった方がお得です！！！！（重要）

これも全て ICPC 運営の方々や現地の学生ボランティア、僕をplayoffに連れて行ってくれた選手、その他ICPCに関わる全ての方々のおかげだと思います。学生最後にとても楽しい思い出になりました。本当にありがとうございました。

ABC340G の木DPパート

次数 1 の頂点の色 $c$ を固定した時の問題を $O(N)$ で解く方法です。

次の動的計画法を考えます。

- $\mathrm{dp}[u]:=$ 頂点 $u$ を根とする部分木の中で、次数 1 の頂点の色が全て $c$ であるものの通り数。

- $\mathrm{dp}_2[u]:=$ 頂点 $u$ を根とする部分木の中で、次数 1 の頂点の色が全て $c$ であるものの通り数。ただし頂点 $u$ が色 $c$ でなく次数 1 であったとしても、頂点 $u$ が孤立点でなければよいものとする。

 

頂点 $u$ の色で場合分けをします。頂点 $u$ の子の集合を $\mathrm{child}(u)$ と表記します。

 

(1) 頂点 $u$ の色が $c$ である時
全ての $v \in \mathrm{child}(u)$ について、$v$ を根とする部分木を含めるか含めないかを考えると、

$\mathrm{dp}[u] = \prod_{v \in \mathrm{child}(u)} (\mathrm{dp}_2[v] + 1)$

$\mathrm{dp}_2[u] = \prod_{v \in \mathrm{child}(u)} (\mathrm{dp}_2[v] + 1)$

が成り立ちます。

 

(2) 頂点 $u$ の色が $c$ でない時
先程と同様に、全ての $v \in \mathrm{child}(u)$ について、$v$ を根とする部分木を含めるか含めないかを考えます。ただし、頂点 $u$ が次数 1 になってしまってはいけないので、頂点 $u$ の子ノードを根とする部分木を 2 つ以上含める必要があります。よって、

$\mathrm{dp}[u] = \prod_{v \in \mathrm{child}(u)} (\mathrm{dp}_2[v] + 1) - \sum_{v \in \mathrm{child}(u)} \mathrm{dp}_2[v] - 1$

$\mathrm{dp}_2[u] = \prod_{v \in \mathrm{child}(u)} (\mathrm{dp}_2[v] + 1)  - 1$

が成り立ちます。（全体から子ノードを 1 つだけ採用するパターンと、子ノードを 1 つも採用しないパターンを引いています。）

また、$\mathrm{dp}_2$ に関しては、$u$ が孤立点でなければ、$u$ の親ノードが $u$ を部分木に含めることによって $u$ の次数が 2 以上になる可能性があります。

よって、頂点 $u$ の次数が 1 で確定してしまうのは現時点で頂点 $u$ が孤立点になってしまうパターンのみなので、子ノードを 1 つも採用しないパターンのみを除きます。

 

以上の動的計画法を行い、最終的に、$\sum_{u=1}^{N} \mathrm{dp}[u]$ が求める答えです。

Golang で競プロ

勉強し始めて日が浅いので、間違っていることがあれば是非教えて頂きたいです

所感

個人的には競プロ(algo)で言語選択をする場合、以下の点が重要だと考えています

  • 実行速度が早い
    • 想定解法を思いついていたのに言語が遅くてTLEしてしまった... は悲しい
      • 高速化してAC出来たとしてもペナルティが痛すぎる
    • 想定解法より遅い解法でも実行速度が早い言語なら定数倍高速化により無理矢理AC出来ることもあるので有利
      • 余計なlogをつけても許される確率が高まる
  • 簡潔に書ける
    • タイピング量は短い方が実装が早く終わるので有利
    • 競プロでは保守性を気にする必要は基本的になく(炎上)、自分が読めたり使えたりしさえすれば良いので、マクロが使えたりコンパイルなども厳しくないほうが良い
  • 標準ライブラリや、ジャッジで使えるライブラリが豊富
    • 例えば平衡二分木(set, map)はかなり使う機会がある（これらを使うことが想定解法であることも多い）ので、これらが標準で用意されていないと自分で用意しなければならない
      • しかし平衡二分木は実装がめちゃくちゃ大変なので自分で用意するハードルが高い
  • 他人のライブラリを窃盗出来るか
    • 実装が大変なデータ構造やライブラリでも他の人のライブラリをパクってきてACすることはよくあります
      • Luzhild's Library にお世話になっている人は多いのではないでしょうか
      • 人によっては怒られるので注意、ライセンスをよく読むこと
        • 最も競プロにおいては怒られる例をあまり知らないが...

これらの点において golang は

  • 実行速度は？
    • 基本的にC++と同等に早く、十分と言える
  • 簡潔に書ける？
  • ライブラリは豊富？
    • AtCoder (Go 1.20.6)
      • 2023年のジャッジアップデートにより結構使えるようになった
        • 特に gostl が追加されたのは大きい
        • これまで golang では gods というデータ構造やアルゴリズムが実装されたライブラリが使えたが、新たに追加された gostl では C++ の STL を意識した実装がされていて、generics を使って実装されているので使いやすいしイテレータもサポートされている
          • 便利な点はあるが不便な点もあり、例えばsetなどはiteratorを指定して要素を削除するメソッドが用意されておらず、multisetを使うときに苦労する可能性が高い
        • golang.org/x/exp/ も追加されていて、slices, constraints とかは便利
        • ACLが使えないのはキツい
    • Codeforces (Go 1.19.5)
      • 標準ライブラリ以外何も使えないのでかなり厳しい (詳細)
    • yukicoder (Go 1.21.3)
      • Codeforces と同じ？(どこに書いてあるか不明だがオンライン実行で試したところ無さそうだった)
    • その他のジャッジ
      • あまり使わないので調べていません
  • 他人のライブラリを窃盗出来るか？

という感じで割と大変だけど無理ではないかなあという感じです 詳しい所はちょろっと使ってみただけの私の感想よりGoでAtCoderをやる話 #Go - Qiitaの方が参考になります

後、他人のライブラリを窃盗出来るか？という点について悪いように見えますが、自作を強制されることで理解を深められるという点でメリットであるという見方もできます

ちなみにこんな記事を書いておいて申し訳ないですが golang を普段使いの言語にする予定はないです（でも ISUCON で使うために勉強してみてかなり好きな言語だなと思ったのでたまに気分転換で使うかもしれません）

後、Heuristic については golang で参加したことがないので分かりません

Golang で競プロする時の注意点

先程も紹介させて頂きましたが、Goで競技プログラミングをするときに作っておくと便利な関数 #Go - Qiita ←こちらの記事を参考にしつつ自分で工夫していた点を説明していきます

入出力

入出力はバッファリングしないと遅いのでbufioパッケージを使います。 構造体にしておくと便利です。 構造体にするついでに、整数列や文字列、グリッドなどの入力やPrintln Printfなどをメソッドとして用意しておくと便利だと思います。

type Io struct {
    In  *bufio.Scanner
    Out *bufio.Writer
}

func NewIo(r io.Reader, w io.Writer) *Io {
    const bufsize = 10000001
    s := bufio.NewScanner(r)
    s.Split(bufio.ScanWords)
    s.Buffer(make([]byte, bufsize), bufsize)
    return &Io{In: s, Out: bufio.NewWriter(w)}
}

func (io *Io) Text() string {
    if !io.In.Scan() {
        panic("failed to Text()")
    }
    return io.In.Text()
}

func (io *Io) NextInt() int {
    x, err := strconv.Atoi(io.Text())
    if err != nil {
        panic("failed to NextInt()")
    }
    return x
}

func (io *Io) NextInt64() int64 {
    x, err := strconv.ParseInt(io.Text(), 10, 64)
    if err != nil {
        panic("failed to NextInt64()")
    }
    return x
}

func (io *Io) NextSliceInt(n int) []int {
    v := make([]int, n)
    for i := 0; i < n; i++ {
        v[i] = io.NextInt()
    }
    return v
}

func (io *Io) NextSliceInt64(n int) []int64 {
    v := make([]int64, n)
    for i := 0; i < n; i++ {
        v[i] = io.NextInt64()
    }
    return v
}

func (io *Io) NextSliceText(n int) []string {
    v := make([]string, n)
    for i := 0; i < n; i++ {
        v[i] = io.Text()
    }
    return v
}

func (io *Io) Println(x ...any) {
    if _, err := fmt.Fprintln(io.Out, x...); err != nil {
        panic("failed to Println()")
    }
}

func (io *Io) Print(x ...any) {
    if _, err := fmt.Fprint(io.Out, x...); err != nil {
        panic("failed to Print()")
    }
}

func (io *Io) Printf(format string, x ...any) {
    if _, err := fmt.Fprintf(io.Out, format, x...); err != nil {
        panic("failed to Printf()")
    }
}

gostl

ドキュメントはこちら↓ pkg.go.dev

GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more powerful.

として紹介されており、実際実装を読んで見ると本当にそんな感じなので凄いです

ただし全部揃っているわけではないので注意する必要があります

set/multiset

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/set

赤黒木で実装されていて、大体 std::set と同じように使えます

ただし注意点としてイテレータを指定して要素を削除するメソッドが用意されていません、なのでmultisetを使う時にとても困ります どうして...

一応 issue は立っておりプルリクもあったようなのですがcloseされてしまっていますね

同じ階層に rbtree パッケージがあるので、それを用いて自分で実装して使うのが良さそうですかね？（そもそも set って赤黒木で実装するのが効率良いのかもよく分かってないので、1から自作した方が良い説もあります）

(追記) よく考えたら treemap で代用することも出来ますね

treemap

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/map

こちらも赤黒木で実装されており、std::map と同じように使えます

こちらにはイテレータを指定して削除するメソッド（EraseIter）があるので基本的に困らない気がします

実際の使用例：Submission #48893483 - AtCoder Daily Training ALL 2023/10/24 15:30start

priority_queue

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/priorityqueue

golang の標準ライブラリにcontainer/heapがあり、これを使うことも出来ますが gostl の方が使いやすいかもしれません

vector

https://pkg.go.dev/github.com/liyue201/gostl@v1.2.0/ds/vector

一応 vector もあるんですけど、C++みたいに演算子オーバーロードがないので...（もちろん普通のプログラミングだと無い方がよいかもしれないのだが、ここは競技プログラミングの世界）

多くの場合 slice で十分な気がします

modint

演算子オーバーロードがある言語じゃないと無理なので諦めるしかなさそうですね...

その他便利関数

generics を使うと良い感じになって嬉しいです

<で比較可能という型制約をどう実装すればいいか分からなかったのでconstraintsパッケージを使っています

func Max[T constraints.Ordered](x, y T) T {
    if x < y {
        return y
    }
    return x
}

func Min[T constraints.Ordered](x, y T) T {
    if x < y {
        return x
    }
    return y
}

func Chmax[T constraints.Ordered](x *T, y T) bool {
    if *x < y {
        *x = y
        return true
    }
    return false
}

func Chmin[T constraints.Ordered](x *T, y T) bool {
    if *x > y {
        *x = y
        return true
    }
    return false
}

func Abs[T constraints.Integer | constraints.Float](x T) T {
    return Max(x, -x)
}

func Reverse[T any](x []T) []T {
    for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
        x[i], x[j] = x[j], x[i]
    }
    return x
}

func Unique[T constraints.Ordered](x []T) []T {
    slices.Sort(x)
    return slices.Clip(slices.Compact(x))
}

感想

Golang は言語仕様がシンプルなので、ライブラリの内部実装を自分でも読むことが出来て楽しい言語だと思っています。

generics に関する仕様を全然理解できてないのでもっと頑張りたいです、これから趣味の範囲で使っていけたらと思います。

ISUCON13 参加記

kiyoshi0205, erule159 とISUCONに初めて参加して スコアは 17782点 でした。

1. 事前準備

夏休み〜参加登録まで

  • インターンでDBのチューニングはやったことがあるものの大分忘れているし、準備しないとまずいなという気持ちになったので勉強することに
  • ISUCON本(https://amzn.asia/d/dah3bzb)を買って勉強した
    • 元々Webアプリのパフォーマンスチューニングや監視などに興味があったので、この本は興味とドンピシャで面白かった
    • 実際の業務に触れたことが無かったので、「実際の業務では〜」という視点が書かれていたりしていたのも良かった
    • 手を動かしながらじゃないと身につかない気がしたので、private-isu を multipass で動かし、それを使って勉強していた（自分が使っているPCがMacなので）
  • のんびり読んでいたり他のことをしていたりであまり時間が取れず、結局6章ぐらいまでしか読んでいないです

参加登録〜ISUCON本番

  • ISUCONを一緒にやる仲間を2人誘った
  • 使用言語をGoに決めた
    • 研究で使っているPython以外どれも等しく書いたことがなかったので何でも良いと思っていたが、話し合いの結果Goになった
    • AtCoder の過去問をGoで何問か解いてGoに慣れておいた
      • 新しく学んだ言語を手っ取り早く馴染ませるには競プロをやるのが一番良いと思っています。競技プログラミングはISUCONの役に立つ。
    • ISUCON終了後の利用言語比率を見たらGoの使用率が70%とかだったので、特にこだわりがない場合はGoを使うのが良さそう。たまたまGoを選んどいてよかった〜
  • 練習として、通話を繋ぎながらISUCON11予選のバーチャルを一緒にやった
  • かなりまずそうなことが分かり、ISUCONまでの残りの時間で必死に練習・・・
  • オンラインだと中々難しい気がしたのでオフラインで集まってやることに

2. ISUCON本番

役割分担

  • siro53(筆者) : 基本的にインフラ（環境構築、計測、deploy、複数台構成への変更等）をやる。余力がある場合のみwebappやdbの改善をやる。リモートサーバーは基本的にsiro53しか触らない。
  • kiyoshi0205, erule159：webapp, dbの改善をガンガンやる

    使用ツール

  • alp
    • nginx の access log を解析するやつ。ISUCON本に載っていたが非常に便利だった
  • pt-query-digest
    • mysql の slow query を解析するやつ。indexを貼ったりする時にこれを見る。便利
  • pprof
    • Goのプロファイリングツール。例えばどの関数にどのぐらい実行時間がかかっているか、が分かる。これもめちゃくちゃ便利
  • Makefile
  • discord
    • alp, pt-query-digest, pprof 等の実行結果を貼り付けて共有したりしていました

本番

以下、本番行った改善です。

gitのcommit 履歴やベンチの結果を元に時系列順に書いていますが、記憶があやふやなので正確でない可能性があります。

10:00 競技開始

  • 配布された cloudformation template を元にインスタンスを立てる。練習時に使っていたインスタンスを消していなくて「インスタンス作りすぎ」みたいなメッセージが出てしまいerrorが出たりしてモタついてしまった
  • インスタンスが立った後、ツールを導入。事前に用意していたMakefileが変数名のtypo等でバグり散らかしており、非常にモタついてしまった…（大反省）
  • 僕以外のメンバーは競技マニュアルやアプリマニュアルを読んでいた

10:49 初ベンチ実行(3631点)

  • ツールの導入は終わり、nginxやmysqlの設定の変更などをしていた
    • ここでもMakefileがバグっていてモタついてしまった…
  • kiyoshi0205, erule159 は既にソースコードを読んでいくつか目星をつけていたっぽい

11:10 KEYを貼る(3335点)

  • kiyoshi が必要そうな所にkeyを貼ってくれた。スコアが全く伸びなくてマジか〜となる。
    • 実際これでスコアが伸びないのはおかしくて、後に凄い事実が発覚する…
  • alpの実行結果を見てボトルネックになっていそうな所を僕が色々指摘する。

12:00ぐらい ADMIN PREPARE 解消

  • conf.InterpolateParams = true　を取りあえず追記しておく

12:48 POST /api/livestream/:livestream_id/livecomment の改善 (3993点)

  • erule159 が N+1を解消したりその他色々やっていた
  • Makefileがバグっていて、実は今までちゃんとデプロイ出来ていませんでした…ということに気づいてMakefileを修正したらちゃんとデプロイ出来たのかちょっとだけ点が伸びた(…のか？)
  • ここらへんで諸々のconfigの変更が完了していた気がする

ここら辺からベンチが詰まり始める。ベンチが中々実行できずにabortされて辛かったが、ベンチの実行が出来るようになるまで待ってられないということで改善する→プルリク立てるをひたすらやることに

14:22 foreign key の追加

  • kiyoshi0205 が色んなテーブルにforeign keyを追加していた

14:51 GET /api/livestream/:livestream_id/statistics の改善 (4011点)

  • pprof、alpを見ると重かったので中身を見るとN+1だったので siro53 がN+1を解消した。
  • バグってfailしたのをkiyoshiが修正してくれた

(ここら辺から記憶が曖昧です)

16:00ぐらい GET /api/user/:username/livestream の改善

  • erule159 がN+1の解消をしてくれた

16:00ぐらい iconのhashをチェックして304を返すようにする

  • テーブルにimage_hashカラムを追加して、画像を追加した際にhashを計算しておき、hashが一致したら304を返すようにしておく、というのをkiyoshiがやってくれたがfailする
  • ハッシュ値の前後に””が入っているのに気づいていなくてそれを修正したりするが、やはりfailする
  • journalctlでログを見ると「image_hashカラムが存在しません」というmysqlのerrorが出ていて「いやカラム追加したけど？？？？？」となる
  • ここで初めてDBの初期化がどうなっているかを確認した。webapp/sql/init.sqlを読むと、なんとDROP TABLE IF EXISTS… しているわけではなく単にDBの中のレコードを全削除しているだけということが判明。ということで今までindexを貼ったりforeign keyを設定したり、カラムを追加したり…といった作業は全部反映されていませんでした。俺たちは今まで一体何を…？？？

16:30ぐらい DBの初期化処理を変更 (10357点)

  • DBの初期化処理を修正するとスコアが爆伸びし、爆笑…
  • ちなみに初期化の結果 foreign key の設定が反映され、failしてしまうことが分かり、原因もよくわからなかったのでforeign keyの設定はやめることになった

17:00ぐらい fillLivestreamResponse() の改善 (11992点)

  • 僕がN+1を解消した。

17:00ぐらいGET /api/livestream/:livestream_id/moderate の改善 (12600点)

  • erule159 がN+1の解消をしてくれた。

17:30ぐらい appとDBの分離 (16206点)

  • 2台目のインスタンスを使ってそちらにDBを移植した。移植自体は前日の深夜に練習していたのですんなりいけた

17:50ぐらい 不要なログを切る (17782点)

  • nginxのaccess logやmysqlのslow query log、echoのdebug logなどを切った
  • 終了

再起動試験の対策は特にしていませんでしたが、再起動試験はpassしていました。

3. 反省点

  • 準備が悪すぎた
    • 初動で時間かかりすぎた。自分がセットアップを終える頃には20000点ぐらいのチームがいた気がしていて、初動で大分差が付きそうな気がした。
    • github template をもっと整備しておく
  • 1人に負担が集中しすぎ
    • デプロイ・ベンチ実行・結果をdiscordに貼る を全て僕が手動でやっており、非常にしんどかった
    • ISUCON公式 discord で質問したら pprotein という便利ツールがあることを知ったので、練習で使ってみたい
      • 他にもメトリクスをモニタリングするツールを自作している人もいたりして、すごい！
    • デプロイまではCIで自動で出来るようにしておくのが良さそうか？
  • 実装・デバッグが遅すぎる
    • まぁこれは練習するしかないよね
  • DNS水責め対策まで手が回らなかった
    • N+1を潰したりといった基本的な改善はサクサク出来るようにしておかないとこういった所まで手が回らなくて、上位に食い込むのは厳しそうです

4. 感想

初めて参加してみてめちゃくちゃ色んなことを学べました。特にAWSとさくらのクラウドのクーポンが貰えたのにはビックリして、参加するだけでもお得じゃん...と思いました。

予定が合えば来年もISUCONに参加したいです。運営の皆様本当にありがとうございました。

AtCoder 黄色 になりました

競技プログラミングを開始して4年半、青になってからは2年半でようやく黄色になることが出来ました。

本当は次のARCで青落ちしてまた戻ってこれたらこの記事を書こうと思っていたのですが、時間が経過するごとに色々書きたいことを忘れそうなので忘れないうちに書くことにしました。

青〜黄になるまでにやったこと

大体時系列順に並んでいると思います。

CF バチャ

記憶が正しければ青になりたての頃に CF div2, ECR バチャをそこそこ高頻度でやっていました。

結論から言うと実力向上には間違いなく役に立ったのですが、upsolveをしっかりしないまま次のバチャを始めたりしていて効率の悪い精進になってしまっていたなぁと感じています。（結構他の方と一緒にバチャを走っていたのですが、upsolveをしっかりしつつ回数をこなしている方はすぐに実力を伸ばしていた印象があります。）

コンテストやバチャはしっかりupsolveをしなければ中々実力向上に与しないんだなぁと身を持って感じました。

ABC 黄・橙 diff 埋め

ABCの後半を解くのに不足した知識を埋めるために始めました。バチャのリンク

解説をガンガン開ける方針で埋めていきました。全然歯が立たずほぼ写経になってしまいそうなものは解説を読み込んでACはせずに放置して後で再挑戦する、みたいなことをしていました。

バチャの順位表を見れば分かる通り全部埋められていないんですが、これは効果があったような気がします。ただ非常に大変なのでモチベーション管理が難しいです。

コンテストに出るのをやめた(数ヶ月ぐらい)

学生最後のICPCで国内予選敗退して競プロを続ける理由を失った + あるゲーム*1が発売された ことを理由にコンテストに出るのを少しの期間辞めました。

元々青で停滞しているのに周りがどんどん黄色になっていく辛さで競プロへのモチベーションをかなり失っていました。しかし、ICPCがあるのでやめるわけにもいかない...という消極的な理由で続けていました。が、ついにICPCの参加権を失ったことで完全にモチベーションを失いました。

今だから言えるのですが、この選択は良かったと思っています。モチベーションがないのに無理やり続けていても精神を蝕むだけで何も良いことがありませんし、そんなんだったら別の楽しいことをやった方が良いです。ゲームはモチベーションが全てです。

ちなみに先程述べたあるゲームをしばらくやっていたのですが、アプデがまさかの3ヶ月来なかったので飽きが来たのと、オンサイトコンテスト*2 が開催されたことがきっかけで競プロを再開しました。

ライブラリ整備をちゃんとやるようになった

個人的に最近ABCの成績が良い理由の1つだと勝手に思っています。

ライブラリ整備は多くの人がやらなきゃと思いながらも「まぁいざとなったら人のライブラリを借りてくればいいだろ...」とサボるものだと思います。僕もそうでした。しかしこれをしっかりやっているのとやっていないのでは解くスピードに大きな差が出ます。現に、例えばABC294GではHL分解を知っていればやるだけなのにも関わらず、準備不足で解くのが遅くなったり解き切れなかった人をTwitterで多く見ました。

「○○はまだ勉強しなくてもいいだろう」みたいな考えで履修を先延ばしにするのはおすすめしません。

レートを気にするのを（なるべく）やめる

レートが下がるのが嫌という感情はとても分かるのですが、コンテスト中にレートを意識してしまいと要らない焦りを生んで解ける問題も解けなくなってしまいます。どうしても気になる人は predictor を消すなどすると良いと思います。（僕は結局消しませんでしたが...）

僕は「レートを上げる」ではなく「解けるべき問題を落とさない」ことを目標にコンテストに参加することにしています。

(2023/11/5 追記) 1600〜1800で沼っていた頃と比べて何が変わったか

ABCでの成績が安定し、ARCで青落ちしても黄色に戻れるようになってきました。 ここ最近、青で沼っていた頃の自分と今の自分で異なる点が分かって来たような気がするので書いてみます。

  • 青diff 以下をほぼ落とさなくなった
    • ジャンルに関わらずほとんど落とさなくなりました
    • 学生最強コンなどのARCチックなやつはまだまだ不安定です
  • 青diff 以下の問題の6, 7割ぐらいはスムーズに解法が出る
    • 早解き出来ることが多いです
  • 黄、橙diff の打率はそんなに変わってない
    • 難しい問題が解けるようになったわけではない気がします

つまり、ABCで大敗しなくなって（やらかしたと思ってもperf 1800〜1900ぐらいに収まる）、勝てる時は勝てる（2200〜2400 perf が出せる）ようになったのが黄色になれた要因かな、と思いました。

青diff 以下を落とさないためには、（意外性のない結論で申し訳無いですが）基本的な典型・知識の抜けがないかをひたすら点検する必要があるでしょう。

最後に

黄色になるまでやったことをつらつらと述べましたが、私が一番伝えたいのは「モチベーションは大切にすべし」です。

競プロはゲームですから、他のゲームと同様にモチベーションの維持が一番大切です。モチベーションを無視して無理にコンテストに出たり問題を解くのは（私の実体験に基づくと）むしろマイナスだと感じます。逆にモチベが高い時は、時間の許す限り問題を解きまくったりバチャをしまくったりコンテストに出まくりましょう。問題を解くのに飽きたら新しいデータ構造やアルゴリズムを履修してモチベを上げるのも良いですよね。

それでは楽しい競プロライフを（？）

おまけ：精進記録

*1:スプラトゥーン3

*2:https://atcoder.jp/contests/abc288

FORCIA社 の Summer Internship 2022 に参加しました

8/15 〜 8/19 の 5日間、FORCIA社 のサマーインターンシップに参加させて頂いていました。

www.forcia.com

非常にお世話になり、また沢山のことを学ばせて頂きましたので、是非紹介したいと思い筆を執ります。

選考まで

M1 になりそろそろ就職活動も意識しないといけないなぁという時期で、5月ぐらいから「どこかインターンに行けたらいいなぁ」と思い探し始めました。応募した時の自分のプロフィール的には多分こんな感じです。

  • 情報系学科卒、情報系修士M1
  • AtCoder 青
  • web系のバイトを少しやっている

話は少し逸れますが、数年前に「ゆるふわオンサイト#3」というフォルシアの社員の方が主催オンサイトコンテストイベントに参加したことがあって、その際にフォルシア社のことを知りました。（とても楽しかったです）他にもフォルシア社のインターン参加ブログなどをいくつか読んだことがあったため、インターンを探す時に候補に入れていました。 そんな中フォルシア社のインターンのコースを眺めて

チューニングコンテスト形式で、検索システムの高速化を目指していただきます。

という文言に惹かれて楽しそうと思い、「検索アプリケーション高速化コース」に応募しました。（面白そうかどうかはかなり大事な要素だと思っていたので、そこは一番意識して探していました）

5日間と期間が短いので自分のスキルがちゃんと合っているかどうかももちろん重視して考えました。「一応TypeScript 書いたことあるし、生のSQLは書いたことないけど prisma は触ったことあるからゼロってわけじゃないだろうし（？）、これから勉強すれば大丈夫だろう」と思ったので応募しました。

選考

AtCoderJobs から応募しました。

面接では研究の話や、アルバイトでどんな風に開発を進めていたか、どんな技術を使っていたか等を話したように思います。競プロの話はほとんどしていないと思います（多分、、、うろ覚えですが）

開発経験がガッツリあるわけじゃないので受かるかどうか不安でしたが、採用メールが来たときは嬉しかったです。

選考後〜インターン開始まで

面接で PostgreSQL を使うと聞いていたので、採用のメールが来てから大学で本（https://www.amazon.co.jp/dp/4798160431）を借りて勉強しました。（全部は読んでいません）

最低限 SQL は書けるようにしておこう...と思い、https://topsic-contest.jp/contests/practice で練習したりしていました。

実際問題を解いてみると勉強したはずなのに全然書けなくて焦ったりしていました...やっぱり知っていると使えるは違うなぁって思いました。今思うとここで最低限書けるようにしておいてよかったです。あと競プロみたいに問題を解く形式だと勉強にも身が入りやすかったです。

あとは docker を使って PostgreSQL のサーバーを立てて、実際に色々触ったりもしていました。高速化についても勉強しようと思ったのですが、自分でデータセットを作るのが面倒で断念しました（？）

一応よくある高速化の手法はググって一通り確認していた感じです。

インターン中やったこと

テストデータの入ったDB+簡単な web アプリが与えられていて、それを高速に検索できるようにするといった内容の課題でした。テストデータを用いているとはいえDBのそれぞれのテーブルのサイズが非常に大きく、また実運用に近いデータセットであるというのが特徴です。

初日は何をしていいか分からなかったので、事前にググって調べていたよくある高速化を一通り試してみようと思ったのですが、中々上手くいかずほぼ進捗がないまま 1 日が終了してしまいました。この時内心めちゃくちゃ焦っていたのを覚えています。

しかし自分の席の近くの社員の方々が気さくに声をかけて下さったり、メンターの方に様々アドバイスを頂いたり分からないことを教えていただいたりなどの助けもあり、残りの日数で必死に課題にかじりついた結果、なんとか結果を出すことが出来ました。

特に、やみくもに高速化の手法を試すのではなく、EXPLAIN ANALYZE して実際にボトルネックになっている箇所を調べ、そこに対して適切に対策するというプロセスを学べたことが良かったです。3日目ぐらいに実行計画の読み方を社員の方に教えて頂けて正しく読めるようになり、そこからは対応策も適切に立てられるようになって、進捗も出やすくなりました。一般的なSQLの高速化方法は広く知られたものがいくつかありますが、それを用いるにもデータセットによって柔軟に対応する必要がある点が難しく、また面白かったです。

他のインターン生の方々が非常に優秀だったことも良い刺激を貰いました。

最終発表では多くの社員の方々に沢山のフィードバックを頂きました。かなり褒めて頂けたので嬉しかったです。

インターンを通して感じたこと

インターン中はオフィスの 1 席を実際に割り当てられて作業することができて、他の社員さんの仕事している様子を肌で感じることができたことが良かったです。

また「座談会」といって社員さんと雑談をする時間が設けられていて、社内に関する様々なことを聞いたり競プロの話をしたりと非常に楽しめました。個人的にはこの時間がとてもありがたかったです。

オフィス環境も、かなり良いスペックのマシンを割り当てて頂けましたし、休憩室のフリードリンクも充実していました。机にバナナが置いてあったり冷蔵庫にピノがあったりして、糖分補給に良く頂いていました。美味しかったです。

昼ご飯は高島屋の弁当が用意されていて、いつも豪華で毎日驚いていました。ご馳走様でした！

これで報酬が出るというのは驚きですね...。

（本当の本当に余談ですが、競プロの話をした社員の方々が全員黄・橙で、強すぎ...となっていました :thinking_face:）

最後に

長いような短いような非常に充実した 5 日間で、参加させて頂けて非常に感謝しています。

この参加記が今後このインターンシップを受ける方々の参考になれば幸いです。

おまけ：お昼ごはんのお弁当の写真たち

1日目

2日目

3日目

※ 4日目は写真を撮り忘れたんですが、ヒレカツ弁当と豚汁でした。美味しかったです。

5日目

ICPC2022 模擬国内 参加記

今年がラストイヤーです、チーム UH_ISSy (suta, siro53, ikefumy) で参加しました

（なお、模擬国のフォームを提出した後にチーム名を変えたので、模擬国は ISSy という名前で参加しています）

〜 -1日目

前日に yukicoder があり、それに出ていたらリハーサルをやるのを忘れた...

リハーサルはちゃんとやりましょう！

当日（開始前）

僕の所属する研究室に集まって参加。

他の早稲田のチームもいくつか（MSB, give us, STT) 大学に来て参加する予定っぽかったので普通に楽しみにしていた。

m_tsubasa さんが研究室に遊びに来たので、今度発売されるモンハンの新作の話をしたりした。モンハンの新作を買わせて闇討ちしようとしてきたので危なかった。

他にもコーチの hatty さんがアルフォートをくださったのでありがたく頂いたりしていた。

コンテスト本番

僕が A、suta が B、ikefumy君 が C を担当することになっていた。

先程も述べた通りリハーサルをやり忘れているので、不安になりながらスタート・・・

A を読み、「面倒だし O(N2) で実装するか...」と言いながら実装したらセグフォで動かず、よく見たら入力を受け取っていなかった...

直してもう一度サンプルを試そうとするとまた動かない。よく見たら「./a.out」ではなく「./a.cpp」を実行していて流石に笑ってしまった。

実行するとサンプルが合った。A を AC

B と C の状況を聞いてみると、なんと B が難しいとのことだった。

suta から概要を聞くと「それ桁DPじゃね？」という気持ちにしかならなかったのでそれを伝えると、

suta「え、そうじゃん　書きます」

あんまり詰めてないけどまぁそうだよね、てか今回は厳密には桁DPとはちょっと違うか、まぁいいや、C 大丈夫そうか聞いて D読もうかn...

suta「B 通った」

早すぎる...　この時 1桁順位だったと思う

C は適当にmapで実装を頑張るだけっぽかったので ikefumy君がそのまま実装し、 suta と D に取り組むことにする。

D をしばらく考えたり E を読んだりしているうちに C が通る。ちょっと実装がつらそうだった

E の概要を ikefumy君に伝えて D を再度考える。

ここで suta に「ある点が次の頂点にたどり着くまでの時刻でイベントソートして、その区間を三分探索すれば良いんじゃないか」と言われ、完全に正しそう（未証明）だなと思う。

三分探索に苦手意識があるので書いてもらうことに（これは僕が書くべきだったかも...）

E は数学で、かなり苦手意識があったが suta が D を実装していてやることがないので E の考察に混ぜてもらうことに。ちなみに MSB が爆速で E を通していて（FAだったらしい）かなり焦らされた...

しかしほとんど役には立てず、研究室に置いてある蟻本を持ってくるぐらいしか役には立てなかった。

結局 ikefumy君が1人で考察を終え、実装を始めた。僕は実装で苦しむ suta のデバッグを手伝うことに。

しばらくすると D のサンプルが合う。同じタイミングで ikefumy 君もサンプルがあったらしい。

同時にデータセットを実行し提出すると 1つめのデータセットがどちらも通る。無事もう1つも通り、盛り上がる。

ここまでの順位はいい感じで、コンテスト時間は後1hぐらい残っており、最後 F, G どちらに取り組むかという感じになっていた。FとGを手分けして読み全員で概要を把握した。

F は最小費用流で辺を O(MK) 本張れば確実に解けるが、終了までに実行が終わるとは思えないし、他の方法もわからない。

G は問題の見た目が Ears(耳DPの名前の元ネタ) に似ており、こちらの方がかなり希望があるように見えたのでGと心中することにした。

G は実際ほとんど考察が Ears に似ていて、それをベースに考えると i -> i+1 を何回通るかというのを左から決めたときにどのようなものがvalidになるかというのを考察する必要がある。

実際、i -> i+1 と i+1 -> i+2 の通る回数の差を d とすると、

  • dは高々2以下
  • dが奇数の箇所は2個

という条件になり、逆にこれを満たすような順列が存在するので左からdp出来る。

しかしこの問題は復元が必要なので更に考察が必要。

ここで ikefumy君が「折り返せるならその時点で貪欲に折り返してもよい」という考察をしていて実装していたが、時間切れ（結局この方針で正しかったらしい）

結果

16位 (selected 14位) でこの成績が取れればアジア進出ですが、去年は模擬国の成績はよかったものの本番で大失敗してしまったので油断しないようにしたいです。upsolveしっかりやります（まだ手をつけられていない...）