AtCoder Beginner Contest 293 参加記録 (C++)

お、久しぶりです。
昨日(2023/03/11)に行われた、Atcoder Beginner Contest 293 の参加記録を、初めて書いてみます。

今回の記録

この参加記録始めたてで申し訳ない(?)ですが、この回で初めて入緑しました。ありがとう...(泣
ABCD4完です。個人的に緑diffのDが解けたので、もう多分この世で一番おもしろいコンテストだと思いました※。

perfは 1027 と、目標にしていた 960 くらいを無事に超えることができました。そしてレート差分は +28 で、緑になりました。(後ほど、入緑記事は書きます)

ABC293の成績

※個人の意見です。異論は認めません。

ざっくり解説

A

問題はこちら。

普通に で を入れ替えればいいと思います。ここで怖いのが、 が文字列 の長さ を超えることですが、私はなんか通りました (原因は不明)。

Submissionは以下のようになります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i <= b; i++) //[a,b]
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
template <class T>
using Graph = vector<vector<T>>;
template <class T>
using SGraph = vector<set<T>>;
template <typename T>
ll siz(T& a){return (ll)a.size();}

int main(void){
    string s; cin >> s;
    rep(i,siz(s)) swap(s[2*i+1],s[2*i]);
    cout << s;
}

B

問題はこちら。

まあ、これも問題と同じようにしていけばいいです。私は人 が既に呼ばれているかどうかを表す配列 seen を使って管理しました。
ただし！！！！ は 1-indexedであることに注意です。過去の私ならそれに気づかなくて殺されていると思います。

Submissionは以下のようになります。(コードの ll siz = ... 以上の行はAとまったく同じなので省略しています)

int main(void){
    int n; cin >> n;
    vector<int> A(n),seen(n,0); rep(i,n) cin >> A[i];
    rep(i,n){
        if(seen[i]) continue;
        seen[A[i]-1] = 1;
    }
    vector<int> ans;
    rep(i,n) if(!seen[i]) ans.push_back(i);

    cout << siz(ans) << endl;
    for(int a : ans) cout << a+1 << " ";
}

C

問題はこちら。

とりかかった当初は、 の長さの配列をそれぞれ作って方向をbit全探索でやろうとしました。
しかしいまいち実装方法がわからなかったので、一回保留。そして再帰DFSの宇宙に旅立ちました。

再帰の方法はけんちょん様の記事をお借りして基づいて頑張ってやりました(語彙力)。
最初は set で保持しようと思いましたが、eraseだと全部消える※ので断念。

次にmultisetを使いました。これもバグり散らかして断念。なんでやろうね...

そして最終的に、誰もが愛する map(連想配列) を使い、個数保持として使い、なんとかACすることができました。
でも40分経過。再帰大好きなのに、これは痛い...と思いました。(もちろんですが、何を使ってもどんだけ時間を使っても解けたときはめちゃくちゃ嬉しいです)

Submissionは以下のようになります。

int ans = 0,h,w;
void dfs(const vector<vector<int>>&A,map<ll,ll> &mp,int ny,int nx){
    if(ny == h-1 && nx == w-1){
        bool ok = 1;
        for(auto& [k,v]:mp){
            if(v != 1) ok = 0;
        }
 
        if(siz(mp) == h+w-1 && ok) ans++;
        return;
    }
 
    if(ny+1 < h){
        mp[A[ny+1][nx]]++;
        dfs(A,mp,ny+1,nx);
        if(--mp[A[ny+1][nx]] == 0) mp.erase(A[ny+1][nx]);
    }
    if(nx+1 < w){
        mp[A[ny][nx+1]]++;
        dfs(A,mp,ny,nx+1);
        if(--mp[A[ny][nx+1]] == 0) mp.erase(A[ny][nx+1]);
    }
}
 
int main(void){
    cin >> h >> w;
    vector<vector<int>> A(h,vector<int>(w));
    rep(i,h) rep(j,w) cin >> A[i][j];
 
    map<ll,ll> mp; mp[A[0][0]]++;
    dfs(A,mp,0,0);
    cout << ans;
}

※例えば集めた整数が とすると、set では となります。再帰で、これはもう条件を満たしてないから無理！！となった後に要素を一つ消したいですが、erase 関数を使うと要素そのものが消えてしまいます。
これはどういうことかというと、「 は つ持っていたはずなのに、 つとも消えてしまった」という最悪なことが起こります。こういうときは、デバッグ大臣をして確かめてみるのは、一種のACへの手段だと思われます。

D

問題は(こちら)https://atcoder.jp/contests/abc293/tasks/abc293_d。

最初は、ロープの色と番号で、なんか二次元配列で頑張ろうとしました。しかしそれだと、例えば 本以上で環状になっていたら...？と思い、やめました。
で、もう一回考えてみます。すると、急にグラフの入力の仕方を思いだしたのです。これがグラフに愛されている人の恋愛...！！！

「これ、 頂点 を相互につなげ合わせたグラフになるのでは...！？」

そう、私の親友、UnionFind くんに呼ばれた気がしたのです。するとこれはロープの色ごとに頂点番号を新たに振り分けるのが、いいと思いました。
そして、 頂点 辺の無向グラフとみなし、閉路検出※を行い、連結成分※の個数を数えた結果、ACしたのです。

UnionFind 君に、またもや救われたコンテストと、確信しました。ほんとうにありがとう...！！！！！

Submissionは以下のようになります。

struct UnionFind {
    vector<int> par,rank,siz;
    UnionFind(int n):par(n,-1),rank(n,0),siz(n,1) {}
 
    int root(int x){
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
 
    bool same(int x,int y){
        int rx = root(x),ry = root(y);
        return rx == ry;
    }
 
    bool unite(int x,int y){
        int rx = root(x),ry = root(y);
        if(rx == ry) return 0;
 
        //union by rank
        if(rank[rx] < rank[ry]) swap(rx,ry);
        par[ry] = rx;
        if(rank[ry] == rank[rx]) rank[rx]++;
        siz[rx] += siz[ry];
        return 1;
    }
 
    int size(int x){ return siz[root(x)]; }
};
 
int main(void){
    int n,m; cin >> n >> m;
    vector<vector<int>> R(n);
    UnionFind uf(2*n);
 
    rep(i,n) uf.unite(2*i,2*i+1);
 
    int ans = 0;
    rep(_,m){
        int a,c; char b,d; cin >> a >> b >> c >> d;
        a--; c--;
        a *= 2,c *= 2;
        if(d == 'R') a++;
        if(c == 'R') c++;
 
        if(uf.root(a) == uf.root(c)) ans++;
        uf.unite(a,c);
 
    }
 
    int cnt = 0;
    rep(i,2*n) if(uf.root(i) == i) cnt++;
    cout << ans << " " << cnt-ans;
    //R:2i+1,L:2i
 
}

※ 「ロープが環状になっている」-> 「 頂点のうちいくつかの頂点を結んだ辺でサイクル(閉路)が作られている」だと思いました
※ すべてのロープの状態を数え、その「状態数」と「ロープが環状になっている数」の差分が「ロープが環状になっていない数」に等しいためです

※上のコードにおいて、

a--; c--;
a *= 2,c *= 2;
if(d == 'R') a++;
if(c == 'R') c++;

となっているのは、私が勝手に 「 R のときは頂点 と、 L のときは頂点 とみなしている(かつ 0-indexedに直している)」ためです。

総括

本当にすばらしいコンテストでした。今までのperfの最高は 1300 くらいと劣ってはいますが、最高でした。何より緑diffを本番ACできるとは、本当に思ってもいませんでした。

Epilogue

よし...こっから本番です。記事を、も一回書きます。頑張ります。

ABC-269 D - Do use hexagon grid 別解説(C++)

前回の記事とうって変わって真面目な記事です。ご了承ください。
今回は、自分が茶梅しているときに書かれていなかった別解説を書きたいと思います(嘘解法ならごめんなさい...一応ACは確認しております)。

問題はこちら。

公式解説の説明(ざっくり)

(...というか、現茶が書いていいものなのか...？まあいっか)

公式の解説(physics0523さんの解説)では、 の大きさの二次元配列を用いて実装しています。
そして我が家の伝統 +UnionFind+ を使って連結性を判定しながら連結成分をカウントしていく、という感じになっています。

これは のみで解けるように感じられます。しかし私が書いた解法(既出そうですが...)では、さらに拡張して で解くこともできます。

自分なりに考えた解法

黒いマスは与えられた のみだけなので、この 個のマス以外は、基本的に考えなくてもよいです。これは上の解説も同じことをしています。
近傍や 近傍で深さ優先探索(DFS)するのも同じですが、ここから上の解説とは異なります。

上の解説では、グリッドの情報を保存するために二次元配列を使うのに対し、私の解法では map(連想配列) を使って判定しています。

どういうこと？

二次元配列は、黒いマスの座標以外に余分な白いマスの情報も保存されています。しかし map を用いることで、黒いマスの座標以外の情報を持たなくなり、情報量が少なくなります。さらに二次元配列は配列の大きさにとらわれるのに対し、map ではその大きさにとらわれない※のが、この解法の特徴です。

※ これ、set でもよくない...？と思った方もいるでしょう。しかし map の方がいいことを後半の方に説明していますので、ご参照ください。

DFSの方法

通常、グリッド上の探索では以下の つの鉄則があります。

• 1: 今探索している座標がグリッド外に出ていないか？
• 2: 今探索している座標に、何も障害物(すなわち探索できないような壁マス)が置かれていないか？
• 3: 今探索している座標が既に探索済ではないか？

しかし、今回は上の鉄則は 1,2 だけ無視することが可能です(グリッド外に出たとしても、それは白いマスを探索しているのと同じなため。また白いマスは障害物扱いになるが、白いマスは探索する必要はないため)。

3: の内容ですが、これを満たしていないと探索の無限ループが起きてしまうのは明らかです。今回はこれだけ満たしていればよいです。

問題は「探索済かどうかどうやって判定するか」です。

いったん、制約を見直してみましょう。制約にはこう書かれています。

「 は相異なる」

この制約は使えそう...！！！となります。つまり、同じ座標のものがない(まああったとしてもあまり影響はない)ので、座標組ごとに番号をつけて管理するのがよいと思われます。これが map を使う理由でもあります。つまり、

• に番号 を付ける

とするのがよいでしょう(このとき は 0-indexed,1-indexedどちらでもよいです。私は0-indexedで実装しています)。

「探索済かどうかどうやって判定するか」の問題に戻ります。上の方法で番号付け、別で探索済かどうかを表す配列 で管理すればよいです(詳しく実装例をご覧ください)。

また「今探索している座標が黒いマスかどうか」判定するのは、count 関数などを用いるとよいです。

今回書いたコード(C++)

(Submissionはこちら)

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i <= b; i++) //[a,b]
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using SGraph = vector<set<ll>>;
template <typename T>
ll siz(T& a){return (ll)a.size();}

int main(void){
    int n; cin >> n;
    map<P,int> mp;
    vector<P> p(n);
    rep(i,n){
        int x,y; cin >> x >> y;
        mp[{y,x}] = i;
        p[i] = {y,x};
    }

    int ans = 0;
    vector<int> seen(n,0);
    stack<P> st;
    rep(i,n){
        if(seen[i]) continue;
        st.push(p[i]);
        while(siz(st)){
            auto state = st.top(); st.pop();
            srep(dy,-1,1){
                srep(dx,-1,1){
                    if(dy*dx == -1) continue;
                    int ny = state.first+dy,nx = state.second+dx;
                    if(!mp.count({ny,nx})) continue;
                    if(seen[mp[{ny,nx}]]) continue;
                    seen[mp[{ny,nx}]] = 1;
                    st.push({ny,nx});
                }
            }
        }
        ans++;
    }
    cout << ans;
}

Epilogue

やっぱ探索問題(特にグラフ)ってこれだから楽しい...！！！！！！

単独コンテストを、開いてみました。(+ラテ流作問の掟(テストケース作成など))

...あれ、見えてますかね？
こんにちは、抹茶大好きまっちゃラテです！！

え～...すみません、話が苦手なもので、ブログも何を書けばいいかわからんですが...
今回、Mojacoder さんで開かせていただきました、私の単独コンテスト、Matcha Rate's Sakura Contest -MRSC- 🌸🍡 の、裏話やどんなことをやったのかなど、ここに記録していこうと思います！

えーとその前に...

私がコンテスト、または問題作成の際に心がけていることを記します。主に以下の 4 つです。
私としたことが、GTXC のやつも忘れてたので、ここに記します。

• ラテ流作問の掟目次
  • 第一: やはり最初、問題作成
  • 第二: ほぼ一番の難所である、想定解作成
  • 第三: 大体ここでいつも精神を削がれる、テストケース作成+バリデーションテスト
  • 第四: 「自分が必ずしも合ってるとは思うな」、Tester集め

第一: やはり最初、問題作成

はい。最初からむずいことが来ました。私もちょくちょく趣味で(!?)作問をしているのですが、「こういうテクニックを使った問題作りたい！！！」という気持ちで臨むと、大体最悪な問題ができてしまうのです (実は、単独で出した問題がそれに当てはまるのです...)。
私の個人の見解ですが、問題の思いつき方は以下の 3 つがあると思われます。

• 1: なんかネタが舞い降りてくるタイプ
• 2: なんか典型問題を少し変更するタイプ
• 3: なんか実験してみてこういう問題が作れそうタイプ

私の場合、圧倒的に 1 番が当てはまると思いました。大体ああいう問題は、学校の下校途中や、友達との会話をしている時や(!?)、なんか思い出を探っていきながら見つけるのです。まさに深さ優先探索ですね！！！！

...まあ、本当にこんなのったりした感じで作問することが多いです。経験を無駄にしないということは、このことなのかもしれません。
この際、典型テクニックはなるべく使わないような問題を思いつくことが多いですね...(だってすぐ見破られたくないもん！！！！)

ちなみにいうと、私の場合はGoogle Document で AtCoder の問題みたいなフォームで書いています。こんな感じ？↓

自分が作問するなら...こういう感じ？

題名はですね...ほぼセンスの光具合が優先されると思われます。私はでぃーぷえるTranslation君を用いてなんとかこんな感じになっています(語彙力

※ $K$ や $\le$ は LaTeX 記法をまねています。確かに数式はありますけど、私はそのフォントがあまり好きではないので使っていません！！

第二: ほぼ一番の難所である、想定解作成

ここも大事なところ。想定解がしっかりしてなければ、それはもちろんコンテストには出せません。これは当たり前です。

想像してみてください。

二分探索を必ず使わなければいけない問題に対して、想定解が "Binary Search!" を出力するだけのコードだったら、嫌でしょう？

なんなら、この想定解を作った時点でこれは噓解法であるかどうかを見極めないと、私のように大変な目に遭います(後半部分をご覧ください)。

まあつまりは、本当にコードの意味をわかっていないと想定解が間違ってるかどうか気づきにくいということです。なので皆さんは、緑色になってから作問をすることを、私自身から強くおすすめします(私自身への戒め)。

いや、もちろん緑色になれ！！！って言ってる訳ではないのです。
想定解の正当性を証明できるような知識さえ持ってれば、必ず質の高い想定解を作ることはできます！！！！！多分！！！！！！！

(言い方、自分は茶色コーダーのくせになんか上からですみません)

第三: 大体ここでいつも精神を削がれる、テストケース作成+バリデーションテスト

来ました。皆さん大好きのテストケース作成です！！！！

私が想定解が嘘かどうかは、大体ここで気づきます。いや想定解作成で気づけたらいいんですけどね...はっきり言いましょう。私には無理です☆

テストケース作成はどうしてるのかというと、以下のような目安になってます(必ずしもどのコンテストでもこんな感じとは言い切れないことに注意してください)。

• sample ケース: 問題の入出力例とまったく同じケースを作る
• hand ケース: とりあえず考えられる入出力を手動で作る
• rand ケース: とりあえず大きいケースを自動で作る
• corn ケース: 想定解でも引っかかったようなコーナーケースを作る
• add ケース: 後々見つかったコーナーケースを作る

...果たしてこれはここに書いていいものなのでしょうか？自分にはわかりません(指摘されたら消します)
手動で作るケースはまあ予想通りでしょう。問題は、自動で作るケースです。

例えば 100000 個の数値が与えられるような問題での作るケースを考えてみましょう。流石にこれは手動では、私だったら宇宙が終わるくらいかかります。
なのでこういうのは、皆さんご存じの「ぷろぐらみんぐ」を使って書いていくのです！！！

ほいでどうやってやるかって？
それは個人で調べてみてください！！！！！！！！！！！！！！！！！！！！！！(説明する気力がない人)

参考までに、ケース作りのサンプルコード(C++)を載せておきます↓

#include <bits/stdc++.h>
#include <fstream> //file参照
#include <random> //乱数生成
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
using urd = std::uniform_real_distribution<>;
using ll = long long;

int main(void){
    //ここではメルセンヌ・ツイスター法を用いた乱数生成器を使用する
    int64_t seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
    mt19937_64 rnd(seed);
    std::ofstream file;
    
    //ここに入力する対象でなんかする！！！
    /*
    * ちなみに、ファイル操作では
    * 
    * file.open(S); (S は参照ファイル名)
    * file.close(); (今開いているファイル S を閉じる)
    * 
    * で、乱数を使って入力を生成したいときは(型エイリアス宣言を使っているので少々見にくいですが)
    * 
    * urd N(1,1000);
    * 
    * と書きます！(これだと 1 から 999 までの実数値をとる！)
    * (つまり生成する数値は半開区間であることに注意！)
    * 
    * で、乱数生成の際に、
    * 
    * file << N(rnd) << endl;
    * 
    * みたいな感じで書きます！(これだと参照したfileに N(乱数) と改行を書き込む！！！
    * 
    * もっというと、for文を使って一気にケースを作ることが可能！！！やばすぎ！！！感動！！！！！！
    */
}

ふぅ...ちょっと落ち着いていいですか？マジになりすぎました...(🍵ごくごく)

まぁ、上のプログラムにお世話になっております。メルセンヌ・ツイスター、名前がかっこよすぎる...！！！！！✨✨✨✨✨✨✨✨

第四: 「自分が必ずしも合ってるとは思うな」、Tester集め

え～私の見解としましては、これが一番精神を削がれることだと思います。
なぜなら、自分の想定解が噓解法であることを躊躇なく指摘されることが多いからです。

じゃあTesterさんが悪いのか！？というとそうではなくて、言い換えるとTesterさんは「良い問題にしよう、絶対嘘解法疑惑なんか生み出させないぞ！！」という気持ちで臨んでくれているので、Testerになってくれた方々には本当に感謝するべきです。
私も実際、" M から始まる 11 文字の人" から噓解法を指摘され、なかなか精神が安定しないときがありましたが、その出来事があったからこそ、こうやって素敵なコンテストを開催することができたのだな、と今でも思っています。

(ん、なんか段々趣旨から外れているような...？)

まぁ、一回そこは置いといて！
Testerさんを集める手段はいくつかありますけど、私はTwitterから自力で集めることがほとんどです！！！

あの時も、yukicoder さんに投稿した問題もあるんですが、実は。その時も最初はどうやって集めればいいかわからず、Twitterで集めている人を見かけたので見様見真似で私も同じようにして集めたのが、今でも続けてTwitterで集めているきっかけでもありますね...

あと、Testerさんとはすぐに共有できるように、なるべく Discord などのプライベートな空間で複数人で話し合えるようなところでやったほうがいいと思います！！！直接、個人個人でTesterさんに、ケース更新の報告や指摘の報告などを共有できないと、いろいろ手間がかかってしまうと思ったためです！！！！

#

...とまぁ、ここまで話しましたが、こんな感じでてんやわんやな問題Testをしていました。

ということで。実は、

ここからやっと本編に入ることを忘れないでくださいね？

(驚かせてすみません)

GTXC のうらばなし

去年(2022)に開催した、クリスマスコンテストでは、裏ではいろいろあったのです...
各問題ごとに記していきます！

ちなみに、このコンテストを開催しようとしたきっかけは...

”””興味""" です。

(じゃあこれ言う必要ある？ないです)

(あ、この先解法ネタバレ注意です)

A(#1) Red and Blue

A問題なので、まあ簡単目で。今回はソートに関するものにしました。連想配列でも解けますけどね...
まだまだ序盤なので、本棚をテーマにして作りました。
(今、問題文を見てみたんですが、ま～わかりずらいですね...すみませんでした...)

推定diffは 50 以下を目安にして作りました。

B(#2) Footprint

B問題なので、まだ簡単目...とでも思いましたか？^^
この頃の私は、「重実装の問題を何か 1 つ出してSolverさんたちを苦しめさせてやろうひっひっひ」と思っていました(最悪)
二次元グリッド問題が好きだったので、シミュレーション問題にしようとしたらこんな感じになっちゃいました。

実は、これはNを10^{18}にしても解けるな...とも思っていました。
Hard版も作ろうかな～と思いましたが、さすがにHardはいっか...ってなってこのような制約にしました。なんなら想定解がむずくて書きたくn (殴

ヒント: (白字にしてます)↓
連想配列でX座標Y座標を別々に持ってれば、クエリ 1 つ当たり二分探索でO(logN)で解けそう...？知りませんけど。

推定diffは 390 以下を目安にして作りました。

C(#3) Let's "Clone" It

C問題はなんかひねりました。なんかCチックな問題を作りたいな～と思って作りました。Bくらいでした。Dくらいでした。Cが作れません。助けて！！！！

と思ったとき、過去の自分が何か作っていたのでそれを参考に作りました。数学的思考ですねこれは。
多分、過去の自分もこういうの作れてうれしかった記憶があったと思います。

あと、Story上にnumDeer君と書きましたが、感のいい人なら多分突っ込まれますねこれ。あとは特に書くことはない！！！！！

推定diffは 500 以下を目安に作りました。

(このタイミングですみませんが、ケース更新しました。過去の想定解は嘘解法でした(今は修正済です))
(私の友だちが指摘してくれました。ありがと～！！！！！！)

D(#4) Pile The Integer Game

実は、とある実況者の実写動画を見て思い浮かんだものです。なんなら確か高2の2学期期末考査の真っ最中...？(勉強せい)
で、二分探索じゃないときついな～と思ってた矢先、愚直でも解けるという二段構えに心躍らされました(?)

まぁつまりはシミュレーションです。今見ると、テーマ被った～やっちゃった～って思いますけど、過去の自分はそんなことはとうに思ってないでしょうね...

推定diffは 700 以下を目安に作りました(にぶたんじゃないと無理と思ったため)。

E1,E2(#5,#7) A Most Popular Matcha's Snow Land

多分過去のツイートをあさっていただくとわかると思いますが、実はimos法に慣れていたときだったのです。その過去のツイートが見つからんです :(
最初この問題を思いついたとき、あのD問題を思い出しました。それもあって、Hard版が作れたんだと思います。ここでHard版の想定解がないのは、自分で解けなかったためでs (大殴

推定diffは、Easy: 700 以下、Hard: 1200 以下を目安に作りました。

F(#6) Playing Connection Woods

F問題なので、相当むずくしようと思いました。実は、最初この問題もシミュレーションのつもりで作っていました(過去の自分、テーマ被りすぎです)。
...と思っていると、なにか🍄の人がそっと手を差し伸べてくれて、その瞬間さわやかな風が心地よく吹き始め、

「おい、この問題、区間スケジューリングで、解けるぜ(イケボ」

と言ってくれたのです...！！！ キャー！！！！かっこいー！！！！！✨✨✨✨✨✨✨✨
実は、過去の過去の自分は貪欲法大好きでいました。めちゃめちゃ嬉しかった覚えがあります。

推定diffは 1000 以下を目安に作りました。

#

こんな感じでGTXCは成り立っていました。違うテクニックでこの問題は解ける！！！って言いきれる人って、マジでかっこいいですよね...あこがれる...

え～、こっから本編の後半です。しっかりついてきてくださいね！！！
長っ！！！！！！もう見るのやめるわ！！！！なんて悲しいこと言わないで心にとめておいてくださいね！！！🔥🔥🔥🔥🔥🔥🔥

MRSC のうらばなし

今日(2023/03/05)、開催した桜コンテストの裏話です。実は裏で大変なことが起こっていたのです...！！！

A(#1) All to Almost Perfect?

A問題なので、気楽に作るか～という思いを込めて作りました。簡単な場合分けです。
Storyは大分意味の分からんものが作れて、大満足です(え？)。綺麗に並べるって、いいよね...並べすぎるのもアレですけどね...

推定diffは 50 以下を目安に作りました。(Testerさんの推定: 10,30,50(Just!!) )

B(#2) Share It Now

実は、過去の自分が作ったやつなのですが、めちゃくちゃな感じで想定解を書いておりました(しかも嘘解法)。改めてA問題と同じ手法で解いてみると、あらびっくり！！超が付くほど簡単に想定解を作れました！！！！

...え？A問題はあまりなんか関係ないって？
実は、またテーマ被りしたのです。最初次のような文章でした。

「すべてのおぼんに対し、乗っている🍡の個数が K の倍数であるようにするためには、少なくともいくつだけお団子を作る必要がありますか？」

でも、後々Bとテーマ同じやん！！！ってことに気づいたのです。なので、おぼんに乗せるお団子の数がちょうど～にすることはできますか？調に変更したのです。
多分、このころの自分は大体Bに殺されていた時期でした。精神が持たなかったんだと思います。

Storyの友だちとの会話は、私の人格を殺して作ってみました。最後の口調が強くなっていると思われます。多分。

推定diffは 100 以下を目安に作りました。(Testerさんの推定: 50,70,80,100(Just!) )

C(#3) Swap to Palindrome

これは最近作った問題です。なぜか回文の問題を作ろうとしたらできたやつです。
最初は順列全列挙で作ろうと思っていたんですが、回文の定義を見直してみればめっちゃ高速に判定できんじゃん！！！！で、N<=10⁵にしました。

今Storyを見てみると、やばいですね。
茶処に回文のメニュー名が入っていたらめちゃくちゃ怖いですよ。知りませんけど。

推定diffは 300 以下を目安に作りました。(Testerさんの推定: 250,200)

D(#4) Separation and Union

過去の自分が解けないくせに作った問題です。今、この立場からすると結構簡単に見えますね(個人差があります)。
最初、題名は "String Sales" でした。売っている文字列を買ってその文字を切り取って組み合わせる、って感じ！

多分ですけど、価格追加して所持金追加してってやると、DPの問題に早変わり！！！(本当か？)になります。ん～...その場合の推定diffは1000を超えそう...
なのでその問題はしまってあります。おいておくので、興味があったらやってください！！そして私に教えてください！！！！！！

DPみたいにしたver.

で、Storyではデコレーションケーキをモチーフにしようかなーと思ったので、ただの文字列だと味気ないので、チョコレートにして自然な感じに仕上げてみました。召し上がれ！！！！！！！！

推定diffは 600 以下を目安に作りました。(Testerさんの推定; 300,350、思ったより結構低め...？)

E(#5) Break-The-Brick!

はい、じゃ、まずは言ってましょう(唐突)。せーの...！！

って、あれだ！！著作権あるから言えないのかもしれない！！！うおー言いたいのに！！！韻が踏めるはずだから！！！！

「OOOO！！！！」(ある女子生徒4人組でバンドを作り、文化祭で青春を飾る青春ストーリーのアニメの題名)

...そうです。不自然に -(ハイフン) を付いていると思ったでしょう？
そのアニメを見ている私からすると、めちゃくちゃ発音同じやん！！！になったのが、題名の起源になりました。(最初は、ダルマ落としを英語にしただけにしようと思っていました)

あ、ご飯呼ばれたので、またあとで～！！

#

よっし、再開しました。
え～となんだっけ？ぼざろの話をしていたのか...

よし気を取り直して。
て言ってももうあまり言うことがない...ただ、過去の自分はこれはDPじゃ解けません！！！どやっとか言って今の自分からすると「は？」の一言になったことだけは言えます。

推定diffは 800 以下を目安に作りました。(Testerさんの推定: 650,600、これも低め...いや、妥当？)

F(#6) L to R Multiply

F問題、実はこんなことがあったのです。こういう問題がありました。

「数列Aからいくつか選び、選んだ要素からなる数列Bとします。Bはどの2要素を選ぼうと互いに素であるようにしたいです。Bの長さの最大値はいくつ？」

N<=16なら、まあbit全探索ですが、これを10⁵で解こうとしました。
しかし、" M から始まる 11 文字の人" に、衝撃の一言を発されたのです。

「これ、NP困難では、ないですか？」

え？と思いました。全然気づかない(そもそも常人ではほぼ見抜けない、すなわちその指摘した人は天才だということ)ので、マジで意味不明と、最初は本当に思いました。でも、その後の説明で、納得しました。

え、じゃあこの問題、多項式時間しゃ解けないってこと？そういうことです。

そう、この問題だけ全取っ替えをしたのです。幸いにも、D問題は過去に作ったことがあったので助かりました。
そのD問題が、今回出したものです。大分、私の"""罠"""にまんまとはまってくれて助かりましたよ！！^^

素因数分解の問題を作りたかったので、この問題はまるで都合のいく素晴らしい問題でした。でも、実際のコンテストでこれが出てきたら私は泣くと思います。
「じゃあその問題を俺たちに解かせんな！！！」って！？すみませんでした。。。

推定diffは 1300 以下を目安にして作りました。(Testerの推定: 1000、そこそこあってそう...？)

G(#7) 1 Bird on Cherry Blossoms

お気づきでしょうか。私はグラフ理論が大好きでたまらないんですよね...！！！！(ニヤリ
ちょっとひねろうとしたら、素数を集めるというものというのが脳の中に出てきたのでそれにしました！！

実は、この問題が時間制限に厳しめにしてあるのです...！！！(すいません、アンケートの問題がすげぇ紛らわしかったですね)
(Pythonではすべてが時間制限に厳しめにしています(最悪))

まあ解説を見てもらったらわかる通り、愚直に素数判定した瞬間即座に落とします(This is True 無慈悲)。

K=0に引っかかってくれてる人がいて、くぅ～！！ありがとうございます！！！！！✨✨✨✨✨✨✨✨^^

推定diffは 1200 以下を目安に作りました。(Testerさんの推定: 800,700、なんか簡単だったそうです...)

Ex(#8) 7 - 3 = 5 ?

題名を見て、「こいつ頭おかしくなったんか？」と思ったそこのあなた！！大正解です()

いや、あるTwitterのスペースでですね、なんかの資格試験の勉強をしている際、7 - 3 = 5 で計算してミスるという最悪なことをしたのですよ！！
それが元凶になってこんなことになりました(実は最初から 7 問構成でいこうと思っていました)

で、肝心の問題内容ですが、実は最初は K=5 固定でいこうとしました。しかし、これまた " M から始まる 11 文字の人" に、またさわやかな風が吹き始め、

「これ、フェルマーの小定理で、解けるよ(イケボ」

と言われました。ずきゅーーーーーーーーーん！！！！！！！！！！！！！！！！！！💖💖💖💖💖💖💖💖💖💖💖💖💖

...んん、すいません取り乱しました。

まぁ、こんな最高な人がいてくれたおかげで、素数に拡張して解くことができました。
...え、合成数のときはどうするかって？知るか！！！！！！！(最悪な返事)

推定diffは 1300 以下を目安にして作りました。(Tester推定: 1300(Just!) )

#

ということでした。
どうでしたでしょうか？今回の「茶処・まっちゃら亭」のStoryをお楽しみいただけたでしょうか？
これからも、こんな感じでのったりゆったりぐったりやっていきますので、よろしくお願いします！！！！！

...次、記事書くのは...入緑時？これからも茶梅、頑張ります！！！！！！！！！！！

今回は、参加してくださり+この記事を見てくださり、誠にありがとうございました！！！！！！！！！！！

(11249文字、マジで疲れた...)

Epilogue

よし...とりあえずはこれでコンテスト関係は終わり！！！AHC、やってきま～す！！！

バタン(ドアを閉める音)