2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

JOI本選参戦記

2
Last updated at Posted at 2022-02-14

自己紹介

 はじめまして、中2のkentandです。AtcoderIDもkentandです。本選時点では水色で、Ratingは1308です。今回はめでたくJOI本選に出場することができたので参戦記を書きます。ブログは初めてなので稚拙な文章ですがご容赦ください。

まずは成績

問題名 自分の得点/満点
問題1 インターカステラ― 100/100
問題2 自習 100/100
問題3 選挙で勝とう 5/100
問題4 鉄道旅行2 8/100
問題5 砂の城2 19/100

本選までにしたこと

 せっかく2次予選は通過したのに、本選で0完は目も当てられないので少し難易度5~7を解きました。これが本選直前での解いた問題数です。しょぼいですね...
スクリーンショット 2022-02-13 234340.png
来年はもっと解いてから参加したいと思います。

1日目

事前練習終了

 まずは8:00に事前練習が終了します。本選で使うサーバーであるCMSに慣れるために本番と同じ環境で去年の問題を解くことができます。筆者は「まあいけるやろ!」と思い前日まで通しでやらなかったら難易度7の1問目が解けずビビりました()

ガイダンス

 開会式動画で思ったよりネタに走った人が多くてとても面白かったです。こんなことなら少しくらいネタに振った方がよかったかもしれません。

プラクティス

 本番と同じくらいの難度の物が出ると思い震えていましたが、CMSに慣れるためのものだったのでそこまで難しくなく安心しました。問題もどこかで見たようなものでしたが、IOIOIだけは許さねぇ!!!(通せませんでした)

ゲーム大会

 Amoung Usをしました。楽しかったです。

2日目

本番の本選競技です。朝9:00~でしたが起床試験は無事突破しました。

タイムテーブル

9:00 本選開始
9:15 簡単やな??と思いつつ1問目を撃破
9:30 2問目の部分点狙いで提出 WAを出す
9:45? 間違いに気づく 部分点Get
~10:30 2問目の満点解法が降ってくるもWA 時間を溶かす ピンチ!!
~11:30 とりあえず飛ばして3問目と4問目と5問目の部分点をGet
12:30 2問目のオーバーフローに気づき修正 ACする 危なかった...
~13:00 3問目を考えるもわからず...

各問題の感想

1問目

 「この個数からこの個数まではもともと $A_i$の長さだったカステラ」という情報を持った配列$B$をそれぞれのクエリについて$X_i$で二分探索すれば通ります。計算量は$O(NlogN)$です。 かんたん

2問目

 オーバーフロー許さねぇ!!!

 方針としては決め打ち二分探索を使います。決め打ち二分探索で目標理解度を決めます。そして$N$教科それぞれについて、目標理解度を達成する最小限の学習をしたときに他の教科のマスに浸食しないといけない、あるいは余るコマ数を求めて浸食するコマ数が余るコマ数より多ければ$×$ そうでなければ$○$といった解法をすると通ります。これで計算量はだいたい$O(Nlog$ ありうる理解度の最大値$)$です。決め打ち二分探索が見た瞬間分かったのは自分の中では良かったと思っています。

 しかし、このとき浸食するマスが非常に大きくなることがあり、それでオーバーフローします。これに気づくまでに1時間くらいかかりました。気づいた後は必要なコマ数が$N×M$を越えそうだったらすぐにNGにするという処理を入れると通りました。

# include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF=5000000000000000000;

int main(){
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    for(int i = 0; i < N; i++) cin >> B[i];
    ll ok = 0, ng = INF;
    for(int i = 0; i < 100; i++){
        ll mid = (ok + ng) / 2;
        ll amari = 0, hituyou = 0;
        bool b = true;
        for(int j = 0; j < N; j++){
            if(A[j] > B[j]){
                if(M * A[j] < mid){
                    ll cn = (mid - M * A[j]) / B[j];
                    if((mid - M * A[j]) % B[j] != 0) cn++;
                    hituyou += cn;//オーバーフローする
                }else{
                    ll cn = mid / A[j];
                    if(mid % A[j] != 0) cn++;
                    amari += M - cn;
                }
            }else{
                amari += M;
                ll cn = mid / B[j];
                if(mid % B[j] != 0) cn++;
                hituyou += cn;//オーバーフローする
            }
        }
        if(amari >= hituyou && b) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

↑筆者の書いたコード このままだとオーバーフローする

3問目

 わかりませんでした... ソートして先頭から貪欲に協力者を得ていくみたいなことを考えましたが結局考察にも実装にも時間が足りず...

4問目

 最初の小課題1は$O(N^3)$まで許されるので愚直に辺を張ってBFSなりワーシャルフロイドなりをすると通ります。逆に小課題1しか通りませんでした()

5問目

 小課題1は昇順の部分列と降順の部分列に分けて検出して個数を愚直に計算してやると通ります。小課題2は、長方形を全探索してそれぞれのマス目の数字でソートして隣接してるかどうか判定すると$O(H^3W^3logHW)$になりますが、HW<=100なので通ります。
 解説のスライドを見ると、満点解法まで含めて複雑なデータ構造を使わず考察を詰めれば場合分けと累積和だけで実装できるようで目から鱗でした。(それでも実装はとても重いですが)

まとめ

 結局得られた点数は232点で本選Bランクでした。今の自分の実力は出し切ったと思いますが春合宿なんぞには遠く及びません。

 今回の良かった点としては、試験時間内に2問目のオーバーフローに気づけたことと、1、2問目の解法がすぐに降ってきたことでした。
 今回の反省点としては、もう少し3問目の考察をしっかり詰めるべきでした。解説を聞くと、もう少し考察を詰めていれば部分点はとれるものだったので、次回機会があれば、その時はもっと各問題について考察を詰めてから捨てる判断をしようと思います。

 来年にはAtcoder青や黄になって再挑戦したいです。
 今回のJOI本選で、消えかけていた競プロモチベも少し復活しましたし、本選の次の日のARCで後輩が入水して追い付かれそうで恐怖なので、今後とも精進していきます。

おまけ ~チューター企画~

 本選競技が終わった後、チューター企画というチューターの方々が考えてくださった問題をチーム形式で解き、トーナメントで戦わせるといったものがありました。

 ざっくり言うと、操作回数を最小化する問題で、できるだけ操作を少なくするプログラムとできるだけ操作回数を多くするテストケースを1つずつ用意して、相手のプログラムに自分のテストケース、自分のプログラムに相手のテストケースを入れて操作回数の少なかった方の勝ちといったものです。
 同じチームで戦ってくれたチームメイトの2人には感謝しています。僕は実装ができずテストケースをちょっと考えただけになり、結局足を引っ張る形になってしまいましたが...

 22チームある中で、ほとんどのチームが最適になりそうなアルゴリズムを考えていたのに対して、優勝したチームは唯一ヒューリスティックな解法を提出し無双していました。これはかっこよかったです。
 優勝はできませんでしたが、チームメンバーと一緒に考察するのは楽しかったし、面白い経験になりました。そしてヒューリスティックにも興味が湧いたので、Atcoderにもヒューリスティックレートが正式に導入されたことですし時間があればこれも勉強してみようと思います。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?