2019-10-19

第30回全国高等専門学校プログラミングコンテスト参加記

Lafolia です。都立品川代表として高専プロコン競技部門に参加しました。結果は2回戦敗退です。
弊校の半年間の虚無を綴ります。

問題公開以前
4 月
5 月
6 月
7 月
8 月
9 月
10 月
本選
感想
来年
リポジトリ

問題公開以前

先輩と「前回は大炎上しましたけど2年連続来ますかね？」「さすがに来ないやろw」とか盛大にフラグを立てる。

4 月

とりあえずルールを読む。2年連続同じ問題でした。絶望。
読み進めていくと、去年の ~~無駄な~~ 人力が消え、エージェントの数だけが増えたことが分かる。

この段階でモチベが限りなく 0 になる。

先輩が早々とソルバ書くことを拒否したため、UI を全てぶん投げて僕一人でソルバを書くことに。
僕自身も書く気が全く起きなかったので、とりあえず Google C++ Style Guide に則って書くことにする。

5 月

去年のプログラムを漁った結果、謎最適化が横行しており書いた本人(僕ではない)ですらそれがどうなっているかを把握できていなかったので流用を断念。おとなしく自力で実装します。

スタイルガイドに適当な相槌を入れながら実装を進める。書きづらいね。
到底速いプログラムができるとは思えないが(それはそう?)、初読での可読性が向上する点は評価していい(そもそも競プロ like なプログラムはそれを犠牲にしやすい)。

6 月

完成。案の定遅い。
ビームサーチは定数倍高速化がものを言うと思ったので(あと単純に書く気が失せた)、全体の設計を開始する。

「盤面データを直接 priority_queue に入れるよりも適当な key で保存して、 key と evaluation だけ priority_queue に入れた方が速そう」とか、「大量に呼び出される箇所のオブジェクトは static にしたほうが速そう」とか実験して遊び始める。

7 月

無。記憶がないけど Github の Network が言うんだから間違いない。

多分 6 月の遊びを続けてたんじゃないですかね。

8 月

あと 2ヶ月しかないじゃん、やばい。

9 月

覚醒する(モチベがあるとは言っていない)。

とりあえず(ちゃんと速い)普通のビームサーチを書く。書き終える。

書き終えたのでエージェントの数が多くても対応できるのを書く。書き終える。

検証する。得点のみの評価でまあまあ動くことがわかる。
逆に得点に関係しない評価を強くすると一気に雑魚くなるので虚無になる。

この段階でできることがビームサーチの改善と評価関数の作成・パラメータサーチだけだったので後者をやる。得点に関係しない評価は弱くすればそれなりの効果を持つのが存在したのでちょっとうれしくなる。

10 月

評価関数作成の進捗が全くでなくなったのでパラメータサーチをする。

たまにビームサーチの改善案が思いつくので実装すると、特別強くならないことがわかって悲しくなる。

本選

強い AI が作れないまま移動が始まる。

1日目(移動)

新幹線に揺られて鹿児島に。

移動の都合上 40 分だけ空き時間が出たので駅周辺をぐるっとする。

都城に着弾する。

お腹が空いたのでラーメンを食べる。

ホテル内に岩盤浴の設備があったので行く。
これすごかったです。90 分暇だから有益なこと考えてようと思ったら何も考えられずに時間が過ぎ去ってた。

２日目(受付)

宮崎駅に行って SUGOCA と土産を買う。

寝る。

受付に行く。

最後のパラメータサーチをする。

3日目(大会1日目)

予行練習で周りがほぼ動かなくてびっくりする。

通信も先輩にぶん投げてたのでなにか言える立場にないが、流石に事故りすぎでしょみたいな気持ち。
やっぱり鯖は仕様のみを公開するんじゃなくて実態も公開したほうが事故が減って嬉しいと思います。

1st ステージで勝つ。 2チーム動いてなかったのでまぁみたいな気持ち。
ちなみにリーグ内には熊本(熊本)さんがいました。全勝したので実質弊校も特別賞だと思います。

ホテルに戻って意識が落ちる。他校の人と夜飯を食べる約束を盛大にすっぽかす。
大変申し訳ありませんでした。

4日目(大会2日目)

２nd ステージで弓削高専に第1試合に勝つ。第2試合で負ける。
得点差で敗退する。つらい。
乱戦になると弱い話はあったからなぁ。

ホテルのフロントで観戦する(Wifi が飛んでるので)。
東京が勝つ。会いに行ってひたすら褒め称える。

帰宅。

感想

改めて振り返ると全体的に虚無をしていることがわかります。まともに開発してたの 9 月からじゃん。よくないね。

敗因は "人力を徹底的に排他した" ことだと思います。ぶっちゃけプログラムの出来は敵・盤面との相性があり、最終的にはじゃんけんになるので本質ではないと思ってます。
東京高専さんの方針は弊校も案が出たんですけど、僕自身がプログラムのみで勝負したい気持ちが強かったので採用しませんでした。
僕のこの考えは明らかに高専プロコンにマッチしてなくて、(唯一?)そのへん込で実装してしっかりと優勝した東京高専さんは本当に偉いと思いました。
本当に、AI が人間に勝てないと判明した段階で素直に人力を交えるべきでした。

ところで僕はゲーム AI を作って戦わせることに結構憧れがあったんですよね。
具体的には高知大会の問題をアーカイブで観て「俺もやりたい！」ってなりました。

で、ゲーム AI を二年連続でやった今の感想は、「もうゲーム AI なんか書きたくない」です。
開発してて一番つらかったのが "人間より強い AI が作れない" ことと "ある程度からは目に見える進捗がなくなる"ことで、2 年連続で(ほぼ)同じ問題をやったことも相まって軽くトラウマになってます。
CodinGame やるの楽しそうと思ってた時期もあったんですけど、しばらくは絶対やらないです。

来年

とりあえず次大会までの半年間は傷を癒やすために適当な開発をして遊ぶつもりです。
来年は最適化問題が出るので(決めつけ)(ホントお願いします)、次回は優勝できるようにモチベ高めてがんばります。人力もちゃんと考慮するようにします。

リポジトリ

せっかくなので公開したリポジトリも貼っておきます。

https://github.com/Lafolia13/Zero_Sum_Ranges

2019-08-18

AtCoder青色になるまでにやったこと

はじめに

Lafoliaです。ついに青色になりました！！！！

大したことはしてない(というか何もしてないに等しい)ですが、青色になるまでにやったことをまとめます。

f:id:Lafolia:20190818233508p:plain

一個目の上り坂

ぶっちゃけAtCoder水色になるまでにやったことの残り香です。このあたりでユーザ数のインフレが始まってますが、企業コン・AGCの参加者はまだ増えておらず、400早解きでも十分に高パフォーマンスが取れたのでそれなりにレートが上がりました。
6月2日(ちなみに僕の誕生日です(聞いてない))のAGC時点でだいぶ青に近くなったのですが、ここで令和以降の大変革、ABCの変化が僕を襲います。

下り坂

平成ABCの出題数が4問(D問題は400-700点)であったのに対し、令和ABCは出題数が6問、配点は100点刻みになりました。また、Rated対象の上限が水色から青色になりました。
500,600は普通に難しいので解けません。あと400点問題のAC者数が3000超えるとかほんとワケワカメ。冷える。

青まで

まあぶっちゃけコンテスト出続ければ慣れます(おい)。
600は普通に無理ですが、500は400よりちょっと頭を使うと解ける難易度で、必要知識があまり変わらないため打率は低いですが解けるようになりました。
あとすごい嬉しかったのが500に最短経路問題が入ったことで、とても嬉しい。なぜなら解けるから。
これに限らず500点問題には400以下で出せなかったアルゴリズムのド典型問題が入るみたいな話をどこかで見ました。

あとは企業コンとAGCで成功をして、最後にABCで早解き5完に成功して青色になりました。

必要そうなこと

当たり前(と勝手に思っています)ですが、レートを上げるには次の二点が必要です。

データ構造・アルゴリズムを学ぶ
考察力・典型力を高める

1に関して、問題を解くよりは蟻本とかを読んだほうがいい気がします。完全習得せずとも、概要と使い所さえ知っていればWebでソースを調べ貼り付ければ通るみたいな問題もそれなりにあるはずです。少なくとも青まではそれでいける気がします。

逆に2についてはひたすら問題を解くことが大事だと思います。解くに考察力を高める利点として、AGCの700,800点問題で考察メインのものを解くことができるようになります。これを解くだけで青パフォが確定したりするのでだいぶ大きいです。
あとは状況を変化させるタイプの問題では実験することを覚えるとだいぶ勝率が上がると思います。

最後に

今日SuperCon2019本選の前日なんですけど、大会前に大成功して気分がめっちゃいいです。本選がんばりまうｓ。

補足

僕が青になるまでに解いたAGCの考察メインな高得点問題です

2019-06-19

SuperCon予選に落ちた話(追記あり)

コンパイラを合わせてなかったので死にました！！！！！！！！！！ f:id:Lafolia:20190619144300p:plain

array<array, T>>のイニシャライザが無いってまじでなんなんだ

来年度以降の参加者へ

環境を絶対に合わせよう！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

追記

受かってました！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

2019-06-14

SuperCon2019予選参加記

はじめに

おはこんばんにちは。テストが死んだLafoliaです。SuperCon予選にでました。実行時間はサンプルに対して0.50sec(4GHz環境)でした。やったことを書きます。

問題発表前

テスト直前って知ってますか？勉強したくないので勉強はしません。

発表当日

問題文を読みました。ディープラーニングさせたいらしいです。日本語が読めません。おわり。

ちょっと後

改めて問題を読むと諸々の設定がめちゃくちゃなことがわかります。大きな特徴は次の2点で、

活性化関数は0/1のステップ関数
重みは-1/1

です。これどういうことかというと、勾配が計算できません。つまりは逆伝播法が使えません重みが2値なのでシグモイドとかで近似するのも多分無理です。この方法で学習させるつもりがないことをなんとなく察しました。

やったこと

もうちょっと真面目に問題文を読むと、貪欲法(山登り法ですね)で解けって書いてありました。実装すると解ける(テストケースの結合がランダムに作られてるので解けないわけがない)ので、これを高速化すればいい気持ちになりました。

高速化

画期的なアルゴリズムを求めてくる声を聞きながらの高速化パートです。下にプログラムを貼ってあるので参考にしてください。

まずは高速化の初歩であるループ外しをします。早くなります。

次に計算値の再利用をします。n層とn+1層をつなぐ結合の重みを変えた場合、それ以前の層までの計算値は変化しないので、ここから計算するとシミュレーションが大幅に高速化されます。

(ここで何も思いつかなくなったので提出をしてしまいました。)

最後に変更する結合をランダムに選ぶことをやめます。ある結合が選ばれる回数の期待値は200回(結合の数が200コ)なので、この程度なら全探索を何回かやればいい気がします。乱数を得るのにも時間がかかるので、これでちょっとだけ早くなります。

(これ締切日の0時に出したんですけど再提出って受理されるんですかね？)

ここまでで画期的なアルゴリズムを何も思いつかないので実質的に敗北です。かなしいね。

ソースコード

はい

#include <array>
#include "sc1.h"

using namespace std;

const int_fast32_t complete = 6;
const int_fast32_t all_score = (4+complete)*10;
const array<int_fast32_t, 6> many = {6, 7, 7, 7, 7, 4};
array<array<bool,6>, 10> in;
array<array<bool,4>, 10> out;
array<array<array<int_fast32_t, 7>, 7>, 5> ans = {};
array<array<array<int_fast32_t, 7>, 6>, 10> check = {};

inline void sum(const int_fast32_t &id, const int_fast32_t &net, const int_fast32_t &&from) {
    check[id][net][0] += ans[net-1][from][0];
    check[id][net][1] += ans[net-1][from][1];
    check[id][net][2] += ans[net-1][from][2];
    check[id][net][3] += ans[net-1][from][3];
    check[id][net][4] += ans[net-1][from][4];
    check[id][net][5] += ans[net-1][from][5];
    check[id][net][6] += ans[net-1][from][6];

    return;
}

inline void sum(const int_fast32_t &id, const int_fast32_t &net) {
    if (check[id][net-1][0] > 0) sum(id, net, 0);
    if (check[id][net-1][1] > 0) sum(id, net, 1);
    if (check[id][net-1][2] > 0) sum(id, net, 2);
    if (check[id][net-1][3] > 0) sum(id, net, 3);
    if (check[id][net-1][4] > 0) sum(id, net, 4);
    if (check[id][net-1][5] > 0) sum(id, net, 5);
    if (check[id][net-1][6] > 0) sum(id, net, 6);

    return;
}


inline const int_fast32_t calc(const int_fast32_t &id) {
    int_fast32_t &&ret = ((check[id][5][0] > 0) == out[id][0]) +
                         ((check[id][5][1] > 0) == out[id][1]) +
                         ((check[id][5][2] > 0) == out[id][2]) +
                         ((check[id][5][3] > 0) == out[id][3]);

    return ret + (ret == 4) * complete;
}

inline void reset(const int_fast32_t &id, const int_fast32_t &net) {
    check[id][net][0] ^= check[id][net][0];
    check[id][net][1] ^= check[id][net][1];
    check[id][net][2] ^= check[id][net][2];
    check[id][net][3] ^= check[id][net][3];
    check[id][net][4] ^= check[id][net][4];
    check[id][net][5] ^= check[id][net][5];
    check[id][net][6] ^= check[id][net][6];

    return;
}

const int_fast32_t Simulation(const int_fast32_t &n) {
    int_fast32_t ret, id, net;
    ret = 0;
    for (id = 0; id != 10; ++id) {
        for (net = n+1; net != 6; ++net) {
            reset(id, net);
            sum(id, net);
        }

        ret += calc(id);
    }

    return ret;
}

inline void makeStartState() {
    int_fast32_t net, from, to, id;
    for (net = 0; net != 5; ++net) {
        for (from = 0; from != many[net]; ++from) {
            for (to = 0; to != many[net+1]; ++to) {
                ans[net][from][to] = (genrand_int31()&1) ? 1 : -1;
            }
        }
    }

    for (id = 0; id < 10; ++id) {
        for (from = 0; from < 6; ++from)
            check[id][0][from] = in[id][from];
    }

    return;
}

void Solve() {
    int_fast32_t net, from, to, score, maxi, change, search, turn;

    makeStartState();
    net = 0;
    score = Simulation(net);
    maxi = score;

    turn = 30;
    search = 5;
    while (--turn > 0 && score != all_score) {
        for (net = 0; net < 5; ++net) {
            for (from = 0; from < many[net]; ++from) {
                for (to = 0; to < many[net+1]; ++to) {
                    ans[net][from][to] *= -1;
                    search = min(search, net);
                    change = Simulation(search);
                    if (change > score) {
                        score = change;
                        maxi = max(maxi, change);
                        search = 5;
                        turn += 5;
                    } else if (change < score) {
                        ans[net][from][to] *= -1;
                    }

                    if (score == all_score) {
                        to = 9, from = 9, net = 4;
                    }
                }
            }
        }
    }

    if (score != all_score)
        return Solve();

    return;
}

int main() {
    SC_input();

    int_fast32_t problem, data, shift, net, to, from, cnt;
    init_genrand(614);
    for (problem = 0; problem < SC_n; ++problem) {
        for (data = 0; data < SC_NDATA; data += 2) {
            for (shift = 0; shift < 6; ++shift)
                in[data/2][shift] = (SC_prob[problem][data]>>shift)&1;
            for (shift = 0; shift < 4; ++shift)
                out[data/2][shift] = (SC_prob[problem][data+1]>>shift)&1;
        }

        Solve();
        cnt = 0;
        for (net = 0; net < 5; ++net)
            for (to = 0; to < many[net+1]; ++to)
                for (from = 0; from < many[net]; ++from)
                    SC_J[cnt++] = ans[net][from][to];
        SC_output();
    }

    return 0;
}

おわりに

ボーダー何秒だろうね。秒だとCPUの影響受けまくりなのでシミュレーション回数でアンケ取りたいお気持ち。

予選通ったらよろしくお願いしまうs。(通ってくれ)

2019-03-09

AtCoder水色になるまでにやったこと

はじめに

Lafoliaです。ようやっと水色になれました。競プロerの慣習として水色になったらそれまでの経緯とやったことを書くらしいので書きます。
前半はただの駄文なので読み飛ばしてください。

f:id:Lafolia:20190309232536p:plain

第一次奮闘期

本格的にやろうかなと思ったのはJOI2017/2018予選で300＋部分点で死んだことです。拡張Dijkstraを思い浮かばず森林伐採ができなかったです。
今から思えば森林伐採の解説読んでDijkstraの応用性の高さを知ったのが僕がDijkstraを好きになった理由だと思います。
学校のお勉強は割とできたほうなので悔しくなりました。やろうとなりました。

気がついたら年度が終わってました。

AtCoderやりましょうとなりました。弊部では1年でAOJのIntroductionをやっているので問題を解くことには慣れており、比較的すぐに300まで解けるようになりました。

休止期

PCKがありましたが大したことはしてなかった気がします。高専プロコンが始まりました。これを言い訳に全く精進せず、コンテストに出るだけをしていました。

高専プロコンが終わりました。

第二次奮闘期

高専プロコンで東京高専の同級生な某々と知り合いました(これは厳密には夏ですが)。やつら強いです。僕は単純なやつなので触発されました。
やりたい気持ちになっていたところ、ちょうどすぐJOI2018/2019が迫ってきたのでやろうとなりました。やります。400難しいです。文字列わからん。未だに分からん。

解説見ながら解ける問題は解きます。解いたので自力が上がります。このあたりでABC全完ができるようになってきました。JOJOにレートも上がります。

JOI予選が通りました。

JOI本選で大爆死しました。

気がついたら年度が終わろうとしています。

春休みになったので圧倒的成長をしたくなり、300を埋めます。埋めました。ABCに出ます。全完します。水色になりました！！！！

水色になるために

上にも書いた気がしますが過去問を埋めるのは非常に重要だったと思います。300点が9割で解けても1割で死ぬので過去の100問くらいを全部埋めて問題に慣れましょう。
ぱっと見で分からない問題で思考停止しないよう耐性をつけましょう。

あと300早解きでも水色になれるらしいですが、多分すごいスローペースになるので400も解けるようにするべきだと思います。

実際問題300と400では基本的には使うアルゴリズムとかデータ構造が違うだけ(だと思っている)なので、どっちも埋めるのがいいと思います。
多分300埋めてるだけだと400を解けるようにはならないんじゃないですかね？出題がまず違うので

400もいくつかに分類できるので、何問か解けばいわゆる典型力が身につくと思います。身についたら本番で出た時に勝てます。レートが上がります。

ということで水色になりました。

300点問題

その他がいっぱいあるきがしますが、基本的には次の問題が出る気がします。文字列は僕の管轄外なので知りません。

GCD(最大公約数)
ソートして総和
全探索
連想配列

GCDはユークリッドの互除法を実装すればいいです。そのへんに転がってます。数列があって、任意の2要素を互いに引いてく動作があれば大抵GCDです。わからなくても適当に書いてサンプルが合ってたらAC出ることが多いです。

一番大きいのを除外するとかK個選ぶ時の最大とかの問題はソートをして任意個足すとかv[0]だけ引くとかするといけます。

最近はbit全探索がよくでる気がします。再帰全探索を書けるようにしましょう。n進数の表現と復元が理解できればあとは評価計算するだけです。

種類数とかN個選ぶコストの最小とかはmapにぶちこんでsizeしたり上からN個になるまで足したりとかしてくと解けます。

400点問題

ぼくもまだわからないです...(ごめんなさい)。ただ僕の場合はxorでbitをこねこねする問題とかCよりちょっとむずかしい考察問題は解けるので僕はこれで稼ぎました。

注意(？)

上の方に貼ってある僕のレート推移を見ると、大きく下がっている場所があります。ここ全部AGCです。

AGCは1完しかできない場合、水色を目指す人は早解き以外人権がありません(怒られそう)。WAなどもってのほかです。
あと点数にも注意です。ABCとは配点の基準が異なるため、200で累積和とか余裕であります。犠牲者は大量にいるはずです。
僕はAGCのほぼ全てで失敗したためこのような面白いグラフになりました。ちなみにこの時のパフォは負の値になってます。

AGCに出るときは覚悟を決めましょう。出ない選択肢もありだと思ってます。実際次のAGCで死んだら緑に戻るので僕今とても怖いです。

終わりに

いかがでしたか?(以下略)

そんなこんなでようやく水色になれました。青になるには500,600が解けなきゃいけないっぽいので去年一昨年よりも強い気持ちで精進していこうと思います。停滞していたら多分精進してないので、僕よりレートが高い人は気軽にマウントをとってください。あまり間隔が狭いといじけますが、ある程度だったらやる気が出る気がします。

あとこれ読み返すのめんどくさくなるほど読みにくいのでいつか修正します。

2019-02-11

JOI2018/2019 本選参加記

はじめに

Lafoliaです。JOI本選に参加したので参加記を書きます。

前日

人々が準備してるのをTwitterで見ながらUnionFind、SegmentTreeを空で書くやつの確認をしていました。
UnionFindはrankを考えないやつだったら秒で書けるので問題なくて、SegmentTreeは某に教えてもらっためちゃんこ書きやすい素晴らしいやつを覚えたので勝ちでした。

1日目

当日に準備をするをしてました。東京23区民のアドバンテージは活かしていきます。
お昼ごろに最寄りのTXのホームで某を待ちました。思ったより早く来すぎてしまい、1時間弱ホームの椅子に座ってるやばいやつをしていました。ここで、冬に1時間じっとしているのは自殺行為だという知見を得ました。某がくるのがもう少し遅かったら凍死していたかもしれません。
某と合流したら人がいっぱいいました。TLerが本当に人間だと判明したのは大きかったです。謎の感動を覚えました。
つくば駅に着くばをしました。誰もスマホで会場の場所を確認しないまま歩いていたら、なぜか遠回りをすることになりました。これは本選2日間での一番の謎といっていいでしょう。会場について受付をして、IAちゃんのクリアファイルをもらいました。服装が変わってます。サッカー日本代表みたいになっていました。ぼくはIA(サッカー)よりもIA(JK)が好きなのですこし悲しい気持ちになりました。

プラクティスをしました。vimrcは必須なのだけ覚えたので操作自体に困ることはありませんでした。ただ、キータッチが重くて(伝われ)うまくタイプすることができず、つらい気持ちになりました。molokaiがないのもつらかったです。そろそろこういう大会はエディタの更新をしてもいいと思うんです。参加者が希望するエディタと補完に関する最低限のプラグインは用意してほしい気持ちです。エディタの違いで有利不利が生まれるはずはないので、認めてほしいです。
全完はしました。バグにうんうんうなりながら適当に書いたら通ります。ダーツで4回投げますとか半分全列挙をしてくださいと書いてあるようなものです。僕は解くのが遅いので、周りで終わった人たちが雑談し始めて人権がなかったです。具体的には2個くらい前の席が双子なので、つよつよの周りにつよつよが集まってつよい話をしていたので悲しい気持ちでした。開成と筑駒の余裕発言を耳にしながら問題を解く僕の気持ちがわかりますか？
ご飯を食べました。早いもの勝ちルール怖いです。ケーキ美味しかった。コロッケも美味しかったです。みんプロで水色になって水色コーダーとして本選に参加するとかのたまった記憶がありますが、察してください。素数大富豪を1プレイだけさせていただいて就寝。

高垣楓

自己紹介で軽く楓さんを布教するをしました。cv.早見沙織ということで歌がまじで神なのでこれを見ている皆さんは「こいかぜ」を聴きましょう。何を間違ったのかオリジナル合わせて3バージョン(厳密には4バージョン)あるので大変素晴らしいです。聴きましょう。
デュエット曲としては「Nocturne」があります。この曲は相方の川島瑞樹(cv.東山奈央)と早見さんの声の親和性が高すぎるので大変エモいです。
最近の曲は「Pretty Liar」ですね。相方は速水奏(cv.飯田友子)です。この曲はCDよりもゲーム楽曲のほうが僕は好きです(歌う箇所が入れ替わってます)。Aメロラストのフォールがたまらないです。ぶわってなる。

2日目

天才なので起床は完璧です。完璧すぎて二度寝のスケジューリングまでできます。部屋の片付けも朝飯前(ここダブルミーニング)に終わらせました。当然朝食を最初に食べ始めたのも僕です。完食もたぶん僕が最速です。朝食ガチ勢ではありません。趣味です。

本選会場に戻ってきました。競技をします。1問目を解きました。2問目が解けません。分かりません。諦めて全探索を書きます。通りません。なんでですか？発狂します。発狂しながら残りの問題を見ます。部分点が取れそうでも発狂しているので当然やりません。2問目に戻ります。できません。1完部分点0で競技が終わります。

解説を聞きます。壮大な誤読をしていることに気づきました。絵の大きさは大きい順でなくてもいいんです。悲しいです。あと4の考察が半分のところまで詰められていることを知りました。まともな思考なら解けたんじゃないですかね？流石に無理か。

秋葉原にみんなで帰ります。ゲームすると思ってたんですけどみんな解散してしまったので一人でCHUNITHMをしました。バンキシャをSしました。うれしい。

帰宅しました。2問目を解きます。秒で解けました。4問目を解きます。1時間程度で解けました。就寝。

感想

人に会えたので楽しかったです。ただ、僕は何も考えないで生きている人間なので、本選落ちの悲しみの声を聞いていると心に結構刺さりました。JOI本選はああいった情熱をもった人たちがいるべき場所なので、僕みたいなやつがいて申し訳なくなりました。

それはともかく、同年代のつよつよの人と会ってお話することができて本当に楽しかったです。弊校には競プロerが全くと言っていいほどいないので、80人全員がつよつよなあの環境は感動を覚えました。
また皆さんと会いたい気持ちが大変強いです。僕はもうJOI参加資格がなくなるので、会える機会は企業コンとかPCKとかに限られます。オンサイトに出れるほど強くなりたいと思います。JOIをあまり重要視できていない分、この二日間はモチベーションが上がり続ける日々でした。

これは完全に余談ですが4問目が個人的にだいぶ好きなやつなので後日解説記事を書きます(本選後の解説の劣化にしかならないと思いますが)。

2018-12-13

第18回JOI予選参加記

はじめに

僕も人々みたいに参加記とか解説とか書いてみたい気持ちになったのでやります。

JOI(日本情報オリンピック)予選に参加しました。結果は410点。配点は100-100-100-100-10-0です。当日の流れとか各問題について書きます。

予選開始まで

前日はABC115を全完して気持ちよくなったのでセグ木の勉強をしてました。厳密にはセグ木使って区間最大と区間最小を取れるようになりたかったので記事を探してました。Tsuta_Jさんのが最高にわかりやすかったのでもし本番で出たら貼り付けりゃいいかなぁとか思いながら寝ました。

予選中

早解きする気になれなかったので20分くらいかけて3問目までを解きました。4問目は簡単だなぁとか思ってたんですけど実装バグらせまくって辛い気持ちになりました。1時間半くらいかってます。

ここからが今回良くなかったところなんですけど、5問目をみて「あっ区間最大じゃん！！」とか思ってよく考えないまま脳死で貼り付けてmaxとる形に改変しました。なんでスニペット作って置かなかったんですかね。改変自体にもそれなりに時間がかかってました。多分20分くらい。そのあと思ったことを実装してたんですけど思いっきり間違ってたんでサンプルが合いません。絶望。残り時間が1時間を切りました。

悲しい気持ちで全探を書きました。残り時間30分。6問目を読む。全探を一から書く。バグる。予選が終わる。

予選後

ついったーを見て人々が416点ばかり取ってるのをみて悲しい気持ちになりました。TLの強い人々はみんなボーダーは416点だとか言ってるのでもっと悲しい気持ちになりました。でも実際のところボーダーは最大でも400だと思ってたので実はそこまで絶望してませんでした。

f:id:Lafolia:20181213164512p:plain 予選1ヶ月前位から封印していたCHUNITHMをやりに行きました。炎上炎上炎上炎上！！！ww
改めてCHUNITHMは楽しいねとなりました。レートが13.80になりました。金レまでがんばります。

解説

既出しまくりですし公式も出してますが一応解いたところまでは解法を書きます。

1問目

1日ずつシミュレーションをしました。forで回してカウンタ変数は外においておくと楽でいい感じです。カウンタの値-1が答えになります。

2問目

1マス進めたいコマとその次のコマを調べていけば大丈夫です。

次のコマが進めるコマのマス+1にいたらダメ。
今いるマスが2019だったらダメ。
これ以外は進めていい。

これだけ書けば通ります。

3問目

1次元DPでやりました。s[i]とs[i-1]が同じ時s[i] = s[i-1]、違うときs[i] = max(s[i-1], s[i-2]+1)をするといい感じになります。多分1,2問目よりも解くの早かったです。

4問目

ぐっと睨んだら水位の上昇で島の数は増えた後減ることがわかったので三分探索をしました。三分探索とは凸関数の極値を高速に調べられるすごいやつです。詳しくは調べてください。更に考えると島の増減が起きるのはt=各区域の高さの時だけなので、最大で10⁵種類の高さについて探索すればいいです。
三分探索は同じ値が連続する部分があると上手くいかない(らしい)のですが、それを知らなかったためWAをし続けました。つらかったです。どれくらいつらかったかはこれを見れば分かると思います。
f:id:Lafolia:20181213164602p:plain 最終的に出した高さから±いくらかの高さを全部調べてその最大を取るとかいう筋肉をしたら通ったので筋肉は強いです。

完全な余談なんですけど、この問題解法が結構あるみたいで、解き方で日本が出現したり沈没したりするのでTLが賑やかだったんですけど、僕の場合は日本浮沈でいいですかね？

5問目

bit全探索をすると10点がもらえます。

感想

部分点を先に取るべきなのは知ってたし後輩氏にも言った気がするのですが、準備してた(実際準備できていない)セグ木を使える問題に興奮して時間を消費してしまったのが本当に良くなかったと思います。そもそもこの5問目はセグ木を貼った後は簡単なDPだったみたいなので気づけなかったことが悲しいです。Aランクボーダーは391点で本戦行ける事になったので本戦では今度こそ先に部分点を取りにに行こうと思います。

ここまで読んでくださりありがとうございました
PS:本戦erエンカお願いします！！