2020-06-14

Codeforces 青になりました！

f:id:null0124:20200614032821j:plain

f:id:null0124:20200614032857j:plain

C の速度が良かった難しいわけじゃなかったけど

やったこと(少し真面目に)

コンテストになるだけ出る
精進はほぼ無だけどこれだけは守った
やりたいことをやる
興味を持ったアルゴリズム/データ構造を優先的に学んだ。結果 DP 力が地の底などの弊害も...
問題を前から解くことにこだわらない
得意分野ができると後ろの方が簡単に見えることも多い
楽しむ
モチベが終わっては元も子もないので

2020-06-14

Codeforces 水色になりました！

f:id:null0124:20200612124337j:plain

やったこと

2 完する

2020-06-14

Codeforces 青になりました！

f:id:null0124:20200612123906j:plain

やったこと

データ構造問題に備える
解く
https://codeforces.com/contest/1354/problem/D
激ヤバタイムだが通ったので OK
制約がサイコパスとの噂も

2020-01-12

BinaryIndexedTree 書いてみた話

ライブラリ

なんか書かないと忘れちゃいそうなので。茶色の時に書けたし怖くないよ！でもいろいろ初心者なので間違ってたらどんどん言ってください！

BITについて

BinaryIndexedTree の略。
可換モノイド列 $a_0, a_1, \dots, a_{n -1}$ を乗せることができる。 (追記) モノイドは、二項演算できて結合法則満たして単位元があればよい。可換であるためには交換法則を満たせばよい。(追記)まあたぶんモノイドじゃなかったら乗せるときに気づきそう。
しかし逆元がないと prefix sum しか求められません。(追記)可変群を扱うことが多いでしょう

クエリ

$a_0, a_1, \dots a_{n - 1}$ に以下の二つのクエリがどちらも $O(log \ n)$ でできる。

$add(i, x)$ : $a_i \mathrel{{+}{=}} x$
$getsum(j)$ : $\displaystyle \sum_{k \in [0, j)} a_k$ を求める。

実装

ここ (Binary indexed tree) とかが強い。~~自分のブログで他人のスライド貼るのはどうなの~~
$a_0, a_1, \dots a_{n - 1}$ について、長さ $n$ の配列一個で表現できます。ただし、正確には長さ $n + 1$ になります。( 1-indexed のほうが嬉しいので)
理論の図は上のスライドを見てください。 TODO:書く~~(絶対やらねえ)~~

個人的な実装の話

実装は 1-indexed のほうが適しているので見かけ上 0-indexed っぽくなるようにしています。

$add(i, x)$
初めに $i \mathrel{{+}{=}} 1$ をし、1-indexed のお気持ちになる。
その後、 $LSB$ を足していき、木を上に登っていく。
$getsum(j)$
まず、 1-indexed にする。 $j \mathrel{{+}{=}} 1$ をする。半開区間 $[0, j)$ にそろえたいが実装上全開区間 $[0, j - 1$ ] のほうが都合がよいので、 $j \mathrel{{-}{=}} 1$ をする。
すると、結局のところ $j$ のままで OK。
なので $j$ から $LSB$ を引き、木を下がっていく。
なお、 $LSB$ は最下位 bit を指す。 $x \ bitwiseAND \ (-x)$ で求まるらしい。これ天才だろ。

BIT の実装例( C++ )

template<typename T>
//0-indexed/内部的に 1-indexed
struct BIT {
    vector<T> tree;
    //初期化
    BIT(ll n) : tree(n) {
        tree.assign(n + 1, 0);
    }

    //[0, n) の sum を返す/0-indexed
    T sum(ll n) {
        T ret = 0;
        //実は 1-indexed だが半開区間なので見た目がそのまま
        for (; n >= 0; n -= LSB(n)) {
            ret += tree[n];
            if (!n)break;
        }
        return ret;
    }

    //n 番目に x を足す
    void add(ll n, T x) {
        ll siz = tree.size();
        for (++n; n < siz; n += LSB(n))tree[n] += x;
    }
};

問題

RSQ( verify 用問題)
数列に対して加算と合計を聞くクエリにこたえる問題。
yosupo judge さん大好き！
judge.yosupo.jp AOJ 版( 1-indexed であることに注意) onlinejudge.u-aizu.ac.jp
ちなみに簡単な引き算で $[i, j)$ の合計は手に入る。

転倒数はバリ典型問題(以下に解法を載せます)

$a$ がとりうる値の長さ(制約より $N$ ) $+1$ の配列 $b_0, b_1, \dots, b_{N}$ を取り、 $b_i$ を $i$ の出現回数とすると、 $i$ の前にいくつ大きい数があったかが $getsum(i + 1, N)$ で出る。これをもとの配列すべてについて回せばよく、また $getsum(i + 1, N)$ を回す前後で $add(i)$ をすればよい。こうすることで今見ているところからの情報のみが得られる。
計算量は、クエリが $O(log \ n)$ , これを $n$ 回回すので $O(n \ log \ n)$ 。 atcoder.jp

SegmentTree という BIT の上位互換のデータ構造があるのですが、それについては今度書きます。BIT は SegmentTree より実装が軽いのと定数倍が軽いのが特徴。
実装が軽いので、 BIT は二次元に発展させたりが簡単らしい。こういうのをやって記事にしたいね。

2019-10-15

Beginners After Typhoon Contest #001 裏話？とか反省点とか

始めに

お疲れ様でした！参加者も運営陣にも感謝です。
実は、僕がleafirbyさんに「HakerRank使ってみたい」って言ったのが始まりなんですよね。
その後、もともと部内コンの予定で進んでいましたが、部内で予定が合わず、もったいないので公開しません？と言って公開しました。予想以上に人が来てビビった。フォロワー増えた。

反省点

いきなり明るくない話ですみませんね。でもいろいろあるので忘れないうちに書きます。

入力10⁷個は不評っぽい
こどふぉでもやらないぞ...という声がありました。まあ高速化させる問題なのでしゃーないとは思うし結構ゆるふわコンテストにしたので許されなくはないと思うけど...僕は一部言語殺すのも入力で落とすのも嫌いです(scanf/printf派ですが)。
テストケース最後の改行
これほんと申し訳なくて、僕は一応改行ないと死ぬ言語を認知していたので、改行で統一した(ミスで改行抜けはあった)のですが、運営陣で情報を共有できておらず、Brainfuckなどの言語を使用している人が問題を解くことが難しくなるなどがありました。これは次回への教訓ですね(改行は必須でちゃんと共通認識にする)。最低限形式を共通にする、ですね。
配点ミス
ミスはしゃーない。これは直前に起きたことだし。ただ配点を直さないほうが対応としてよかったかもしれない...
H問題
僕は(問題は)嫌いだけど(これを出す精神は)好きです。有志コンなんだし。ただ僕嫌いすぎてtesterできなかったんだよな。不備が見つかった配点変更はしゃーないとして、嫌われる問題ってことはわかってるしleafirbyさんには最後まで気を強く持ってほしかった。
使用言語選択バグ
これあんま俺ら悪くなくね？一度選択すると設定引き継がれて困らないんですよ。これからはHackerRankの言語選択は信用せずテストします。あと言語数限定します。
キムワイプ食べ始めどこ？
これ唯一の純粋なミスへのclarじゃないか？問題文は無心になって読み返しましょう。特にこういう一見自明が落とし穴です。null覚えた。
既出目立つ
正直、僕のは過去問改変が多いのでそれはそうなんですが、もうちょっと既出見つかるを抑えたいなと思いました。逆ポーランド記法はギリ。ちなみにZero-Xor-Sum Rangesは完全にパクりネタ枠なので気にしてないし、想定解が本家改変です。

他思ったことなど
これ問題完璧に完成してテスト終わってから告知なりやればいいのでは
天才では？準備はちゃんとしましょう。(直前までドタバタしてたのはダメ)
ちゃんと必要なことを調べよう

有志コン開くのは良いけど、コンテストに必要な準備をそもそも知らずにコンテスト開催している人が多い気がするので、ちゃんと調べてから開催してね！
（といいつつ、その辺の資料ってどこに揃ってるのかな）
— chokudai(高橋直大)🌸🍆🍡 (@chokudai) October 14, 2019
正直いろいろ知らなかったことがここに書いてある単語を交え検索すると出てきました。開催動機があれなので無知になってしまうことは自然なのですが、だからと言って許されません。
次回からコンテスト開催経験者を呼びたい
これで解決しそう。いろいろ知れるし。誰かコンテスト開催経験者で次回一緒にやりたい人いませんか？
いろいろ言ったけど初開催にしてはかなり上出来な気もする
初開催で不具合がここまでしかなく、ちゃんとできたのはかなりすごいのでは？すごい(自画自賛)。

次回どうしよっかなって話

僕はいつかやる気でいます。それまでに緑にはなっていたいな～。DP問を書きたい。今回のコンテスト、800のおかげで盛り上がった感じがあるので、それに代わるものを生成できるようになりたい。頑張ります。
次回やるとしたら一緒にやりたい人をwriter,testerともに勝手に募集してます。ぜひ。
次回人増えたらGitHub使うのかなぁ...なにもわかんないなぁ...

ご参加ありがとうございました！次回もお待ちしてます！

2019-10-14

Beginners After Typhoon Contest 担当問題解答例

includeなどは省略させていただきます。

B

int main() {
    int a, b, c, d;
    string ans;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if (a > c) {
        ans = "null";
    }
    else if (a < c) {
        ans = "tRue";
    }
    else {
        if (b == d) {
            ans = "Draw";
        }
        else if (b + 1 == d || b - 2 == d) {
            ans = "null";
        }
        else {
            ans = "tRue";
        }
    }
    printf("%s\n", ans.c_str());
    return 0;
}

C

int main() {
    string s;
    cin >> s;
    cout << (s == "ushitapunikiakun" ? s : "No") << endl; 
    return 0;
}

F

int main() {
    int a, b, c, d, p, q;
    cin >> a >> b >> c >> d >> p >> q;
    long long M = INF * -1, xM, m = INF, xm;
    for(int i = p; i <= q; ++i){
        long long atai = a * i * i * i + b * i * i + c * i + d;
        if(atai > M){
            M = atai;
            xM = i;
        }
        if(atai < m){
            m = atai;
            xm = i;
        }
    }
    cout << M << ' ' << xM << ' ' << m << ' ' << xm << endl;
    return 0;
}

G

#define rep(i, n) for(int i = 0; i < (n); ++i)
int main() {
            int n, m;
            string s;
            cin >> n >> m >> s;
            vector<vector<bool>> a(n + 1, vector<bool>(n + 1));
            a[0][0] = true;
            int x = 0, y = 0;
            rep(i, m) {
                if (s[i] == 'U') {
                    ++y;
                }
                else if (s[i] == 'D') {
                    --y;
                }
                else if (s[i] == 'R') {
                    ++x;
                }
                else {
                    --x;
                }
                a[x][y] = true;
            }
            rep(i, n + 1) {
                rep(j, n + 1) {
                    cout << (a[j][n - i] == true ? 0 : 1);
                    if (j != n)cout << ' ';
                }
                cout << '\n';
            }
    return 0;
}

L

using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
        int n;
    scanf("%d", &n);
    vector<int> a(n);
    rep(i, n)scanf("%d", &a[i]);
    vector<ll> r(n + 1);
    r[0] = 0;
    rep(i, n) {
        r[i + 1] = r[i] ^ a[i];
        //printf("%lld\n", r[i + 1]);
    }
    unordered_map<ll, ll> aa = {};
    for (auto aaa : r) {
        ++aa[aaa];
    }
    ll ans = 0;
    for (auto aaa : aa) {
        //if (aaa.second > 1)printf("%lld\n", aaa.first);
        ans += aaa.second * (aaa.second - 1) / 2;
    }
    printf("%lld\n", ans); 
    return 0;
}

P

using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); ++i)
const ll INF = 1e9;

void dfs(int now, vector<vector<int>> ki, int flag, ll& ans, int n, ll cost) {
    if (flag == (1 << n) - 1) {
        ans = min(ans, cost);
        return;
    }
    else {
        rep(i, n) {
            int next = ki[now][i];
            if ((flag & (1 << i)) == 0 && next != 0) {
                dfs(i, ki, flag + (1 << i), ans, n, cost + ki[now][i]);
            }
        }
    }
}

int main() {
                int n, m, a, b, c, flag = 0;
            ll ans = INF;
            cin >> n >> m;
            vector<vector<int>> tree(n, vector<int>(n));
            rep(i, m) {
                cin >> a >> b >> c;
                tree[a - 1][b - 1] = c;
                tree[b - 1][a - 1] = c;
            }
            ll cost = 0;
            dfs(0, tree, flag + 1, ans, n, cost);
            cout << ans << endl;
    return 0;
}

2019-10-14

Beginners After Typhoon Contest解説・講評

それぞれ以下のリンクに講評・解説があります。裏話？みたいなのは別記事にします。

講評

18:09:訂正しました。

解説

writer:null(by null)
追記:ソースコードはこちら
 B
C
F
G
L
P
leafirbyさん(全問題の解説を書いてくれました。感謝！)
editorial
Nanashiくん
解説

各位、ここまで形にしてくださってありがとうございました！
思ったより多くの参加者がいて感動しました。ご参加ありがとうございました。

やったこと

やったこと

BITについて

クエリ

実装

個人的な実装の話

問題

始めに

反省点

他思ったことなど

次回どうしよっかなって話

ご参加ありがとうございました！次回もお待ちしてます！

B

C

F

G

L

P

解説