AtCoder Beginner Contest 133 - zeronosu77108’s blog

C問題沼りましたが，4完でした．

f:id:zeronosu77108:20190709101430p: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］で探索したら良いかな〜と思ったんだけど，それだと，１周（以上）している場合に判定できないなといろいろやっていたら沼りました．

#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 \\$

１行目の式から，２行目の式を引いて，

$x_1 - x_3 = 2A_1 - 2A_2$

さらにその式に３行目の式を足して，

$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;
}