SHIINBLOG

AtCoder Beginner Contest 133

はい. AtCoder Beginner Contest 133 です

C問題沼りましたが,4完でした.

f:id:zeronosu77108:20190709101430p:plain f:id:zeronosu77108:20190709101433p:plain


A - T or T

問題文

電車かタクシーかどちらが安いかという問題.
単純に  N*A  B のどちらか小さい方を出力するだけ.

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

using namespace std;

int main() {
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
}



B - Bite Eating

問題文

問題文の通りに計算しました.
整数の判定ぱっと思いついたものが,ceil()floor() して,同じなら〜と思ったんだけど,
他の人のソース見てみたら, sum == (int)sum みたいなことしていて,そっちの方が良いな〜と思いました.

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

using namespace std;

int main() {
    int n,d;
    int count=0;
    cin >> n >> d;
    vector< vector<int> > x (n+10, vector<int>(d+10));

    for(int i=0; i<n; i++) {
        for(int j=0; j<d; j++) {
            cin >> x[i][j];
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            double sum = 0.0;
            for(int k=0; k<d; k++) {
                sum += pow((abs(x[i][k] - x[j][k])), 2);
            }
            sum = sqrt(sum);
            if ( ceil(sum) == floor(sum) ) {
                count++;
            }
        }
    }

    cout << count << endl;
}



C - Remainder Minimization 2019

問題文

割った余りなので,単純に l %= 2019; r %= 2019 して,[l,r] で探索したら良いかな〜と思ったんだけど, それだと,1周(以上)している場合に判定できないな といろいろやっていたら沼りました.

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

using namespace std;

const long mod = 2019;

int main() {
    long l,r;
    cin >> l >> r;

    long ldiv = (l-1) / mod;
    long rdiv = r / mod;
 
    if ( rdiv - ldiv > 0 ) {
        puts("0");
        return 0;
    }

    l%=mod; r%=mod;

    long ans = 3000;
    for (long i=l; i<=r; i++) {
        for(long j=i+1; j<=r; j++) {
            ans = min(ans, (i*j)%mod);
        }
    }
    cout << ans << endl;

}


最初に

if ( r-l >= 2019 ) {
  puts("0");
  return 0;
}

とかやってたんだけど,そっちの方が良かった.



D - Rain Flows into Dams

問題文

「なんだこの問題…」と思っていました(Cが解けなくてD来てよく分からん…と何度か往復しました).

最初に考えたのは,連立方程式をたてて,行列で解く方法なんだけど,
なんとなくダメそうな気がして辞めました.

その連立方程式を足したり引いたりしたら,解けるのでは?と考えていたら解けました.
こんな感じの式がたてられるんだけど  x_1 / 2 + x_2 / 2 = A_1 分母の2が邪魔なので,全体に2をかけて.
 N=3 のとき,全体としては以下の感じ.


  x_1 + x_2 = 2A_1  \\
  x_2 + x_3 = 2A_2  \\
  x_3 + x_1 = 2A_3  \\

1行目の式から,2行目の式を引いて,


  x_1 - x_3 = 2A_1 - 2A_2

さらにその式に3行目の式を足して,


  2x_1 = 2A_1 - 2A_2 + 2A_3

という感じで,  x _ 1 が求められる. x _ 1 が決まったら後は,
 x _ {i+1} = 2A _ {i} - x _ i \quad(i = 1,2,\cdots,n-1) という感じ.


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

using namespace std;

const long mod = 2019;

int main() {
    long n;
    cin >> n;
    vector<long> a(n);
    vector<long> x(n);

    x[0] = 0;

    for(long i=0; i<n; i++) {
        cin >> a[i];
        if (i%2==0){
            x[0] += a[i];
        } else {
            x[0] -= a[i];
        }
    }

    cout << x[0] << " ";
    for(long i=1; i<n; i++) {
        x[i] = a[i-1]*2 - x[i-1];
        cout << x[i] << " ";
    }
    cout << endl;
}



E - Friendships

問題文

残り15分くらいで読んだけどよく分かりませんでした.
解説を聞きながら寝たんだけどなんか  nPr を使うらしい.
解けたら追記します.



まとめ

4完で,緑パフォーマンスだったので,最近の成績から言えば悪くなかったですね. C問題沼らなければ,もう少しパフォーマンス出たのかなぁ〜と思うので,もっと勉強しなくては!