ntk log ntk

競プロや非競技プロのやったことを書いています.

ICPC2020 Asia Yokohama Regional 参加記

その他

だ～っと書いた日記です。

一日目

例年と違って今年はオンライン開催。初競プロオンサイトのチャンスだったので、やっぱりちょっと残念。

一日目は午後からだったけど、二日目は朝9時からコンテストが開始なので一日目も早起きした。ちょうど寝る前にAHC001のシステスが走っていたので、それが気になって早く起きられたな。

13時半までに受付（学生証をカメラでチェック、これのためにwebカメラ買った）を済ませる必要があって、ちょうど13時にzoomに入った。めちゃくちゃnoborito290yenが連呼されててすでにちょっとおもろかった。呼ばれたチームから順番に、zoomのブレイクアウトルームってのにチームがどんどん割り振られていく感じだったっぽい。

途中でThe atamaを運営の人が探すときに「あたまさん、あたまさん一人見つかりません」を連呼していておかしかったな。リストもそれに染まっていた。

f:id:ntk_ta01:20210316133153p:plain

学生証チェックだけどピントが合わなくてOKがパッともらえなかった。ピント合わせるの水diffくらいある。

開会式が始まった。アイコンがTwitterと同じ人かなり誰かわかりやすいな。リハーサルコンテストは「使い方に慣れてください」をめちゃくちゃ強調されたけど模擬地区やったからだいたい大丈夫だな～みたいな気持ちだった。

あ　リハーサルコンテスト後に今入ってるZoomの部屋に戻ってくるのか（メモ）　誰か紛失してそうURL（この少し後のTLで保存してない、みたいなのを誰かツイートしてた気がする）

slackの通知音が無限に聞こえてくる　10秒に一回くらい　ｽｯｺｺ　←だんだんこれが面白いと感じてくる、通知音で笑ってしまう罠

ジャッジシステムの説明北、DOMjudgeってやつでした。

二次方程式を解く問題をライブコーディングしてて、0割をケアしてなくてWAだったけど、説明してる人慌ててない。あまりに自然な流れだったので台本だったのか…と把握。そのままclarの説明行った。

f:id:ntk_ta01:20210316135803p:plain

これすき clarは英語で送れとのこと

f:id:ntk_ta01:20210316135900p:plain

流行語大賞　ぜひAtCoderでも使っていこう（迷惑では？それはそう）

リハーサルコンテスト始まったのでやっていき

TLEとかWAとかわざと出してねって言ってたからa.pyをC++選んで出してみる　CEかな？と思ったら

None of the submitted files match any of the allowed extensions for C++ (allowed: cpp, cc, cxx, c++)

ちゃんとこれが出た。ペナにならないっぽい。すげー。

質問の送り方もちゃんとやっておく。

AとBはいいとしてCはよくわからんだったな（実力さん……）、Judging Detailを読んだりしておく。

WA、OLE、CE、NO-OUTPUT、TLE、RE、TOO-LATEなどエラー全部出すをした。CEでペナつかないのはAtCoderと同じだったな。

Contact to Staff以外は英語で質問をしてくれとのこと（メモ）

居残りのチームあってびっくりした。しかもそのチームNから始まるから自分が呼ばれたのかと思った。これ結局なにで呼ばれたかどこでも知ることができなくて今も気になってる。

今日は早く寝るぞい！（寝た）

二日目

7時起き！

f:id:ntk_ta01:20210317075310p:plain

リストを見てると人々が続々と起きている。

8時半にはZoomなので着替えてこなきゃ……一限より早いやん。

少々の注意事項があって、コンテストが始まる。

もうここからかなりうろ覚えだけど、まあとにかくコンテストをやった。うちは緑水青のチームだった。AもBも分けてやるより全員で考察を進めていくみたいな形でやった。並列コーディングの恩恵はそんなになかったけれど、結果的にそれでAB通した時点の順位が最終よりはよかった気がする。うろ覚えだけど。

まあさらにBも全員で進めるというよりは、僕だけこれチームメンバーが通しそうだなと思ったあたりでJの読解に移ったりしていた。最終的にはABJの3完でコンテスト終了。JをACした後にGを読んでいたけれどわからなかったな。最近アルゴをやってなかったのもあって、テストケース作ったり読解やデバックばかりして実装はすべてチームメンバーに任せた。チームメンバーありがとう……。

順位表凍結（60分前になると各チームの提出がACかWAなのかわからなくなるシステム）の後の結果を貼りますと38/40位でした。難しい問題ばかりだったけれど、同時に強いチームばかりだったなあと改めて実感させられた。

f:id:ntk_ta01:20210317214713p:plain

順位表のリンク↓

icpcsec.firebaseapp.com

そっからはずっとGather Townにいた（ICPC運営からここで懇親、交流してね！と言われていた場所、なんかブラウザ上でマップがあって近くにいる人と通話できるサービス）。とは言っても「チーム名+本名」表記なので、知らない人にはめちゃくちゃ話しかけにくかった……。プロフィールにTwitter ID書いたり、suffixにハンドルネーム書いたりしてアピールしておきました（でも最終的に話したいと思っていた人に話しかけられないこともあったな～～～）。

Gather Town開始直後に店長さんがTwitterで募集をかけていたので凸る。

f:id:ntk_ta01:20210317213913p:plain

そっからはりゅうせいさんが集まったり山梨大のちるけーきさん（この人僕や店長さんら6人くらいがいるところに凸ってきたのすごかった、最初流れているYoutube Live側の音声だと思ってしまい申し訳ない）が来たりで結果発表などを聞きながら人々と喋っていた。ICPCから配られたポテチやチョコレートもお腹に入れていた（ICPCのポテチ美味しかった）。Yes/Noマン（筑波大の先生なのかな？）のおかげでYes/Noが面白いのを実感したり、上位6チームのつよつよのコメントを聞いて、かっけ～と思うなどした。＿＿KING_____マジですごかったなあ。

せっかくなので企業ブースに行ったり（Googleの方と喋ったりした）、問題Bのブースに行ったらJAGの方が来たり（りあんさんやamylaseさんと喋れた！こちらとしては一方的に知っていたので喋れてすごい！！！！みたいな気持ちになった）で楽しかった。あとうちのチームのmiiifaが前に競プロerスノボ？に行った関係でととりさんやolpheさんと喋っていたので混ぜってもらった。農工大競プロerに対して勝手なファン意識見たいなものがあったので喋れてかなり嬉しいみたいな気持ちがあった。

Gather Townの終盤はharaharaのうちのお二人やLorentさん、あとtsutajの方と喋っていてとても楽しかった。喋っているうちにGather Townを占める時間になっていたので名残惜しいけど解散をした。Lorentさん、マジで良い人だったな～～～～～～～。

まあアジア大会だったのでそれについてもうちょっと振り返っておくと、少し前に卒論が重なった時期だったのもあって（？）、競プロとは少し離れた時期にICPCアジア大会を迎えることとなった。もちろん元々の実力が離れていたのもあるが、それもあって上位はなんて遠い存在なんだ……。と改めて実感しました。強い人はAOJ-ICPCの550以下を埋めているし、直前になんどもバチャをしている。すごいなあ、遠いなあと改めて感じました。

国内予選通過もギリギリのラインだったので、そこから予想できた結果ではありましたがなんだか無力感みたいなのがあります。でもすごい強い人たちがいる大会に参加できたり、その後の懇親会も楽しめたのでとてもよかったです。最初に言ったようにオンラインでの開催だったので、オフラインとは違ったものになりましたが、その中でもとても楽しい経験ができた大会だったと思います。運営の方ありがとうございました！！！！

次の（自分のラストの）ICPC国内予選も突破してアジア地区行けたりしたらいいな。そんなことを考えています。参加した方はお疲れさまでした、応援してくれていた方はありがとうございました！

AHC001 参加記

競プロ

AtCoder Heuristic Contest 001に参加した！技育祭でchokudaiさんが「ヒューリスティックスコンは自分の書いたプログラムを育てるのが楽しい」のようなことを言っていたけれど、かなり実感した。

atcoder.jp

一週間のうち、最初の3日と最終日にがっつり取り組んだ。ICPC模擬地区があったり、技育祭が三日間あったりで取り組んでない時間のが長かった。

f:id:ntk_ta01:20210314222150p:plain

システス前46,877,146,209点で431位。

やったこと

Introduction to Heuristics Contestの解説がRustだったので、Rustで自分も取り組んだ。vis.rsからscoreやintersectをそのまま持ってこれたりして楽だった。

一日目

  • 1*1の正方形を作る 823090点
  • 外周までの距離で各長方形をソートしてから、各長方形を他の長方形と交差しないように拡大 453億点

二日目

  • 局所探索法を書く 目標面積より小さい長方形（公式ビジュアライザにおいてより青いものから）を拡大する 交差したらほかの長方形を縮小 456億点

三日目

  • 焼きなまし法を書く 456億点
  • 適当に長方形を選んで縮小する近傍を増やす

最終日

  • 縮小する近傍を減らす
  • バグがあったので直す 468億点

自分の提出↓

https://atcoder.jp/contests/ahc001/submissions?f.User=ntk_ta01atcoder.jp

あとは、グラフを書いたり

f:id:ntk_ta01:20210314212534p:plain

（焼きなまし法実装直後は解が全然動いてなくて困惑した）

f:id:ntk_ta01:20210314212601p:plain

（終盤はちゃんと動くようにグラフを見ながら温度いじってた）

GitHub（private）にコードとメモ上げたりしてた。最終日に改めて取り組むときに何やってたっけ？を思い出せてよかった。けれどやっぱりまだ使い方がちゃんとわかってない。

github.com

コンテスト終了直後、TLに大量に知見が流れていたのでまとめていきたい↓。

自分用人々の知見まとめ

hakomoさん

多スタートと山登り。なんか近傍で賢いことしてそう。

TERRYさん

※後日参加記を書くとのこと

長方形を破壊するみたいな発想出なかったな。最大長方形問題ってなに…？ビジュアライザが動くと楽しい（それぞれ途中結果を出力してパラパラ漫画的に作ってるらしい）。

TERRYさんによる初心者向け解説

www.terry-u16.net

めちゃくちゃ丁寧で参考になる。Tipsまで全部読むべき。さらに参加記も書くそうで…すごいな…。

takumiさん

※後日参加記を書くとのこと

ペナルティをつける、みたいなのやったことない（自分は重なりを許さないような実装をしました）。

じろうさん

shuu0914.hatenablog.com

自分も平行移動みたいなことをしたかったのだけれど、実装できなかった。引力？を発生させるみたいなのすごい。

さはらさん

知らないTree出てきた。自分は膨らませる近傍しか最終的に実装できなかったけれど、人々はいろいろな近傍を作っていてすごい。あと今回みたいな局所解にハマりやすい感じ（これ問題の性質ではなく自分の実力のせいだったりしますか？）だと多点スタートがやっぱり強そう。

ymatsux ACさん

考えてることとしてはこういうことがやりたかった。空白地帯を使ったり、ランダムな変形をいれるなどができなかったな。

可視化大事だな～～と感じたあたりまとめ

次回はこういうの作りたいな。

iwashiさん

iwashi31.hatenablog.com

序盤の順位表から考えたことやスコアの伸びた/伸びなかった方法など、かなり細かく一週間何をしていたか書かれていてめちゃくちゃ参考になる。

optさん

optさんだけ違う問題を解いているかのよう……。

ウォンバットさん

こういう方針もあるんだ、という気持ちに。

binさん

縮小や破壊、実装できずにちゃんとわかってなかったのでこういうことなのかやってみよう～～～と思った。

人々の知見が多すぎてまとめきれてない。Twitterの#AHC001 タグももうちょっと漁りたい。

次のAHC002も楽しむぞ～～～

AmongUsの戦績っぽい値を返すDiscordBot書いた

非競技プロ

まとめ

こういうやつ．

f:id:ntk_ta01:20210217104329p:plain

github.com

モチベ

最近は知り合いとAmong Usをやることが多い．

ふとゲーム内の統計を見たときに「これ勝率とか見れたらいいのにな～」と思って，簡単な計算をするBotを作った．

画像から文字を読み取るのをBotがやってくれるといいな～ってのが一番のモチベだった．

やったこと（画像から文字認識）

tesseractという文字を認識してくれるエンジンがあるみたいでこれをインストールしてきて，pyocrから利用した．

github.com

ここがモチベだったのだが，スクショの画像そのままだと文字を読み取る精度が低かった．

この画像に対して，

f:id:ntk_ta01:20210217110522p:plain

こう．

f:id:ntk_ta01:20210217110506p:plain

う～～～ん．微妙．Bot作るのやめるか？困った．

困ったのでtesseractのドキュメントのサンプル画像を見に行くと白背景かつ黒字のものが多く，似たような雰囲気にしたら精度が高くなると推測した． 実際，画像をグレースケール変換してからネガポジ反転させたら精度が高くなった．

f:id:ntk_ta01:20210217110847p:plain

いいじゃん！

やったこと（herokuでデプロイ）

あとはDiscord.pyのAPIリファレンスとにらめっこしながらコマンドを実装して，手元では動くようになった．常時動かしたいな～と思ったので，ググったらherokuに置くのがよさげと判明．使ったこともなかったのでアカウント作成してBotを稼働させる！

しかしすぐに動くことはなく，苦戦した． tesseractをherokuのほうに入れて，settingsのbuildpackからaptを使えるようにしたのまではよかった．けれどどうにもtesseractが上手く動いてなかった．

いろいろ探していたら似たようなことで困っている人がいた．

stackoverflow.com

回答にあったようにstack:set heroku-18 をしてみると…動いた！最高！

TESSDATA_PREFIXを環境変数として設定して完璧！完成！

こういう非競技プロの経験をもっと増やしていきたいぜ……．あとBotの機能ももう少し増やしたり，画像は背景が写らないようにした方がきちんと読み取れるのでそこをなんとかしたりしたい．

参考にした記事

Pythonで実用Discord Bot(discordpy解説) - Qiita

Discord Bot 最速チュートリアル【Python&Heroku&GitHub】 - Qiita

heroku 初級編 - GitHub から deploy してみよう - - Qiita

ABC123 D - Cake 123

競プロ

WriterがE869120さんとsquare1001さんの双子なので別解がたくさん紹介されている．公式解法3に近いが，途中でheapqに追加していくというよりは，次の候補を先に全部追加して解いた．

D - Cake 123

解法

制約からAとBの和は全列挙できるので，まずそれを行う．AとBの和の配列ABを降順ソートし，ABの先頭の要素とCの要素それぞれとの和を優先度付きキューに入れる．このとき，和とABのindexをペアにしてから入れる．

それからK回優先度付きキューから値を取り出す．i回目の操作では，i番目に大きいAとBとCの和が取り出せる．

ABのindexをインクリメントしてから，そのABとそのとき取り出しているCと和を取り，再び優先度付きキューに戻すことを繰り返す．

pythonのheapqを扱うときは，3要素以上のタプルをheapqに入れると計算時間が長くなることが多い．公式解法3よりもこちらの解法のがよさそうな気がする．またpythonのheapqは最小ヒープなので，マイナスをつけて最大要素を取り出せるようにする．

コード

def main():
    X, Y, Z, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()]
    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)
    AB.sort(reverse=True)
    from heapq import heappush, heappop
    ABC = []
    for c in C:
        heappush(ABC, (-(AB[0] + c), 0))  # 和, ABのindex
    ans = []
    while len(ans) < K:
        (s, idx) = heappop(ABC)
        s = -s
        ans.append(s)
        s -= AB[idx]
        idx += 1
        if idx < X*Y:
            s += AB[idx]
            heappush(ABC, (-s, idx))
    ans.sort(reverse=True)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

提出コードへのリンク

これだけたくさん別解があると強い人はどう早く解くのか気になる．50分くらいかかったので，水diffを解くスピードをもっと上げたい．強い人の提出見に行く．

見に行った．ねてるくんさんの提出が参考になって，2回に分けて全列挙するみたいな感じだった．シンプル．

ABC170 E - Smart Infants

競プロ

コンテスト後，公式解説に「multisetなどを用いることで高速に処理することができます」ってあったからPythonじゃ解けないのか？？と放置していた問題．2時間くらいかかっちゃったけど，なんとかC++で解けた．

E - Smart Infants

解法

シミュレーションをする．

各幼稚園ごとの幼児のレートのmultisetと，幼児iをキーとし，その幼児のレートと幼稚園のpairを要素としたmapと，また各幼稚園の一番レートの高い幼児を最強園児と呼ぶが，最強園児のレートのmultiset topを用意する（最後だけ説明の都合上，名前をつけた）．

各クエリにおいて，幼児cのレートをa，転園前の幼稚園をb，転園後の幼稚園をdとする．やることは以下の通り．

  • 転園前の幼稚園bの最強園児のレートをtopから削除する
  • 転園処理の消去部分を行う

  • もし転園前の幼稚園bにまだ幼児がいれば，転園前の幼稚園bの最強園児のレートをtopに挿入する

  • もし転園後の幼稚園dに幼児がいれば，転園後の幼稚園dの最強園児のレートをtopから削除する

  • 転園処理の挿入部分の処理を行う
  • 転園後の幼稚園dの最強園児のレートをtopに挿入する

実装の注意は，multisetから要素を消すときは，単純にeraseをするとすべて消えてしまうこと．

multiset<int> top;
top.insert(10);
top.insert(10);
top.erase(10); // 10が二つとも消える

一つだけ消したいときは，

multiset<int> top;
top.insert(10);
top.insert(10);
auto it = top.find(10);
if (it != top.end()) {
    top.erase(it);  // 10が一つだけ消える
}

とするといいらしい（下のACコードでは面倒なのでif文のところを書いていない）．

あと初めてのmultisetだったので知らなかったが，

*top.begin();  // 最小値
*top.rbegin();  // 最大値

らしい．

  • 追加サンプル1
3 3
20 30
10 30
10 30
2 500
1 500
1 30
  • 追加サンプル2
3 3
10 3
10 4
10 5
1 4
3 4
2 3

出力は全部10になる．

コード

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
using ll = long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

constexpr int INF = 1e9 + 7;
constexpr int _MAX = 200005;
/* -------------------------------------------------- */

void solve() {
    V<multiset<int>> T(_MAX);     // 園b : レートa
    map<int, pair<int, int>> mp;  // 幼児i : レートa, 所属園b
    multiset<int> top;            // 最強園児のレートの多重集合
    int n, q;
    cin >> n >> q;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        --b;
        T[b].insert(a);
        mp[i] = {a, b};
    }
    rep(i, _MAX) {
        if (!T[i].empty()) {
            int v = *T[i].rbegin();  // 園iのレートの最大値
            top.insert(v);
        }
    }

    int ans = *top.begin();  // 最強園児のレートの最小値
    int c, d;
    while (q--) {
        cin >> c >> d;
        --c;
        --d;
        auto [a, b] = mp[c];
        mp[c] = {a, d};

        int v = *T[b].rbegin();    // 園bの最強園児のレート
        top.erase(top.find(v));    // いったん消す
        T[b].erase(T[b].find(a));  // 転園処理（消去）
        if (!T[b].empty()) {
            v = *T[b].rbegin();  // 園bの最強園児のレート
            top.insert(v);
        }

        if (!T[d].empty()) {
            v = *T[d].rbegin();      // 園dの最強園児のレート
            top.erase(top.find(v));  // いったん消す
        }
        T[d].insert(a);      // 転園処理（挿入）
        v = *T[d].rbegin();  // 園dの最強園児のレート
        top.insert(v);

        ans = *top.begin();
        cout << ans << "\n";
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}

提出コードへのリンク

Pythonだとheapqを幼稚園の数くらい生やしてる人とかいたっぽい．

  • 今日知ったこどふぉ豆知識コーナー

から

f:id:ntk_ta01:20201111014250p:plain

フレンドのコドフォのAC数一覧が見られる！自分は今123AC．え　もっと増やしてえ～AC数の近いフレンドに負けません．今AC数が負けているフレンドもできるだけたくさん抜かしたいです．

ABC182 D - Wandering

競プロ

反省．ABC3完．レート-51．

D - Wandering

解法

問題文の，箇条書きの一行で表されるまとまった動作を，ここではステップと呼ぶ．

2回累積和を取った配列から，各ステップの開始時（終了時）の座標がわかる．あとは，各ステップ内で移動できる最大値を計算しておく．これは累積和の累積MAX．（各ステップの開始時の座標 ）+（各ステップで移動できる最大値）の最大値が答え．

これを理解するために（発想するために），考えたいことはすべての動作後のロボットの座標は，（各ステップの開始時の座標） + （各動作の移動距離の累積和）で表されるということ．例えば，サンプル2において各ステップの開始時の座標は，0, -2, -3, -1, 0である（手元で書くととてもよい）．ステップ1において，A_1だけ動かすときは， 0 + -2 = -2にロボットがいる．ステップ4において，A_1, A_2, A_3だけ動かすときは， -1 + (-2 + 1 + 3) = -1 + 2 = 1である．

今知りたいのは，ロボットの座標の最大値なので，（各ステップの開始時の座標） + （各動作の移動距離の累積和の最大値）を各ステップで計算し，そのうちの最大値を求めればよい．

計算量はO(N)である．

コード

def main():
    from itertools import accumulate
    N = int(input())
    A = [int(i) for i in input().split()]
    S = list(accumulate(A))
    T = list(accumulate([0] + S))

    M = list(accumulate(S, func=max))

    ans = 0
    for i in range(N):
        ans = max(ans, T[i] + M[i])
    print(ans)


if __name__ == '__main__':
    main()

提出コードへのリンク

ACを取ってからだれさんのツイートについて考えてみると，より問題への見通しがすっきりとした，だれさんありがとうございます…！

類題

(最小値, 累積和)みたいなのを使う問題．アルメリアさんの記事を読んで解説ACしたけど，まだその感覚が落としこめてない…．悔しい．

提出コードへのリンク

やっぱりABCを5，6完安定してできる実力が欲しい．なんとなく○○をやればいいかな～（今回だったら2回累積和を取ってみた），を実装してサンプルが合わないと思考が止まってしまうことを今からやめる！

手元でサンプルを実験して，ある程度正解である自信が得られてから実装に入りたい．また焦らずに，ていねいに考察ステップを踏むようにしたい．またすぬけさんの書いていた表がわかりやすくて，同じような表を書きたい．知りたい情報について，どう表現できるか丁寧に書くと，どこを高速化できるかわかりやすそう．

今回の内容が，考察に含まれた高難度（と言ってもABC-F）の問題もあるので，やっぱり新規ACを増やしていくことが大事．

そしてやっぱり，AtCoder青になりたいな．精進しよう．

ICPC2020 国内予選 模擬国内 参加記

その他

国内予選終わって一息ついて，シュークリーム食べながらダラダラ書いてます．日記です．

メンバーは oldlickくん（@oldlick_tech）とmiiifa（@miiifa1）で，Flip-Flop Cという名前の水水緑のチームでした．miiifaは研究室の同期でたまにコンテストに参加するぐらいですが，後輩のoldlickくんはコンテストに毎回参加していて僕よりレートが高いです（一回青タッチもしている！）．

模擬国内

まず模擬国内っていうのがあるんですよね．これTLのリツイートとかで回ってこなかったら存在が認知できませんでした．でも本番の半分くらいのチームは参加してたかも？（逆に言うと半分だけ？）．

このときの結果はAB2完でした．

f:id:ntk_ta01:20201025185748p:plain

国内予選突破ラインまで10位足りず…（79位 39位と書かれているチームが通過ラインです，間違っていなければふくぶちょーさんのチーム？）．

僕がやったこととしては，ABを通して，Dを見に行き，Dが解けないためCを見に行って終了という感じです．初めにoldlickくんがCをずっと考えていたのですが（終わってから気づいたんですが，かなり正解に近い方針だったぽい），ただ彼は実装が上手くいかなかったそうです．miiifaにはDのサンプルを作ってもらったりしていました．おかげで僕のDの解法が嘘だということがわかったりしました．

途中でoldlickくんの話を中途半端に聞いてCとDをバトンタッチしたりしていたのですが，もっとちゃんと考察を聞けばよかった……．二人のできたところやできなかったところを上手く合わせれば行けたかもしれませんでした．チーム戦の難しいところです．Cはテキトーにimos法とダイクストラを書いて，わからねえをして時間切れでした．1

国内予選まであと少し…なんとか3完をする実力はつけて本番に臨みたい，と思っていました．

国内予選までの精進

割と出ると決めるのが遅かったんですよね（模擬国内数日前？）．というのもうちの大学の最強ぷちくん（@petite_prog）が，「今年は出ないかな～」という感じだったので参加を見送るつもりでした．ただ，miiifaがそれなら俺が出る！とやる気に満ち溢れていて，そこで誘われたので参加を決めました．

そのためAOJ-ICPCなんて1mmもしていませんでした．画像は確か模擬国内前後のスクショです．

f:id:ntk_ta01:20201107002429p:plain

模擬国内でも感じたのですが，全然ICPCに慣れていなくて…やばい！と思ったのでできるだけ精進しました．一応，去年も国内予選は出たのですが…．まあまあやったつもりですが，TLの精進erに比べると全然できていないな…という感じがします．pitsuさんとLorentさんの切磋琢磨がまぶしい…．国内予選のときです．↓

f:id:ntk_ta01:20201107002633p:plain

ひそかにlongrunさんやshop_oneさんをライバルのところに入れて見ていました．longrunさんの精進を追い越す🔥🔥という気持ちでやっていました（これツイートして意識されたら追いつけないな…と思って黙っていました）．

あとは同じ大学のチーム集めてバチャを2，3回やりました．AOJのバチャの建て方も覚えました（最初わからなくて，でもどこにも記事がなかった気がする．需要あったら記事にしてもいいなと思っています）．

国内予選

当日です．16:30からのコンテストって，なんだかびっくりしませんか？お昼ご飯を14:30くらいに食べたりして，普段のABCと近い感じにリズムを合わせるなどしていました．

リハーサルのURLがほにゃららしていたみたいで，リハーサル開始直後からやろうとした人は困っていたみたいです？

ICPC，競プロがさかんでない大学でかつTwitterで情報取得してないと大変だなという感じがします（模擬国内然り，去年は何もわからなかったな～）．

開始直前はTLがだいぶ盛り上がっていて，つられてだいぶテンションがあがっていました．

しかし，いざ始まってみるとコンテストページが開けない．ICPCodeforcesか？

チームメンバーからも開けないとチャットで連絡をもらったので，通話してどうすればいいか確認．ちゃんと対応の書かれたメールを保存しておいて，よかった…．こどふぉがこどふぉったらTwitterで確認しますが，特定のサイト以外のwebアクセスが禁止されているので，審判団の方に電話．しかし，話し中…いや逆に全チームこうなっているのか？とすぐに気づき安心しました．

とりあえずちょっとしたらかけ直そうと思いながらF5連打してると，急に復旧．すぐに切り替えてコンテスト開始．開始直前の高まったテンションがいい感じに落ち着き，かえって集中して問題に取り組み始められました．

A問題をサクッとoldlickくんが通してくれて，僕はB問題を通しました．ちょっとだけもたついたかも．

それから3完する！！というのを意識して，3人でC問題に取り組みました．oldlickくんが書けそうだというので，パーッと書いてもらって，miiifaと僕がデバッグも手伝いつつ，時間がかかりそうな感じでしたがCを走らせました．そして，なんとかテストデータの実行が終わり（今更ですがICPCは普段のAtCoderと違って，手元での実行結果とプログラムを提出します．実質の実行時間制限は3時間），提出したところAC………．模擬国内では2完だったので，嬉しかったです．

そこからDやEを考えるもできずに，終わりました．結果は77位．

f:id:ntk_ta01:20201107005227p:plain

oldlickくんのおかげで思ったより高い順位になれたな～と思いました．模擬国内よりチーム数増えてるけど順位は上がったためです．しかも有志による現状のまとめを見るとこれはもしかして国内予選突破…？？？

ボーダーギリギリなこともあって公式アナウンスが出るまでは安心できませんが，この画像を見たときは喜びのあまり叫んでしまいました．いや，安心したいので一日でも早いアナウンスをお待ちしております…（ICPC運営の方は例年と違う状況やトラブルなどあって大変だったと思いますが，開催ありがとうございました…．リプライでもメールでも問い合わせをしたのですが，しっかりと返ってきて助かりました）．

（11/16 追記）国内予選突破しました！アジア地区大会では一問でも多く解けるように頑張ります！

f:id:ntk_ta01:20201116154522p:plain

ICPC参加した方もお疲れさまでした！

  1. そのときのC問題 https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/3203↩