2020-06-22

AtCoderで青色になりました

苦節1年4ヶ月、ようやく青色になりました

おぉぉっっぉっっぉぉぉぉおおあ

SashimingさんのAtCoder Beginner Contest 171での成績：306位
パフォーマンス：2030相当
レーティング：1566→1621 (+55) :)
Highestを更新し、2 級になりました！#AtCoder #ABC171 https://t.co/Kf8jllJ2sE pic.twitter.com/IIevL2ye4u
— sashiming🐟 (@sashiming_syumi) 2020年6月21日

やったこと

Educational DP Contest をやる

DP力が多少必要なのでこれで鍛えましょう　JOI 過去問もおすすめ

こどふぉの問題を解く

こどふぉは単純に問題数がバカ多いので練習がたくさんできます

生活習慣ぶっ壊れる覚悟さえあればこどふぉのレートは勝手に上がります

レートを気にせず楽しむ

「レートを冷やすは、いとをかし」の精神でやりましょう　どうしても冷えてかなしいときはうしさんの -285 を見て笑顔になりましょう

すごいことになっている pic.twitter.com/Ti9gb7Ztbs
— 🐮😁 (@ei1333) 2020年3月3日

おわり

青色達成おめでとう

黄色目指して頑張りましょう

2019-12-10

JOI 2019/2020 2次予選感想

競プロ

ABCDの4完でした f:id:sashiming:20191210140255p:plain

以下、解いた順に書いていきます

A問題 - ポスター

一瞬ん？となったけど各方向について全部のマスを見るだけです、はい
ところで謎関数書いてないか？

f:id:sashiming:20191210140952p:plain:w400:left

C問題 - 桁和

桁和の文字列見た瞬間身構えたけど、そんなに難しくなかった

$1$ から $N$ それぞれについて、もとの数と一回操作した後の数を UnionFind 上で unite させる
すると、 $N$ を含む集合の size をとるだけで答えが求められる

集合サイズを求められる UF のライブラリを持ってたら一瞬で解ける

ところで桁和求める関数の実装がスマートじゃなくない？めっちゃ緊張してますね

f:id:sashiming:20191210142856p:plain:w450:left

B問題 - いちご

Cよりは難しいと思う

最遠点には出来るだけ早く到着しないとダメそうなお気持ちを察したので、とりあえずスタート直後は最遠点に直行
帰りに残りのイチゴを回収していく感じ

そしてクソ実装、まあ通ったからヨシ！

f:id:sashiming:20191210144034p:plain:w500:left

D問題 - テンキー

脳死桁 DP 笑　これしか浮かばなかった
多分 10 桁で十分だろうな～、でも一応 15 桁取っとくか～という気持ちで投げたけど、14 桁で落ちるケースがあるらしくびっくり　あぶねー

ところで 15 桁で十分な証明をしていませんよね？ダメですねえ

以下実装 (dist 配列は各キー間の移動距離を埋め込んだ)

f:id:sashiming:20191210144537p:plain:left

ちなみに提出結果はこの通り　時間ギリギリだけど剰余演算最適化したらはやくなりそう

f:id:sashiming:20191210144752p:plain

E問題 - じゃんけん式

なにこれ笑

構文解析をやったことないので Google 先生の力で 20 点取ろうとしたものの、めっちゃバグりまくった　うく

終了後に見返したら、20 点狙いより満点狙いのほうがやりやすいと感じた　最初から諦めるのはやめましょう

おわり

多分 2 次予選通過ですね、対戦ありがとうございました

2019-03-10

ABC121 D - XOR World メモ

競プロ AtCoder AtCoder Beginner Contest 400点

XORの性質とか知らないのでアでした、あと D 解けてる人多くてビックリ

問題概要

$A$ 以上 $B$ 以下の全ての整数の XOR 和を求めよ。

制約： $0 \leq A \leq B \leq 10^{12}$

問題リンクはこちらから

解説

ここからは $N$ と $M$ の XOR を $N \oplus M$ で表すことにします。

言い換え

XOR の性質として、

同じ数の XOR は０ ： $A \oplus A = 0$

があります。

問題上の $f(A, B)$ は、この性質を用いれば

$f(A, B) = f(0,B) \oplus f(0,A-1)$

これは $0$ 以上 $A-1$ 以下の部分で数がダブり、その部分における XOR 和が 0 になるからです。

よって、 $A$ から $B$ までの XOR 和は、 $0$ から $A-1$ までの XOR 和と $0$ から $B$ までの XOR 和の XOR と等しくなります。

0からXまでのXOR和を求める

以上のことから、 $0$ から $A-1$ までの XOR 和と $0$ から $B$ までの XOR 和さえ求めればよいです。

ここで実験。適当に $x=0,1,\cdots,15$ で $f(0,x)$ を求めると

 x    bin    f(0,x)
-------------------
 0    0000    0000
 1    0001    0001
 2    0010    0011
 3    0011    0000

 4    0100    0100
 5    0101    0001
 6    0110    0111
 7    0111    0000

 8    1000    1000
 9    1001    0001
10    1010    1011
11    1011    0000

12    1100    1100
13    1101    0001
14    1110    1111
15    1111    0000

実験より、 $x \% 4$ が

$0$ のとき： $f(0,x) = x$
$1$ のとき： $f(0,x) = 1$
$2$ のとき： $f(0,x) = x+1$
$3$ のとき： $f(0,x) = 0$

となります。これで $f(0,x)$ が求められるようになったので、この問題は解けました。

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(void){
    ll a, b; cin >> a >> b; a--;
    ll xa, xb;
    if(a % 4 == 0) xa = a;
    else if(a % 4 == 1) xa = 1;
    else if(a % 4 == 2) xa = a+1;
    else xa = 0;

    if(b % 4 == 0) xb = b;
    else if(b % 4 == 1) xb = 1;
    else if(b % 4 == 2) xb = b+1;
    else xb = 0;

    cout << (ll)(xa^xb) << endl;

    return 0;
}

2019-02-10

ABC110 D - Factorization メモ

競プロ AtCoder AtCoder Beginner Contest 400点

逆元の mod のとり方を知ったので自分用にメモ。

問題はこちらから

atcoder.jp

大まかな解き方

問題を解く上での考え方は単純。 $M$ の素因数の種類の数を $k$ として、

$M = {p_1}^{b_1} \times {p_2}^{b_2} \times \cdots \times {p_k}^{b_k}$

と素因数分解されるとします。

それぞれの素因数 $p_i$ が $b_i$ 個あるので、これらを $N$ 個のグループに分配します（０個のグループがあってもよい）。この分け方の総数は ${}_{N+{b_i}-1}\mathrm{C}_{b_i}(={}_{N}\mathrm{H}_{b_i})$ です（１列に並んだ $b_i$ 個の ◯ を $N-1$ 本の区切りで分けると考えればよいです、下図参照）。

この値を $i = 1, 2, \cdots , k$ のそれぞれについて全てかけ合わせたものを 1e9+7 (= 1000000007)で割った余りが答えです。
要するに

$\displaystyle \left( \prod_{i=1}^k {}_{N+{b_i}-1}\mathrm{C}_{b_i} \right) \bmod 10^{9}+7$

が答えです。

f:id:sashiming:20190202191504p:plain:w500

問題点

${}_{N+{b_i}-1}\mathrm{C}_{b_i}$ を愚直に求めて mod をとろうとしても、値が long long でも扱えないほどクソでかくなるときが出てきます。 ${}_{10^{5}}\mathrm{C}_{10}$ の時点でムリです。これを解決するにはどうすればいいでしょうか？

解法

${\displaystyle {}_{n}\mathrm{C}_{r} = \frac{n!}{r!(n-r)!} }$ の定義に除算が入っているので、通常では計算途中に mod 計算をすることができません。しかし、次のようにすれば除算でも mod をとることが出来ます。

ここからは ${\frac{b}{a}}$ の mod をとることについて考えましょう。

${\frac{b}{a} = b \times a^{-1}}$ なので、 ${\frac{1}{a}}$ の mod をとることは $a^{-1}$ の mod をとることと同義です。（ちなみに $a^{-1}$ のことを $a$ の逆元と呼びます）

ここで、フェルマーの小定理より

$\displaystyle a^{p-1} \equiv 1 \pmod{p} \quad (a,p \,$ は互いに素 $)$

この両辺に $a^{-1}$ をかけて、

$\displaystyle a^{p-2} \equiv a^{-1} \pmod{p} \quad (a,p \,$ は互いに素 $)$

（p = 1e9+7 であり、1e9+7 は素数なので、a が p の倍数でない限り a, p は互いに素になります。今回の場合、制約上 a が p の倍数になることはないためフェルマーの小定理が適用できます）

以上より、 $b \div a$ の答えを $p$ で割った余りは、 $b \times a^{p-2}$ を $p$ で割った余りに等しいです。

${}_{n}\mathrm{C}_{r}$ の定義は次のように変形されます。

${\displaystyle {}_{n} \mathrm{C} _{r} = \frac{n!}{r!(n-r)!} = n! \times {r!}^{-1} \times {(n-r)!}^{-1} }$

剰余を求めたいので、 $a^{p-2} \equiv a^{-1} \pmod{p}$ を利用して

${\displaystyle {}_{n} \mathrm{C} _{r} \equiv n! \times {r!}^{-1} \times {(n-r)!}^{-1} \equiv n! \times {r!}^{p-2} \times {(n-r)!}^{p-2} \pmod{p} }$

コード解説

ACコードは以下の通りです。（そこそこ長いです。もっと洗練できるかも）

#include <bits/stdc++.h>
using namespace std;
#define int long long // 簡略化のため longlong を int に
const long long MOD = 1e9+7;

int fact[150000], revfact[150000]; // fact[i]はiまでの階乗、revfact[i]はiまでの階乗の逆元
queue<int> prime_count;

int powmod(int a, int p){
    int res = 1, tmp = a;
    while(p != 0){
        if(p % 2) res = (res*tmp) % MOD;
        tmp = (tmp*tmp) % MOD;
        p /= 2;
    }
    return res;
}

void factmod(){
    fact[0] = revfact[0] = 1;
    for(int i = 1; i < 150000; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        revfact[i] = (revfact[i-1] * powmod(i, MOD-2)) % MOD;
    }
}

int nCrmod(int n, int r){ // nCr % MOD
    return (((fact[n] * revfact[r]) % MOD) * revfact[n-r]) % MOD;
}

signed main(){ // ここの signed を int にするとCEします
    int N, M; cin >> N >> M;

    for(int i = 2; i <= sqrt(M); i++){ // 素因数分解して指数を queue に突っ込む
        if(M % i == 0){
            int cnt = 0;
            while(M % i == 0){
                M /= i;
                cnt++;
            }
            prime_count.push(cnt);
        }
        if(M == 1) break;
    }
    if(M != 1) prime_count.push(1); // Mが素数の場合はqueueに1だけが入ることになります

    factmod();

    int ans = 1;
    while(!prime_count.empty()){
        int bi = prime_count.front();
        ans *= nCrmod(N+bi-1, bi); ans %= MOD;
        prime_count.pop();
    }
    cout << ans << endl;

    return 0;
}

一部分ずつ解説していきます。

int powmod(int a, int p){
    int res = 1, tmp = a;
    while(p != 0){
        if(p % 2)
            res = (res*tmp) % MOD;
        tmp = (tmp*tmp) % MOD;
        p /= 2;
    }
    return res;
}

$a^{p}$ (mod 1e9+7) を計算します。
今回の場合、 $p = 10^{9}+5$ なので、通常の累乗の求め方（計算量 $O(p)$ ）ではTLEしてしまいます。

そこで、繰り返し二乗法という手法を使います。

例として $187^{82}$ について考えることにしましょう。 $187^{82}$ は次のように変形されます。

$\begin{align} 187^{82} & = 187^{64} \times 187^{16} \times 187^{2} \\ & = 187^{2^{6}} \times 187^{2^{4}} \times 187^{2^{1}} \end{align}$

次に、指数である $82$ を２進数で表すと $1010010$ です。ここで、ビットが立っているところは $187^{82}$ を分解した時のそれぞれの指数に対応しています。
したがって、 $187^{82}$ は $187^{2^{1}} , 187^{2^{2}} , \cdots , 187^{2^{6}}$ をそれぞれ計算すると求められます。
（僕の説明はわかりにくいのでこちらを参考にすると良いと思います）

繰り返し二乗法を使うと、 $a^{p}$ が $O(\log{p})$ と高速に求められます。

void factmod(){
    fact[0] = revfact[0] = 1;
    for(int i = 1; i < 150000; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        revfact[i] = (revfact[i-1] * powmod(i, MOD-2)) % MOD;
    }
}

fact[i] は i までの階乗 (mod 1e9+7)の配列、revfact[i] は i までの階乗の逆元 (mod 1e9+7) の配列です。制約上、150000 ぐらいまで計算しておけば十分です。十分すぎるくらいです。

そのままの階乗の計算は特に言うことはありませんが、 $a$ の階乗の逆元の計算は

$\begin{align} \displaystyle ({a!})^{-1} & = \frac{1}{a!} \\ &= \frac{1}{(a-1)!} \times \frac{1}{a} \\ &= (a-1)!^{-1} \times a^{-1} \end{align}$

で求められます。

int nCrmod(int n, int r){
    return (((fact[n] * revfact[r]) % MOD) * revfact[n-r]) % MOD;
}

nCr (mod 1e9+7) を求めています。nCr の定義の通りに計算しています。

${\displaystyle {}_{n} \mathrm{C} _{r} = n! \times {r!}^{-1} \times {(n-r)!}^{-1} }$

for(int i = 2; i <= sqrt(M); i++){
    if(M % i == 0){
        int cnt = 0;
        while(M % i == 0){
            M /= i;
            cnt++;
        }
        prime_count.push(cnt);
    }
    if(M == 1) break;
}
if(M != 1) prime_count.push(1); // Mが素数の場合はqueueに1だけが入ることになります

$M$ を素因数分解し、指数のみを queue に突っ込んでいます（指数しか計算に利用しないためです。素因数分解をライブラリ化する場合は map で素因数を key にしておくとよさそう）。

$M$ の素因数分解では、 $2$ から $\sqrt{\mathstrut M}$ までを調べれば十分です（ $M$ が合成数の場合、 $\sqrt{\mathstrut M}$ より大きい素因数は存在しないため）。 $M$ が素数かそうでないかは、for文を抜けた後の $M$ が $1$ であるかどうかで判断できます。

さいごに

今回は「フェルマーの小定理＋繰り返し二乗法」で解きましたが、他にも解法はあります。

フェルマーの小定理＋繰り返し二乗法で逆元の mod をとる手法はよく出てくるので、ライブラリ化しておくと良いかも。
例えばこの問題だとライブラリコピペしてえい！するとささっと解けてしまいます。 atcoder.jp

＜参考にしたサイト＞

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - Qiita

ハムスターでも分かった組み合わせの余剰 - Qiita

2019-01-21

AtCoderで水色になりました

競プロ

競プロを本格的に始めてから8ヶ月ほど。ついにAtCoderで水色になりました！！

水色になっちゃった！！！
すぐ緑落ちしそう pic.twitter.com/aLuYUmARop
— 🍏さしみもち💎´ (@sashiming_syumi) 2019年1月20日

ということで、自分が水色になるまでにやったことをまとめます。

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

300点を安定して解けるようにする

正直、ABCで300点までを早解きすれば水色になれます。なので、まず300点を安定してAC出来るぐらいまで精進すると良いです。ちなみに僕はまともに400点を解けません。

Unratedコンでもできるだけ参加する

Unratedのコンテストではレートが変動しないので参加しない人も多いと思いますが、触れる問題数も増えるのでできるだけ参加しましょう。

ばちゃこんに参加する

AtCoder Virtual Contestでコンテストがしょっちゅう開かれています。これに参加することで他人と競いながら精進できるので、ばちゃるのも良さそう。

必要なテク

全探索系

ABC-Cでは、アルゴリズムを使うとしても全探索で済むことが多いように感じます（たまにDPとか出てきますが）。全探索・DFS・BFS・bit全探索ぐらいは流石に押さえておきましょう。DPもある程度押さえておくべきでしょう。

累積和

これを使うと数列のある区間の総和が ${O(1)}$ で求まるので、なかなか使えるテクニックであります。

基本的なSTLは使えるようにしときましょう。具体的には、vector, map, set, queue, stack。STLを使わないと実装がめんどくさくなるorできない問題は多いです。

己の実装力

実装で殴る問題があったりするので、実装力はある程度磨いておきましょう。実装ミスでWAったらシャレにならないからね。

ひらめき

重要。難しい問題でも、違う角度で見ればかなり簡単になることが多々あります。

さいごに

他にも二分探索とかは押さえていていて損はないですが、ざっとこんな感じ。大切なのはやはり解いた問題量です。経験の量が物を言います。

これからも精進を重ねて、もっと上の色にまで昇格したい。

もちっ

（2019.1.29追記）緑落ちは一瞬。しばらくここらへんでレート停滞しそう...？ f:id:sashiming:20190129205448p:plain

2019-01-01

新年のおきもち

あけましておめでとうございます。sashimingです。

2019年の目標は、

AtCoderで水色になる（あわよくば青）
JOI予選通過

特にJOI予選は絶対に通過したいです。あとCTFも若干触ってみたい。

2019年も†圧倒的精進†キメていきたいですね。

今年もよろしくお願いします。

（2019.1.2追記）

現在のレートはこの通りです。新年度までには水色になれるか...? f:id:sashiming:20190102122042p:plain

2018-12-09

JOI 2018/2019 予選感想

競プロ

はじめに

2回目のJOI参加。去年初めて参加したときはお試し感覚でしたが、今回はそこそこ真面目にやりました。

点数は321点 (100+100+100+15+0+6)。来年は予選通過してみたいですね。

f:id:sashiming:20181209195221p:plain

A問題

変な考え方して初っ端から2WAしたのでB, Cから解いて戻ってきた。その後にもう1WAしてようやくAC。結局変な考え方のままACしました。

１日目から毎日ログインすれば最善ですよね。当たり前ですね。

B問題

やるだけ。国語力のおはなし。

C問題

左から"ox"または"xo"となるものを順々に探せばいいです。ダブって数えてしまうミスに注意。

D問題

f:id:sashiming:20181209214751j:plain

下から順番に水位を上げていって、それぞれに島の数を求めて部分点。島の数を求めるときの水位は１刻みで考えると明らかに駄目なので島の高さの種類で考える。

満点解法は座圧とか聞きましたが、座圧知りません。精進(しなさい)。

E問題

な　ぜ　全　探　索　を　怠　っ　た

全探もやらない怠慢さで10点を逃しました。

F問題

next_permutationなりを使って順列を作って、条件に合うものの個数を求める。その後、同じ国の選手を区別するので ${A_i}$ の階乗をそれぞれかけて ${10007}$ で割った余りを出力して部分点。

ちなみに本番中は ${A_i}$ をそのままかけて求めてしまっていましたが（そのせいで入力例３の出力が4754じゃなくて6192になった）、小課題１の制約が ${A_i \leqq 2}$ なので助かりました。

まとめ

来年こそ予選通過したい！

なので全力で精進あるのみ。

sashimingの競プロメモ

チラシの裏

AtCoderで青色になりました

やったこと

おわり

JOI 2019/2020 2次予選感想

A問題 - ポスター

C問題 - 桁和

B問題 - いちご

D問題 - テンキー

E問題 - じゃんけん式

おわり

ABC121 D - XOR World メモ

問題概要

解説

言い換え

0からXまでのXOR和を求める

ABC110 D - Factorization メモ

大まかな解き方

問題点

解法

コード解説

さいごに

AtCoderで水色になりました

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

必要なテク

さいごに

新年のおきもち

JOI 2018/2019 予選感想

はじめに

A問題

B問題

C問題

D問題

E問題

F問題

まとめ