SHIINBLOG

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みたいな問題がまだ練習できていないと分かったので,良かったといえば良かったです.
次はレート上げられるように頑張ります.

AtCoder Beginner Contest 143

はい. AtCoder Beginner Contest 143 です

今回は参加が遅れて,1時間以上経っていたので参加見送りました. 22:40 なった瞬間に解き始めました.

D までサクサク解けたので参加したかったです(:3」∠) 参加してたら多分 4完でした.


A - Curtain

問題文

長さ  A のカーテンが2枚あって  B の窓をどれくらい隠せるかという問題.
基本的には引くだけで,負数になる場合は0にする必要があります.
max 取れば終わりです.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int a,b;
  cin >> a >> b;
  cout << max(0, a - 2*b);
}



B - TAKOYAKI FESTIVAL 2019

問題文

 N が 50以下なので, \mathcal{O}(N ^ 2)(2重for文) で愚直に書いても通りそうですが,
どうしても  \mathcal{O}(N) にしたかったです.(しました)

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

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

  int sum = accumulate(d.begin(), d.end(), 0);
  for (int i=0; i<n; i++) {
    ans += (sum-=d[i])*d[i];
  }

  cout << ans << endl;
}



C - Slimes

問題文

B より簡単なのでは…?
文字が切り替わる所を数えれば良いです.

最近,c=s[i], ans++ みたいな記法を知ったので使ってみました.

#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;
  int ans = 0;
  char c = ' ';
  for (int i=0; i<n; i++) {
    if (c != s[i]) c=s[i],ans++;
  }

  cout << ans << endl;
}



D - Disjoint Set of Common Divisors

問題文

ソートしておいて,大きい方から処理します.
2つのペアの差よりも小さいものは三角形になり得ないので,そこまでに含まれる個数を数えればOKです.

a < b + c  
b < c + a  
c < a + b

式からもテキトーに求められますね…

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  for (int i=0; i<n; i++) cin>>l[i];
  sort(l.begin(),l.end());
  // for (auto i:l)cout<<i<<" ";cout<<endl;

  int ans = 0;
  for (int i=n-1; i>=0; i--) {
    for (int j=i-1; j>=0; j--) {
      auto it = upper_bound(l.begin(),l.end(), l[i]-l[j]);
      ans += max(0, (int)((l.begin()+j) - it));
    }
  }
  cout << ans << endl;
}



まとめ

出てたらパフォーマンス悪くなかったんじゃないかなぁ…
次の ABC144 頑張ります!

AtCoder Beginner Contest 142

はい. AtCoder Beginner Contest 142 です

A,B,C の3完でした. 今回もパフォーマンスもダメダメでレートも下がってしまいました…

DもEも見てたけど,両方解けずにダメでした.

f:id:zeronosu77108:20191023120101p:plain


A - Odds of Oddness

問題文

偶数が  \frac{N}{2} 個あるので,それを  N から引いて,全体の  N で割れば奇数である確率が分かりますね.

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

using namespace std;

int main() {
  int n;
  cin >> n;
  cout << (n-(n/2))/(double)n << endl;
}



B - Roller Coaster

問題文

 K 以上なら数え上げればいいので,入力を取りながら数えました.

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

using namespace std;

int main() {
  int n,k;
  int ans =0;
  cin >> n >> k;
  for (int i=0; i<n; i++) {
    int h;
    cin >> h;
    if (h >= k) ans++;
  }

  cout << ans << endl;
}



C - Go to School

問題文

とりあえず入力とって,  [0..N] のデータを  A のデータを使ってソートして答え作りました.

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) cin>>a[i];
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);

  sort(ans.begin(), ans.end(), 
    [&](int x, int y) { return a[x] < a[y]; });

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



D - Disjoint Set of Common Divisors

問題文

なんか GCD を求めて,それを素因数分解をしたりしてました(:3」∠)
GCD だと漏れるのでダメでしたね.
うーむ.思考ロックしていたのでダメでしたね.

もう少し丁寧に考えるべきでした.



E - Second Sum

問題文

 N が 12以下なので,全探索できる!と思って bitset で書いてたんだけど,ダメでした.
TLE が直せず…

解説をちらっと読んで DP と書いていたので書いてみました.
そうしたら通せました〜
DP という発想が欲しかった(:3」∠)

bitDP と言われているやつっぽいです.
bitでこういうことするのはよく考えるので DP という発想が欲しかった…

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


using namespace std;

int main() {
  long n,m;
  cin >> n >> m;
  vector<long> costs;
  vector<long> open;
  vector<long> dp(1<<n, -1);

  for (int i=0; i<m; i++) {
    long a,b;
    cin >> a >> b;

    long cnt = 0;
    for (long j=0; j<b; j++) {
      long c;
      cin >> c;
      cnt += 1<<(c-1);
    }
    costs.push_back(a);
    open.push_back(cnt);
  }

  dp[0] = 0; 
  for (long i=0; i<m; i++) {
    dp[open[i]] = costs[i];
  }

  for (long i=0; i<(1<<n); i++) {
    if(dp[i]<0) continue;

    for (long j=0; j<m; j++) {
      long index = (i | open[j]);
      if (dp[index]<0) dp[index] = dp[i] + costs[j];
      else 
        dp[index] = min(dp[index], dp[i] + costs[j]);
    }
  }

  cout << dp[(1<<n)-1] << endl;
}



まとめ

レートが30も下がりました.
辛い…