SHIINBLOG

AtCoder で水色になりました

AtCoder Beginner Contest 171 にて水色になることが出来ました!

f:id:zeronosu77108:20200622222137p:plain

色変記事なるものを1回も書いたことがないため、 AtCoder を始めた所から振り返っていきたいと思います。

ハッキリ言って、競プロ始めたばっかりのときは水色はすぐに達成できる(予定の)目標でした。 しかし、少しずつレートを上げていき、なんだかんだで1年かかりました。

今回は「水色になるために勉強したアルゴリズム」的なものではなく、お気持ちをまとめておきたいと思っています。

なぜ水色はすぐ達成できる(予定の)目標だったのか

単純に始めたばかりの頃に、水色パフォーマンスや緑後半のパフォーマンスを出せていたからです。

初めて参加したコンテストは AGC だったので、成績としてはイマイチだったのですが、その後はこんな感じでした。

f:id:zeronosu77108:20200622222204p:plain

そのため、少し練習して簡単なアルゴリズムの基礎力がつけば水色になれるだろうと思っていました。

しかし、そう甘くはありませんでした。

茶(レート400) 〜 緑(レート800) まで

レート遷移を見ても分かるように、 2019年1月頃に始めて(登録自体は3年くらい前)、2ヶ月ほどはまともに参加していませんでした。その後も練習をせずにコンテストに参加したり、遅刻参加したりとレートを溶かしていきました。 このままでは灰色に戻ってしまうと思い、精進とコンテスト時間にはちゃんと参加するということをしました。

とはいえ、少しずつ問題を解いていただけで、 Twitter の TL で見るような “異常精進” はしていません。 そのため、レート増加も緩やかでした。 緩やかでしたが、特に問題も無く順調に緑色になれたと思います。

f:id:zeronosu77108:20200622222238p:plain

緑(レート800) 〜 水(レート1200) まで

ここが苦労しました。 「パフォーマンスが低く出るようになっているのではないか?」という話がありますが、僕は数学に慣れ親しんでいる方ではないので最近の算数パズルみたいな問題が辛く、レートがふらふらしていました。

f:id:zeronosu77108:20200622222336p:plain

まず、2019年11月頃にパフォーマンスが安定しないのは、数学に慣れていないから、そういう問題に時間がかかる/解けないことが原因だと思い、簡単な問題埋めをしました。

これは効果がありました。パフォーマンスの安定感が出てきて、水色になる直前の Highest もこの時期に取りました。 簡単な問題埋めとは言え、精進がレートに直結している感じがあったのでモチベーションはかなり上がっていました。

しかし、この後です。 「ABC156 辺りから精進しているのにレートが下がる…」という感じでした。 時間をかけて Highest から100ほどレートが下がっていました。練習しているのに練習している問題が出ないどころか、算数パズルばかりが出ている印象でした。

この辺りの問題に時間がかかり(もしくは解けない)、パフォーマンスが伸びませんでした。

数え上げや、ルンルン数のような問題が苦手で、考察が全く進まないことが多くコンテスト中に「諦めたくないが、何も分からない」状態が多く辛かったです。

精進を増やしても毎回レートが下がる感じで、精神的に苦痛でした。 こんなに水色から離れて、もうずっと水色には慣れないんじゃないか。辞めようかと思っていました。

このときの精進は、上記の通り簡単な問題埋めをしていたので、この辺りで難しい問題に挑戦し解ける問題を増やす方に動けば良かったかなと思っています。

そんな感じで、2020年4月になりました。


f:id:zeronosu77108:20200622222353p:plain

社会人になったこともあり、精進は4月中盤くらいからはかなり止まっていました。 が、何故かレートは上がってきました。

さらに第3回PASTが無料なこともあり、受験してみたのですがなんと70点で中級でした。 しかも、IとKを飛ばしていて(パッと思いつかなくて飛ばした)たので「Lと同レベルか簡単なはず!これは実質上級!!」 とメンタルを回復することに成功しました。

メンタル回復が良かったのか、5月末辺りからはすごく大きな失敗はなく、順調にレートが上がり水色になる事が出来ました。

f:id:zeronosu77108:20200622222420p:plain

今後の精進について

前から思っていたのですが、数学的な考察よりも実装の方が得意なようです。次のABCで緑Diffの数学的考察の入った問題が出たら解けるか怪しいです。下手したら緑に戻ってしまうかもしれません。

また、上記で書いていたような「簡単な問題を埋める」というのは作業感が強くレートが下がってしまったときにメンタルに良くない事が分かりました。

そこで、今後は緑上位Diff や数学問題をメインに精進していきたいと思います。

現在の目標としては、 maspy さんがツイートしていた yukicoder の 星1.5〜2の数学チックな問題を埋めていきたいと思っています。 その後は、苦手な数え上げ人並みにできるようにしたいと思っています。

パナソニックプログラミングコンテスト2020

最近まとめてなかったのですが,昨日は酷すぎたので,まとめておきます. パナソニックプログラミングコンテスト2020

C 問題,誤差に関する知識がなさすぎるのに誤差を消そうと頑張って 11WA しました(?) 結局 C 問題は力技で通しました.

久しぶりに茶パフォ取りました.酷すぎます.

D 問題を先に解いておけば良かったです. C 解いた後の脳みそで D 問題を考察していたのがよろしくないです.


A - Kth Term

問題文

コピペして vector に初期値として入れました.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    vector<int> n = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << n[k-1] << endl;
}



B - Greedy Takahashi

問題文

「サンプルめっちゃ易しいじゃん〜」と  H \times W / 2 周辺ということがすぐにわかって調子に乗ったら  H = 1 のときと  W = 1 のコーナーケースに引っかかって WA 直しました.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int64 h,w;
    cin >> h >> w;
    if (h == 1 || w == 1) {
        cout << 1 << endl;
        return 0;
    }
    cout << (h*w+1) / 2 << endl;
}



C - Sqrt Inequality

問題文

予想はしていましたが,誤差で死にました.
どうやって解いたらいいかわかりません.

大きな値のときに誤差が生まれそうだということに気がついたので,
最大公約数で割るという力技で通しました.
大きな互いに素な値が与えられると死にます.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

typedef long double ld;

int64 gcd(int64 a, int64 b) { return b? gcd(b,a%b):a; }; int64 lcm(int64 a, int64 b) { return a/gcd(a,b)*b; };


int main() {
    int64 a,b,c;
    cin >> a >> b >> c;
    int64 GCD = gcd(a,b);
    GCD = gcd(GCD, c);
    a /= GCD;
    b /= GCD;
    c /= GCD;

    if ( sqrt(a) + sqrt(b) < sqrt(c) ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


この問題はきちんと式変形をすることで整数だけで判定できるらしいです.
自分でやってみると普通に出来ました(最初からやってください)

 \sqrt{a} + \sqrt{b} \lt \sqrt{c}
両辺を二乗して  (\sqrt{a} + \sqrt{b}) ^ 2 \lt c  = a + b + 2\sqrt{ab} \lt c
ここまででも解ける可能性があるけど,念のため全部整数に落とすと,
 4ab \lt (c - (a+b)) ^2 で,  c - (a+b) がマイナスになるパターンは省く必要があるのでテキトーに条件書くと通るみたいです.

int main() {
    int64 a,b,c;
    cin >> a >> b >> c;

    int64 x = c - a - b;
    if ( x > 0 && 4*a*b < x*x ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



D - String Equivalence

問題文

C で 11 WA した後です.冷静であるはずがありません(?)

 N = 3 のときに, 1文字目に b や c が来るのはおかしくて, 2文字目にc が来るのはおかしいなぁと考察していたはずなのに,
実装にしたら頭がバグっていました. こんなかんじ

ちゃんと実装したら結構綺麗に書けました. 1文字目を決めるときは, 'a' + 0 までしかしない.
2文字目を決めるときは, `'a' + 1' までしかしない.

と決めていくと良い感じになりました.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;
void dfs(string s, const int& t, const int& n, set<string>& ans) {
    if (s.size() == n) {
        ans.insert(s);
        return;
    }

    for (int i=0; i<=t; i++) {
        string ts = s + (char)('a' + i);
        if (i == t)
            dfs(ts, t+1, n, ans);
        else
            dfs(ts, t, n, ans);
    }
}

int main() {
    int n;
    cin >> n;

    set<string> ans;
    dfs("", 0, n, ans);

    for (auto s : ans)
        cout << s << endl;
}



E 問題以降は黄色だったのでまだ見てません.

まとめ

小数は悪

AtCoder Beginner Contest 149

はい. AtCoder Beginner Contest 149 です
本当は ABC146,147 を先に書かないといけないんですけど,このままだと永遠にスタックされていきそうなので,とりあえず ABC149 について書きます.
ABC148の記事 のときにも言ってた気がする…

Unrated になってしまって残念ですが,一応 ABCDの4完でした.
そんなに難しくなかったかな?
参考までに順位表を

f:id:zeronosu77108:20191229215713p:plain

A 問題を勘違いして 1度  S ~ T の順で提出してしまったのが辛いですね.


A - Strings

問題文

文字列を連結して出力するだけです.
※順番は間違えないように

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    string s,t;
    cin >> s >> t;
    cout << t << s << endl;
}



B - Greedy Takahashi

問題文

高橋君のクッキーを食べられるだけ食べて,次に青木君のクッキーを食べられるだけ食べる.

高橋君の食べるクッキーが  A - K枚で,青木君が食べるクッキーが  B - (K-A) 枚です.
そんな感じです.

 0max 取ってるのは, 負数になったときの対応です.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    int64 a,b,k;
    cin >> a >> b >> k;
    cout << max(0LL, a - k) << " ";
    cout << max(0LL, b - max(0LL, k-a)) << endl;
}



C - Next Prime

問題文

 X 以上の素数のうち最小のものを出力してくださいというシンプルな問題.
エラストテネスのふるい で素数列挙して求めました.

 2X まで探索すれば  X 以上の素数は見つかるだろうと思ってましたが,
どれくらい探索したら良いのかよく分かっていません.

素数列挙出来たら,素数vector から lower_bound するだけです.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;

vector<int64> Eratosthenes(  int64 N )
{
    N *= 2;
    vector<int64> p;
    vector<bool> is_prime(N+1, true);
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            p.emplace_back( i );
        }
    }
    return p;
}

int main() {
    int64 x;
    cin >> x;
    vector<int64> ans = Eratosthenes(x);
    cout << *lower_bound(ans.begin(), ans.end(), x) << endl;
}



D - Prediction and Restriction

問題文

感覚的に,rrr とかになったときに奇数番目を勝つように選んでいけば良さそうと思って実装しました(  K=1 以外でも).
通りました.

実装に関しては.もう少しましな方法があった気もしますが,map<char, int> で,
win['r'] みたいな感じでアクセスできるようにしました.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;



int main() {
    int n,k,r,s,p;
    int64 ans = 0;
    string t;

    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> t;

    map<char, int64> win;
    win['r'] = p;
    win['p'] = s;
    win['s'] = r;


    vector<vector<int64>> dp(n+1, vector<int64> (3, 0));

    for (int i=0; i<n; i++) {
        if (i < k) ans += win[t[i]];
        else if (t[i-k] != t[i]) ans += win[t[i]];
        else t[i] = '-';
    }

    cout << ans << endl;
}



E - Handshake

問題文

なんか二分探索っぽい雰囲気を感じたんですけど,その他の実装が 1ミリも思い浮かばなかったので実装出来ませんでした.

最近,レート下がりすぎて悔しいので,近いうち勉強してプログラムと解説載せます.

まとめ

Unrated になったのが悲しかったです.
次までに精進します.

AtCoder Beginner Contest 148

はい. AtCoder Beginner Contest 148 です
本当は ABC146,147 を先に書かないといけないんですけど,このままだと永遠にスタックされていきそうなので,とりあえず ABC148 について書きます.

ABCDの4完でした.結構簡単だったみたいで,パフォーマンス低かったです…
E が解けませんでした.解きたかった_(:3」∠)_
F も時間があってちゃんと考察したら解けそうな気がしています(気がしているだけ)


A - Round One

問題文

選択肢が  1,2,3 であり,選択肢  A,B が誤答だと分かっているようです.
合計が 6 であることが分かっているので,  6 - A - B を出力すれば良いです.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    int a,b;
    cin >> a >> b;
    cout << 6 - a - b << endl;
}



B - Strings with the Same Length

問題文

長さが同じなので,交互に出力するだけです.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    int n;
    string s,t;
    cin >> n >> s >> t;

    for (int i=0; i<n; i++) cout << s[i] << t[i];
    cout << endl;
}



C - Snack

問題文

 A,B で割り切れる最小の数を出力すれば良いので,最小公倍数を求めます.
最小公倍数(LCM)は, \frac{A \times B}{GCD(最大公約数)} ですね.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;

int64 gcd(int64 a,int64 b){return b?gcd(b,a%b):a;}

int main() {
    int64 a,b;
    cin >> a >> b;
    int64 GCD = gcd(a,b);
    int64 ans = a*b/GCD;
    cout << ans << endl;
}



D - Brick Break

問題文

順番に 1,2,3,\cdots とならないといけないので,
 1が来るまでレンガを割り続ける, 2 が来るまで… とやっていけば良いです.

そして,1回も1 が出てこなければそういう列が作れません.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;


int main() {
    int64 n;
    cin >> n;
    vector<int64> a(n);
    for (int i=0; i<n; i++) cin >> a[i];

    int64 ans = 0;
    bool flag = false;
    int64 i = 1;
    for (int j=0; j<n; j++) {
        if (a[j] != i) ans++;
        else i++,flag=true;
    }

    cout << (flag? ans : -1) << endl;
}



E - Double Factorial /

問題文

考察不足でした.10が何個あるか数えてたんですけど,
2 は大量にあるため, 5 が何個あるか(入るか)数えるだけで良かったです.
10以下であることを避けるために最初だけ10で割ります)

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

typedef long long int64;

int main() {
    int64 n;
    int64 ans = 0;
    cin >> n;
    if (n%2) {
        cout << 0 << endl;
        return 0;
    }

    ans += n /= 10;
    while(n != 0) {
        ans += n /= 5;
    }

    cout << ans << endl;
    return 0;
}

まとめ

またレート下がりました_(:3」∠)_
E問題は「 1331! の下桁に0はいくつ連続するか」という問題と本質的に同じ問題みたいです(↓参考).

中学受験とか高校受験にこんな問題出るんですか(無知).
こういう知識ないので,辛い_(:3」∠)_



参考

きょうぷろたのしいよ

琉大 Advent Calendar 2019 3日目です.

記事用意するの忘れていました_(:3」∠)_
そのため,構成・内容が微妙かもしれません.

タイトル通り競プロの話をします.
(開催時間の関係で)基本的に AtCoder しか参加していないので, AtCoder の話がメインです.

僕自身まだ始めたばかりの初心者なので,すごいアルゴリズムの解説!
とかはしない予定です.

競プロとは

ある期間(時間)内にパズルのような問題をプログラミングして解くものです.
AtCoder では毎月数回 ,1回90分のコンテストがあります.

こんな感じの問題が出ます. https://atcoder.jp/contests/abc145/tasks/abc145_a

整数 r が与えられ,その r を半径とした円が,半径 1の円の面積の何倍になりますか.
という問題ですね.

円の面積の公式が分かれば,すぐに求められますね.
 r ^ 2 \pi なので,  r ^ 2 が答えになりますね.
競プロでは C++ で解いている人が多いので, C++PythonRuby で解いてみます.

// ABC145A.cpp
#include <iostream>

using namespace std;

int main() {
    int r;
    cin >> r;

    cout << r*r << endl;
}
# ABC145A.py
r = int(input())

print(r*r)
# ABC145A.rb
r = get_s.to_i

puts r*r

各言語,入力を取って  r \times r を出力すれば良いですね.
簡単でしょ?



競プロやって何が嬉しいのか

プログラムを書く習慣ができる

AtCoder Beginner Contest というビギナー向けのコンテストが月に2回くらいは開催されます.
これに参加するだけで,定期的にプログラムを書く習慣ができます.

さらにやる気が出たときは,過去問などで復習することができます.
最初のうちは,言語の実行速度が問題になることは少ないと思うので, AtCoder にある好きな言語でプログラミングの練習ができて良いです.

実装力・実装速度が上がる

数学っぽい問題もありますが,実装力が必要な問題もちょいちょいあります.
そういう問題を解くことによって,実装力がつきます.
後は,いろいろなアルゴリズムの知識が必要になるので, そういうアルゴリズムを実装できるようになります.

また,コンテストに参加すると,問題を解くと点数がもらえて,同点の場合は解いた時刻が順位に影響します. 参加しているうちに簡単なアルゴリズムであれば,一瞬で思いついて,すぐに実装することができるようになります.
AtCoder の chokudai さんがこういうツイートをしています.
https://twitter.com/chokudai/status/1153528912531451905?s=20

競プロ強くなるとロジック単位の実装に強くなります.
場合によっては,就職にも有利になるかもしれません.
まぁ,競プロで書くプログラムは使い捨てになることが多いので,そのまま業務で使えることはないでしょうけど…

計算量を見積もることができるようになる

一般に短時間のコンテストは2秒程度の時間制限があります.
つまり,愚直な解法だと2秒以内に終わらないことがあります.

そこで,計算量を見積もって,大きい場合は減らす必要がでてきます. 上記のロジック単位の実装とも被りますが,そういうところに強くなれます(雑).

ie にも 競プロやっているひと結構居ます

多分います(少なくとも僕はやってます).
競プロの話題で先輩と仲良くなりましょう!!

僕もできる限り,解いた問題はブログに書いているので少しでも参考になれば良いなと思います.

楽しい

上に書いていることは建前で,単純に問題を解くのが楽しいです.
解けないと禿げそうになりますが,そういう問題が解けたときのうれしさは特に大きいです.



まとめ

プログラミング1で Python 習ったし,競プロ解いてみるか〜という感じで解いてみましょう!
いくつか競プロっぽい問題が解けるサイトをあげておきますが,とりあえず AtCoder のコンテストに参加してみると良いと思います(とは言ったものの近々ビギナーコンテストがない…).

何か分からない事があれば @e145755 にリプでも送ってもらえると,手伝いできるかと!



競プロ関係のサイト

日本語でできるやつだけ上げておきます.

  • AtCoder 日本だと一番人気だと思います?
  • AIZU ONLINE JUDGE たくさん問題があります.
  • yukicoder 競プロの模試・勉強会の位置づけを目指しているみたいです.結構問題あるし,ちょいちょいコンテストも開かれてます.
  • paiza paiza は競プロじゃないですが,スキルチェックが競プロの形式とほぼ同じです.

AtCoder Beginner Contest 145

はい. AtCoder Beginner Contest 145 です

ABCの3完でした.
Dが解けませんでした…辛い…

f:id:zeronosu77108:20191127133436p:plain


A - Circle

問題文

 R \times R を出力するだけですね.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int r;
    cin >> r;

    cout << r*r << endl;
}



B - Echo

問題文

 N が奇数だとそもそも半分で分けることが無理なので No します.
後は, substr で半分ずつに分けて判定します.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    if (n % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }

    if (s.substr(0,n/2) == s.substr(n/2, n/2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



C - Average Length

問題文

 N \leq 8 だから, 全列挙しても間に合うはずなので,next_permutation で列挙します.
next_permutation はソートしておく必要があるんだけど, x,y をまとめてソートするのがめんどくさかったので, iota で連続した数列を作ってそれを使いました)

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;

long long frac(long long n) {
    long long res = 1;
    for (int i=1; i<=n; i++) res *= i;
    return res;
}
int main() {
    long long n;
    long double ans = 0;
    long double sum = 0;
    cin >> n;
    vector<long double> x(n);
    vector<long double> y(n);

    for (int i=0; i<n; i++) cin>>x[i]>>y[i];

    vector<int> c(n);
    iota(c.begin(), c.end(), 0);

    do {
        for (int i=0; i<n-1; i++) {
            sum += sqrt( pow(x[c[i]]-x[c[i+1]],2) + pow(y[c[i]]-y[c[i+1]],2));
        }
    } while(next_permutation(c.begin(), c.end()));

    cout << setprecision(14) << (sum/frac(n)) << endl;
}



D - Knight

問題文

コンビネーションで求められることは分かっていたんですが,いろいろダメでした
辛い…

コンテスト後にときました.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

const long long mod = 1e9+7;
struct mint {
  long long x;
  mint(const long long x=0) : x(x%mod) {}
  mint& operator+=(const mint a) {if((x+=a.x)>=mod)x-=mod; return *this;}
  mint& operator-=(const mint a) {if((x+=mod-a.x)>=mod)x-=mod; return *this;}
  mint& operator*=(const mint a) {(x*=a.x) %= mod; return *this;}
  mint& operator+(const mint a) const {mint res(*this); return res+=a;}
  mint& operator-(const mint a) const {mint res(*this); return res-=a;}
  mint& operator*(const mint a) const {mint res(*this); return res*=a;}
  mint pow(long long t) const {
    if (!t) return 1;
    mint a = pow(t>>1); a*=a;
    if(t&1) a*= *this;
    return a;
  }
  mint inv() const {return pow(mod-2);}
  mint& operator/=(const mint a) {return (*this) *= a.inv();}
  mint& operator/(const mint a) const {mint res(*this); return res/=a;}
};

mint fact(long long n) {
  mint res = 1;
  for (long long i=n; i>0; i--) res*=i;
  return res;
}

int main() {
  long long x,y;
  cin >> x >> y;

  if ((x+y)%3 != 0) {
    puts("0");
    return 0;
  }

  long long a = (2*x-y)/3;
  long long c = (2*y-x)/3;

  if (a<0 || c<0) {
    puts("0");
    return 0;
  }

  mint ans = fact(a+c);
  ans /= fact(a);
  ans /= fact(c);
  cout << ans.x << endl;
  return 0;
}



まとめ

レート微増(+2)でした.
最近下がりっぱなしだったので,少しましですね…

次はもっと頑張ります

E 問題解けたら更新します.

AtCoder Beginner Contest 144

はい. AtCoder Beginner Contest 144 です

ABCの3完でした.
DとEは時間内に見ていたのですが,Dは場合分けがダメでした(数式でゴニョゴニョして atan しようとしていた).

E は,ソートして反対向きにマッチングさせるっていう所までは考えたんだけど,その後の処理が分かりませんでした.
二分探索すれば良かったらしい.

f:id:zeronosu77108:20191103163004p:plain


A - 9x9

問題文

九九を覚えたって可愛いな〜と思いながら書いてました.
まぁ,そんな感じ.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;
  cout << ((a<=9&&b<=9)? a*b : -1) << endl;
}



B - 81

問題文

1 から 9 までで商が9以下になって,余りが0なら満たします.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  bool ans = false;

  for (int i=1; i<=9; i++) {
    if (n/i<=9 && n%i==0) ans = true;
  }

  cout << (ans? "Yes" : "No") << endl;
}



C - Walk on Multiplication Table

問題文

愚直に探索するだけです.
 i \times j N になる組み合わせを全部探して,その和の最小値を求めます.
ただ,計算量を減らす必要があって, \sqrt{N} まで探索するようにします.

10 の約数は, 1,2,5,10 だけど, \sqrt{10}=3.1\cdots まで探索したら,  \frac{10}{1} = 10 \frac{10}{2} = 5 となって,  \sqrt{10} より大きい値は探索しなく良いです.

これで探索範囲が  10^ {12} から  10^ 6 になるので, \mathcal{O}(N) でも間に合います.

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long n;
  cin >> n;
  long ans = LONG_MAX;

  long stop = sqrt(n);
  for (int i=1; i<=stop; i++) {
    if (n%i==0) ans = min(ans, i+n/i);
  }
  
  cout << ans-2 << endl;
}



D - Water Bottle

問題文

解説をなんとなく聞いて,自分で式おこしして解いてみました.  A \times B の面積で考えることができるので,最初に次元を落としておきます.

そして, A \times B の面積の半分を超えない場合は,単純な三角形で考えることができます.
面積の半分を超える場合は,四角形の上に三角形が乗っているような形になるので,三角形部分を atan すれば良いです.

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long double a,b,x;
  long double ans;
  cin >> a >> b >> x;

  x /= a; // 奥行きを消す(平面で考える)

  // 半分より多いか少ないかで場合分けをする
  if (x <= a*b/2) { 
    ans = atan2(b, 2*x/b);
  } else {
    ans = atan2(2*(b-x/a), a);
    // 反対側の三角形から高さを求める.
    /*
      h = 2*(a*b -x) / a
        = 2*(b - x/a)
    */
  }

  cout << setprecision(14) << ans * 180.0 / M_PI << endl;
}



E - Gluttony

問題文

基本的に,片方を昇順にしてもう片方を降順にして同じインデックスのものを組み合わせると最小値になります.
このときに, K 回の操作を上手くしたときの最小値を求めるのが分からなかった.

こういう問題は二分探索するみたいです.
コンテスト後に解いたんですけど,二分探索書き方忘れていて,苦労しました.

後は,long long じゃないと通らなかった…

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;


int main() {
  long long n,k;
  cin >> n >> k;
  vector<long long> a(n);
  vector<long long> f(n);

  for (int i=0; i<n; i++) cin>>a[i];
  for (int i=0; i<n; i++) cin>>f[i];

  sort(a.begin(),a.end());
  sort(f.rbegin(),f.rend());

  long long l = -1;
  long long r = 1e12;
  while(l+1 < r) {
    long long g = (l+r)/2;
    bool flag = true;

    long long count = 0;
    for (long long i=0; i<n; i++) {
      count += max(0LL,(a[i] - g/f[i]));
      if (count > k) {
        flag=false;
        break;
      }
    }
    (flag? r : l) = g;
  }

  cout << r << endl;
}



まとめ

またレート下がってしまいました…
三角関数弱者なので辛い…

DやEみたいな問題がまだ練習できていないと分かったので,良かったといえば良かったです.
次はレート上げられるように頑張ります.