ガナリヤの空巣

ガナリヤのプログラミング記録

非公式解説放送について

まえがき

投稿おくれました… もうしわけないです!

Adventerということで、今年から始めた「非公式解説放送」について書こうと思います~~
ICPCアジア参加記とどちらについて書くか悩みましたが、他の方のもありそうなので、個人的に推していきたい非公式解説放送について書いていこうと思います。


非公式解説放送とは?

某、ガナリヤは、今年の夏頃から「非公式解説放送」というのをはじめました。
AtCoderCodeforcesなど、ジャンルをしぼらず自分の参加したコンテストに関して、これからも時間がある限り動画を上げていきたいと思っています。
(最近上げていないじゃないかという声は申し訳ないがNG)


Codeforces 515 Div3 非公式解説放送

例えば、以上のような動画ですね
今はなかなか説明が下手くそなので、時間がかかっていますが、もっとシンプルに簡潔に説明できるようにしたいですね…

なんで非公式放送なの?

非公式解説放送を自分が始めた原因が、いろいろな方の競プロブログをみて、なかなか自分が理解できなかったというのがあったからです。

どうしても、自分は物分りが非常に悪いほうなので、文字媒体のみのブログではなかなかすんなりと入ってこず、いくら読んでもさっぱりわからないみたいなときが多かったです。

ただ、AtCoderの公式解説放送などでは、ある程度理解することができ、視覚情報や音声情報、動作や話し方で伝わる情報は一気に増えるのだなと思いました。

そういったわけで、ガナリヤはブログから解説放送にシフトしました。

最後に

ブログでの解説も非常にいいのですが(図やLaTeXなどを書いているうちに理解が深まり度が高い)、 解説放送だと、より多くの情報が一度に入ってきてわかりやすいような気もします!

できるだけこれからも解説放送をやっていきたいとおもいます!ぜひ皆さんもご検討願えれば!

AtCoderBook(Chrome拡張)

はじめに

どうも。
ガナリヤです。
ここ最近は、競プロずくめの毎日で全然開発できてないです・・・
もっと色々な開発もしたいのですが・・・

大学の授業で忙しいんですよね・・・(元も子もない)


AtCoderBook

AtCoderBook(https://chrome.google.com/webstore/detail/atcoderbook/lcojnofidkanlkoaagdbjkdnelbnlnng?hl=ja)は、ガナリヤが作成した、

  • AtCoder
  • Codeforces
  • AOJ(まだ対応してない)
  • CSAcademy(まだ対応してない)
  • yukicoder(まだ対応してない)

の問題を、コンテストサイトで、ブックして、復習に役立てよう!という拡張機能です。

こういうのがほしいなと思ったきっかけとしては、AtCoderだけでなく、こどふぉにも出始め、過去問もどんどん解いていた結果、どの問題を復習して、どの問題がやりっぱなしなのかわからなくなったからですね・・・

それで、こういうAtCoderのサイト自体で、ボタンをjQueryで作成して、それをユーザページが自分だけの復習ページを表示できればなと考えてました。


AtCoderBookの機能

AtCoderBookの機能は今の所

  • 問題のブックマーク
  • 問題の検索
  • お気に入りボタン

の機能があり、これから実装予定の機能(はよ実装しろ)が

  • 他サイト(AOJ, CSA, yuki)への対応
  • ブックマークのJSON保存
  • 解いた問題などとの同期

があります。
ICPCの対策で忙しくてなかなか作れていないので早く拡張していきたいですね・・・


構成

中身は

をふんだんにガバガバに使用してます。
正直今見たら何やってんだ?っていうコードなので、触りたくないお気持ちがお強い。 開発環境は

  • WebStorm
  • Node.js
  • Webpack + babel

やっぱり、フロントエンドでは、実際に開発している時間より、パッケージがインストールできないと嘆いている時間のほうが長い、はっきり分かんだね。


最後に

もうフロントエンド開発はこりごりなんじゃ〜〜

AtCoder Beginner Contest 097 ガナリヤ

AtCoder Beginner Contest097

こんばんえるえる〜。 ガナリヤなのじゃ・・・!

前回のAtCoder097のABCコンテストは、ABCD全部解けて非常に嬉しかったのじゃ・・・

ただ、C問題、D問題はよくわかんないけど愚直に実装したらなんとかなったみたいなところがあったのでまとめていこうとおもうのじゃ・・・。

後、三回もWA出してしまったので、次回はもうちょっとゆっくりとこうと思うのじゃ!じっくり三分プラスで考えれば防げたミスなのじゃ・・・

A問題  Colorful Transceivers

問題文 数直線上にいるAさんとBさんとCさんがトランシーバーで会話をしようとしています。 Aさんは a [m] 地点、Bさんは b [m] 地点、Cさんは c [m] 地点にいます。 二人の人間は、距離が d [m] 以内のとき直接会話が出来ます。 AさんとCさんが直接的、あるいは間接的に会話ができるか判定してください。 ただしAさんとCさんが間接的に会話ができるとは、AさんとBさんが直接会話でき、かつBさんとCさんが直接会話できることを指します。

これはもう問題文読んでなかったの・・・ 入出力サンプル見てこんな感じかな?ってやってたのじゃ・・・

AさんBさんCさんはそれぞれ一直線上にいて、AとCが会話できればオッケーなのじゃ・・・ AさんとCさんが直接d[m]以内なら当たり前にOKじゃし、AさんとBさん、BさんとCさんがそれぞれd[m]以内の場合もOKじゃな・・・

B問題 Exponential

問題文 正整数 X が与えられます。 X 以下の最大のべき乗数を求めてください。 ただし、べき乗数とは、ある 1 以上の整数 b と 2 以上の整数 p を使って b p とかける整数のことを指すこととします。

べき定数とはbpと表せるものであり、たとえば32とか、28のことなのじゃ・・・ X以下で最大のべき乗数を出せばいいわけじゃな・・・

以下実装じゃ・・・

int main() {

    int X;
    cin >> X;

    VB goods(X+1, false);
    goods[1] = true;

    for(int b=2;b<=1000;b++){
        int value = b*b;
        for(int p = 2;;p++){
            if(value>X){
                break;
            }else{
                goods[value] = true;
                value *= b;
            }
        }
    }

    RREP(i, X+1){
        if(goods[i]){
            OUT_L(i);
            return 0;
        }
    }

    return 0;
}

正直こういう計算の小難しいのは大苦手なのじゃ〜〜

C問題 K-th Substring

問題文 文字列 s が与えられます。 s の異なる substring のうち、辞書順で K 番目に小さいものを出力してください。 ただし、 s の substring とは、 s の空でない連続した部分を取り出してできる文字列とします。 例えば、 s = ababc とすると、 a, bab, ababc は s の substring ですが、 ac, z, 空文字列 は s の substring ではありません。 また、substring が異なるとは、文字列として異なることを指します。

またじゃよ!また! ガナリヤは辞書式が苦手なのじゃ〜(よくわかってない) 辞書式の理解にコンテストの時間を割いてしまったのじゃ・・・

辞書式とは?

辞書式とは、日本の国語辞典とかで、単語が現れる順番のことじゃな・・・
以下のルールによって掲載されておる。

  1. X, Yの文字列を左から見ていったとき、異なる文字が出た時は小さい文字のほうが小さい文字列である。
  2. X, Yの文字列を左から見ていったとき、片方がなくなってしまった場合は、なくなったほうが小さい。

よくわからん!!

  1. X=abcd Y=abceとする。左から見ていって、四番目で初めて異なる文字が出てきてdのほうが小さいため、Xのほうが小さい。

  2. X=ab Y=abcとする。左から見ていってXのほうが先に文字がなくなってしまう。よってXのほうが小さい。

具体例を交えると多少わかりやすくなるのぉ・・・


本題に入るのじゃ・・・

文字列sの異なるsubstringのうち小さい方からK番目を出力する必要があるのじゃ・・・

ただし、Kは1<=K<=5とかなり小さく設定されているところがポイントじゃな・・・

substringを全部試そうとすると

  1. 部分文字列の左側を決めるのにN
  2. 部分文字列の右側を決めるのにN
  3. 小さい順である必要があるため、NlogN

であるためO(N3 logN)らしいのじゃ・・・?

そのため、何か工夫をしないといけないのじゃ・・・

小さい順で1~5番目のどれかを出力するというところがポイントで、部分文字列の長さが6以上を考える必要はないのじゃ!

abcdefを考えるのじゃ・・・。仮にabcdefが1~5番目に入ろうとすると、a,ab,abc,abcd,abcdeの5つがすでに存在しているのじゃ・・・

やっぱC,D問題は気づきが勝負らしい気がするのじゃ・・・


int main() {

    string s;
    cin >> s;

    int K;
    cin >> K;

    set<string> PS;
    REP(i, SZ(s)){
        REP(j, 5){
            string ps = s.substr(i, j+1);
            PS.insert(ps);
        }
    }

    VS ANS_S;
    FOREACH(x, PS){
        ANS_S.push_back(x);
    }

    SORT(ANS_S);

    OUT_L(ANS_S[K-1]);

    return 0;
}

PS c++のsubstr(i, j)は文字列sのi番目からj個取り出すって意味じゃったんじゃな・・・
よく知らずに使っていたのじゃ・・・i+jがsの長さはみ出てもエラー出さないんじゃな・・・

D問題 Equals

Equals

問題文がうまく引用できないので、リンク先を見てほしいのじゃ・・・

なんか小難しいこと言っとるが簡単に言うとこうじゃな・・・

与えられたN個の整数を、指定された位置同士を何回でも交換して良いのじゃ・・・
何回か交換した後、順列Nのそれぞれの数字の位置があっている個数を増やしたいわけじゃな・・・

よくわからんな・・・具体例具体例・・・

N=6 で最初が613452とするのじゃ・・・ (1, 6), (2, 6)が交換できるとすると、(1,6)で交換して(2, 6)で交換すると、123456とすべて一致させることが出来るわけじゃな・・・

この問題はよく分からず自分で何個か具体例を書いたら、交換する二つの数がかぶったところは自由に値を変更できるということがわかったのじゃ・・・
例えば、(1, 2), (10, 20), (20, 5), (5,2)があったら、1・2・10・20・5の5つの位置にある数は自由にならびかえられるのじゃ・・・
これが成り立たなかったらバブルソートもできんわけじゃな

自由に並び替えられるとすると、同じ数字がかぶっているところは同じ性質を持つ・・・
→つまりUnionFind木で集合として扱うのかな?
と考えたのじゃ・・・

こういう考えで合ってたらしいのじゃ(細かい理屈はいっぱいあるらしい・・・)
UnionFindの実装が怪しいので後で見直しが必要じゃな・・・

// 素集合データ構造
//--------------------------------------------
struct UnionFind {
 
    // par[i]→データiの親の番号 i==par[i]ならiは木の親
    vector<int> par;
    // sizes[i]→iを根とする木に含まれる子の数
    vector<int> sizes;
 
    UnionFind(int n)
            : par(n), sizes(n, 1) {
        // すべてのノードがiに属すると初期化
        REP(i, n) {
            par[i] = i;
        }
    }
 
    // データxが属する木の根を得る
    int find(int x) {
        if (x == par[x]) {
            return x;
        }
        return par[x] = find(par[x]);
    }
 
    // 2つのデータx, yが属する木をマージする
    void unite(int x, int y) {
        // データの根ノードを得る
        x = find(x);
        y = find(y);
 
        // 同じ木ならマージしない
        if (x == y) {
            return;
        }
 
        // xの木 > yの木
        if (sizes[x] < sizes[y]) {
            swap(x, y);
        }
        // xはyの親とする
        par[y] = x;
        sizes[x] += sizes[y];
    }
 
    // x,yが同じ木ならtrue
    bool same(int x, int y) {
        return find(x) == find(y);
    }
 
    // xが含まれる木のサイズ
    int size(int x) {
        return sizes[find(x)];
    }
};
 
 
int main() {
 
    int N, M;
    cin >> N >> M;
 
    VI p(N);
    REP(i, N) {
        cin >> p[i];
    }
 
    vector<PII> xy(M);
    REP(i, M) {
        int x, y;
        cin >> x >> y;
        xy[i] = MP(x, y);
    }
 
    UnionFind uf = UnionFind(N);
    REP(i, M) {
        uf.unite(xy[i].first - 1, xy[i].second - 1);
    }
 
    int count = 0;
    REP(i, N) {
        if (p[i] == i + 1) {
            count++;
        } else {
            if (uf.same(i, p[i] - 1)) {
                count++;
            }
        }
    }
 
    OUT_L(count);
 
    return 0;
}

完走した感想

よくわかんないけど解けるっていうのが、少しずつ競技プログラミング慣れしてきた気がするのじゃ・・・
あとはどうスピードを早めるだとか、新しくアルゴリズム覚えるかとかじゃな・・・

理論の説明もできるようになりたいのじゃ・・・

C++ pairとmaxの組み合わせ

競技プログラミングにおいて、他の方の解答を見ていたときに発見。 なんかmaxはpair型にも使えるみたいですね・・・

int main() {

    PII a = MP(10, 20);
    PII b = MP(0, 30);

    PII c = max(a, b);

    OUT_L(c.second);
    //出力は20
    //firstが10, 0で10のほうが大きいため、aのsecondが出力される


    return 0;
}

基本的には、pair型のfirstのみを見て比べてるみたいなのじゃ・・・ ただし、firstが同じ場合はsecondの大きい方を取り出すようじゃの・・・ うまく工夫するともっと楽にコーディングできそうなのじゃ!