2019-07-09

AtCoder Beginner Contest 133

AtCoder 競プロ

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

E - Friendships

問題文

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

まとめ

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

2019-06-23

AtCoder Beginner Contest 131

AtCoder 競プロ

はい． AtCoder Beginner Contest 131 です

久しぶりに参加したので，ちゃんと解けるか不安だったけど， A,B,C,D は解けました．
E も解けそうだったけど，時間が足りませんでした（ C に時間をかけ過ぎた）．

f:id:zeronosu77108:20190623155652p:plain

A - Security

問題文

char で取って1つ前を保存しておきました．

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>


using namespace std;

int main(void) {
    char c1,c2;
    c2 = '-';
    bool f = false;
    for(int i=0; i<4; i++) {
        cin >> c1;

        if ( f || c1 == c2 ) {
            f = true;
        }
        c2 = c1;
    }

    cout << (f? "Bad" : "Good") << endl;
}

B - Bite Eating

問題文

愚直に計算しつつ，絶対値の小さいものを保存しておきました．

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>


using namespace std;

int main(void) {
    int n,l;
    int eat = 999;
    int sum = 0;
    cin >> n >> l;

    for(int i=1; i<=n; i++) {
        sum += l + i - 1;
        if( abs(eat) > abs(l+i-1) ) {
            eat = l+i-1;
        }
    }

    cout << sum - eat << endl;
}

C - Anti-Division

問題文

a未満の c,dで割りきれる数と b以下の割り切れる数を求めて引き算したら解けました．
最初 (b-a) で range を取ってごにょごにょしていたんですが，それではダメでした
（本当にこの方法で良いのか疑問を持ちながら書いていたので，まぁ当たり前と言えば当たり前でした）

この手の問題は，問題集とかにも載っているらしく，時間かかってしまったのは，ちょっと残念ですね．

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cmath>


using namespace std;

long long gcd(long long a,long long b){
    if (a%b==0){
        return(b);
    }
    else{
        return(gcd(b,a%b));
    }
}

int main(void) {
    long long a,b,c,d;
    cin >> a >> b >>  c >> d;
    long long ans1,ans2;
    long long GCD = gcd(c,d);
    a--;
    ans1 = a/c + a/d - a/((c*d)/GCD);
    ans2 = b/c + b/d - b/((c*d)/GCD);

    cout << (b-a) - (ans2 - ans1) << endl;
}

D - Megalomania

問題文

期限の短い順に並べて，処理していけば時間内に仕事が終わるかどうか分かります．
C より簡単なのでは…？

なんか compare の関数内側に書く方が良さそうなんだけど，書き方を覚えていなかったので外側に書くことになってしまった．
pair をほとんど調べずに進められたので，成長を感じました．

最初，期限の長いものから引き算していったので，変数名とかがそこに引きずられて残念な感じになっています…

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cmath>
#include <utility>


using namespace std;


bool compare(pair<long long, long long> i1, pair<long long, long long> i2) 
{ 
    if ( i1.second == i2.second) return i1.first > i2.first;
    return (i1.second < i2.second); 
} 

int main(void) {
    long long n;
    cin >> n;
    vector< pair<long long, long long> > ab;
    for (long long i=0; i<n; i++) {
        long long tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        ab.push_back( make_pair(tmp1,tmp2));
    }

    sort(ab.begin(), ab.end(), compare);
    long long max = 0;

    for (long long i=0; i<n; i++) {
        if ( max+ab[i].first > ab[i].second ) {
            cout << "No" << endl;
            return 0;
        }
        max += ab[i].first;
    }

    cout << "Yes" << endl;



}

E - Friendships

問題文

これもそんなに難しく無さそう…（希望的観測）
もう少し時間があったら解けた気もしますが，とりあえず解けませんでした．

勉強して書けたら追記します．

まとめ

今回は A,B,C,D 解けて，E もある程度解けそうだったので悪くないかもと思ったのですが，順位的には微妙でした．
次回はもっとレートを上げられるように頑張ります！

2019-05-27

AtCoder Beginner Contest 128

競プロプログラム AtCoder

はい． AtCoder Beginner Contest 128 です

f:id:zeronosu77108:20190527000245p:plain

今回は酷い． AC になったのは， A と B だけでした(:3」∠)
とりあえず，この2つをまとめておきます．

C以降は勉強して解けたら追記していきます．

A - Apple Pie

問題文
リンゴが 3 つの欠片になるのだから，足して割るだけ．

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
    int a,p;
    cin >> a >> p;
    cout << (a*3+p)/2 << endl;
}

B - Guidebook

問題文
index 置いてソートするだけ．

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

using namespace std;


int main(void) {
    long n;
    vector< pair<string, int> > ass;
    cin >> n;

    for (long i=0; i<n; i++) {
        pair<string, int> tmp;
        cin >> tmp.first >> tmp.second;
        ass.push_back(tmp);
    }

    vector<int> index(ass.size());
    iota(index.begin(), index.end(), 0);


    sort(index.begin(),
         index.end(),
             [&](long x, long y){if( ass[x].first != ass[y].first) return ass[x].first<ass[y].first; return ass[x].second>ass[y].second;}
    );

    sort(ass.begin(), ass.end());

    for(auto i: index){
        cout << i+1 << endl;
    }
}

C問題以上は，明日以降にちゃんと考えて解いたら追記します．

2019-05-25

AtCoder Beginner Contest 127

AtCoder プログラム競プロ

はい． AtCoder Beginner Contest 127 です

今回は縛りプレイじゃないです（だからといって順位は高くないです）．

f:id:zeronosu77108:20190525231129p:plain

f:id:zeronosu77108:20190525231148p:plain

A - Ferris Wheel

問題文
はい．問題文の通りに実装しました．

#include <iostream>

using namespace std;

int main() {
    int a,b;
    cin >> a >> b;
    if ( a <= 5 ) {
        b = 0;
    } else if ( a <= 12 ) {
        b /= 2;
    }

    cout << b << endl;
}

B - Algae

問題文
for文ぶん回すだけ…？

#include <iostream>

using namespace std;

int main() {
    long long r,d,x;
    cin >> r >> d >> x;
    
    for(long long i=0; i<10; i++) {
        cout << (x=r*x-d) << endl;
    }
}

C - Prison

問題文
Lの最大値と Rの最小値を求めれば良いだろ〜って感じで書いた．
これ，LとRすれ違うこともあるよなぁとか思いつつもそのまま出してしまって WA
即 if文を書き足して AC

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long n,m;
    cin >> n >> m;
    long long nmax=-1;
    long long nmin=9999999999;
    for(long long i=0; i<m; i++) {
        long long l,r;
        cin >> l >> r;
        nmax = max(nmax, l);
        nmin = min(nmin, r);
    }

    long long ans = abs(nmin - nmax) + 1;
    if ( nmin < nmax ) {
        ans = 0;
    }
    cout << ans << endl;
}

D - Integer Cards

問題文
ソートして小さい方から書き換えて行けば良いのでは？という感じ．
入れ子な vector のソート慣れてなくて時間がかかった．

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

using namespace std;

bool compare(vector<long long> i1, vector<long long> i2) 
{ 
    return (i1[1] > i2[1]); 
} 

int main() {
    long long n,m;
    vector<long long> a;
    vector<vector<long long> > bc;
    cin >> n >> m;

    for(long long i=0; i<n; i++) {
        long long tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    for(long long i=0; i<m; i++) {
        long long tmp;
        vector<long long> vtmp;
        cin >> tmp;
        vtmp.push_back(tmp);
        cin >> tmp;
        vtmp.push_back(tmp);
        bc.push_back(vtmp);
    }
    
    sort(a.begin(), a.end());
    sort(bc.begin(), bc.end(), compare);

    long long i,j;
    i = j = 0;

    while( a[i] < bc[j][1] ) {
        if( bc[j][0] > 0 ) {
            a[i] = bc[j][1];
            i++;
            if( i > n-1 ) {
                break;
            }
            bc[j][0]--;
        } else {
            j++;
            if( j > m-1 ) {
                break;
            }
        }
    }
    long long ans = 0;
    for(long long i=0; i<n; i++) ans += a[i];
    cout << ans << endl;
}

E - Cell Distance

問題文
最初 4C2 とか組み合わせ使うのかな〜って考えてたけど，思いつかなくて一旦 F問題へ．
戻ってきて雑に総当たり書いてみたけど，よく分からず…

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

using namespace std;

long long mod = 1000000007;

long long calc(long, long, long, long, long, long );

int main() {
    long n,m,k;
    cin >> n >> m >> k;
    long sum = 0;

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++ ) {
            sum += calc(n,m,i,j,k,1);
        }
    }
    cout << sum << endl;
}

long long calc(long n, long m, long i, long j, long k, long l) {
    if ( l == k ) {
        return 0;
    }

    long sum = 0;
    for (int ii=i; ii<i; ii++) {
        for (int jj=j+1; jj<j; jj++) {
            sum = (sum + calc(n,m,ii,jj,k,l+1) + abs(ii-jj)) % mod;
            //cout << "sum " << sum << " ";
        }
    }
    //cout << endl;
    //cout << "(" << i << "," << j << ") " << "l : " << l << endl;
    //cout << "sum " << sum << endl;
    //cout << endl;
    return sum;
}

F - Absolute Minima

問題文
何だこの問題は…
a の最小値と a を vector に溜めておいて， 2 が来たら全部絶対値取って足せば良いかな〜とか思ってた．
ダメみたいです．

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

using namespace std;


int main() {
    vector<long long> a;
    long amin = 9999999999;
    long n;
    long b = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        long q;
        cin >> q;
        // cout << "q : " << q << endl;
        if( q == 2 ) {
            long sum = 0;
            for (auto it : a ) {
                sum += abs(amin - it);
            }
            cout << amin << " " << sum + b << endl;
        } else {
            long ta,tb;
            cin >> ta >> tb;
            // cout << "a b : " << ta << " " << tb << endl;
            a.push_back(ta);
            amin = min(amin, ta);
            b += tb;
        }
    }
}

E問題と F問題は解けなかったので，次回までに（と言っても明日なんだけど…）勉強したい(:3」∠)

2019-05-19

AtCoder Beginner Contest 126

AtCoder 競プロ

はい． AtCoder Beginner Contest 126 です

22:00から始めるという縛りプレイでした．

タイムはそんなに悪くないかな… f:id:zeronosu77108:20190519232304p:plain

A - Changing a Character

問題文
k番目の文字を小文字にするやつ．
char型に1文字ずつ読み込んでいって，k番目なら tolower するだけでできた．

#include <iostream>

using namespace std;

int main(void) {
    int n,k;
    char c;
    cin >> n >> k;

    for (int i=1; i<=n; i++) {
        cin >> c;
        if ( k == i ) {
            c = tolower(c);
        }
        cout << c;
    }
    cout << endl;
}

B - YYMM or MMYY

問題文
日付の表記判断．
2桁ずつに別けて， 1 ≦ x ≦ 12 か判断するだけ．

#include <iostream>

using namespace std;


int main(void) {
    string str;
    int i,j;
    cin >> str;
    bool i_f, j_f;
    i_f = j_f = false;

    i = stoi( str.substr(0,2) );
    j = stoi( str.substr(2,2) );

    if ( 0<i && i<=12 ) {
        i_f = true;
    }
    if ( 0<j && j<=12 ) {
        j_f = true;
    }

    if (i_f && j_f) {
        cout << "AMBIGUOUS" << endl;
    } else if ( i_f ) {
        cout << "MMYY" << endl;
    } else if ( j_f ) {
        cout << "YYMM" << endl;
    } else {
        cout << "NA" << endl;
    }
}

C - Dice and Coin

問題文
確率の計算していくだけ．テキトーでいけるかなと思って書いた．

#include <iostream>

using namespace std;

int main(void) {
    long long n,k;
    double ans = 0.0;
    cin >> n >> k;

    for (long long i=1; i<=n; i++) {
        double sum = i;
        double tmp = n;

        while( sum <= k-1 ) {
            sum *= 2.0;
            tmp *= 2.0;
        }
        ans += (1.0 / tmp);
    }

    printf("%.16f\n", ans);
}

すると，サンプルの2と何故か微妙に違う…
時間も無かったので，とりあえずそのまま提出しました．

解説を見るとほぼ同じプログラム…
なんと確率の分母を全部取って割り算ではなく，逐次で /=2 していた．

うーん，そんなに差が出るんか…？

#include <iostream>

using namespace std;

int main(void) {
    long long n,k;
    double ans = 0.0;
    cin >> n >> k;

    for (long long i=1; i<=n; i++) {
        double sum = i;
        double tmp = 1.0 / n;

        while( sum <= k-1 ) {
            sum *= 2.0;
            tmp /= 2.0;
        }
        ans += tmp;
    }

    // cout << ans << endl;
    printf("%.16f\n", ans);
}

2019-05-20 追記
double → long double にしたら誤差が 1*10^{-9} 以下になりました．

D - Even Relation

問題文
はい．時間が無くて超雑に書きました．
通るわけ無いですよね．

#include <iostream>

using namespace std;

int main(void) {
    int n;
    int ans[100010];
    bool f[100010];
    for (int i=0; i<10000; i++) {
        f[i] = false; ans[i] = 1;
    }

    int u[100010],v[100010],w[100010];
    
    cin >> n;
    
    for (int i=0; i<n-1; i++) {
        cin >> u[i] >> v[i] >> w[i];
        if (w[i]%2 == 0) {
            f[u[i]-1] = true;
            f[v[i]-1] = true;
        } else {
            if ( ans[u[i]-1] != -1 && ans[v[i]-1] != -1 ) {
                if ( ! f[u[i]-1] ) {
                    ans[u[i]-1] = 0;
                } else if ( ! f[v[i]-1] ) {
                    ans[v[i]-1] = 0;
                } 
            }
        }

    }

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

とりあえず2点間が偶数なら良いじゃん！っていうアレで書いたんだけど，
雑過ぎました．
しかも，未定義を -1 とした名残の if文が残っている…

圧倒的時間不足により問題文把握，プログラムが雑になってしまった感があります…
次はちゃんと時間作るぞ〜

あ， E問題と F問題は解けたら上げます．

2019-03-02

エンジニアを説明上手にする本を読んだ

本

エンジニアを説明上手にする本を読んだ．

わかりやすく説明するために，
分類してラベルをつけて説明する．
使う用語や関心についてターゲットを分析することなどが説明されていた．

プレゼンテーションについても触れており，
ジェスチャーは3秒キープすることや間についての説明などもある．

情報を構造化するパターンについても説明があった．

言っていることはとても分かる．凄く説明が上手くいきそうだと思った．
悪くない．悪くないんだけど…
日本語が頭に入ってこない…

~~3度くらい読むの挫折しそうになった．~~

2018-12-22

CADDi 2018 for Beginners

競プロ AtCoder プログラム

CADDi 2018 for Beginners に参加しました．

~~またもや気付いたら始まっていた…~~
まぁ，言い訳は置いといて，

結果的には全部解けました．
A → B → D → C の順で解いた．

A - 12/22

問題文はこちら

4桁の整数が与えられて， '2' が何個現れるか求めるもの．

C++ で解いたので， string で受けて，単純に'2'の数を数えた．

#include <iostream>
#include <string>

using namespace std;

int count_char(string s,char x) {
    int count;
    for (auto c : s) {
        if ( c == x ) {
            count++;
        }
    }
    return count;
}

int main(){
    string s;
    cin >> s;
    cout << count_char(s,'2') << endl;
}

B - AtCoder Alloy

問題文
hight と width が与えられて，それ以上の金属板はいくつあるかみたいな問題．

これもすぐに書き終わったかな．

#include <iostream>

using namespace std;

int main(void) {
    int n,h,w;
    int count;

    cin >> n;  cin >> h;  cin >> w;
    for(int i=0; i<n; i++) {
        int a,b;
        cin >> a; cin >> b;
        if( h <= a && w <= b ) {
            count++;
        }
    }
    cout << count << endl;
}

D - Harlequin

一応解いた順番にD問題から．
問題文

交互にリンゴを食べていって，最後のリンゴを食べるのはどちらかっていう問題．

問題を眺めながら紙に書いてたら何か神が降りてきて，

2 で割った余りが全部 0 なら second の人が勝つのでは？
と思って実装してみたら合ってた．

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int n;
    string winner = "second";
    cin >> n;
    

    for(int i=0; i<n; i++) {
        int a;
        cin >> a;
        if ( a % 2 != 0 ) {
            winner = "first";
        }
    }
    cout << winner << endl;
}

よく見たら， winner = "first" としている部分で break した方が良いのでは…？

C - Product and GCD

問題文

D 問題解く前に1度見て，ぱっと見思いつかなかったので，一旦放置した問題．

なんとなく素因数分解使えそうだな〜と考えていて，

n個に分解するんだから，素因数分解したときの素数がn個以上あれば，それが最大公約数に含まれるじゃん！
と気付いた．

それで，最初書いたのだけれど，
2*n個以上ある場合を考えていなかったので，
問題によっては，WA（間違い）になってしまった．

全然間違っている理由が分からなくて，
いろいろ変えて提出したので間違いだらけになってしまった．
（int を long long にしてみたりとか）

#include <iostream>
#include <unordered_map> 

using namespace std;

std::unordered_map<long long,long long> c;

void decompositPrime(long long n)
{
    long long a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            n /= a;
            c[a] += 1;
        } else {
            a++;
        }
    }
    c[n]++;
}

int main(void) {
    long long n;
    long long p;
    long long ans=1;
    cin >> n;  cin >> p;
    decompositPrime(p);
    
    for (auto itr = c.begin(); itr != c.end(); itr++) {
        // if ( itr->second >= n ) {
        while ( itr->second >= n ) {
            itr->second -= n;
            ans *= itr->first;
        }
    }
    cout << ans << endl;
}

今回は， Beginners だけど， 267位だったので，
40分ほど遅れてスタートした割りには良い方なんじゃないだろうか．