17日目 Beginner 34

17日目(2019/9/2)

AtCoder Beginner Contest 034

AとBがすごく簡単で、Cで突然難しくなる感じでした。
アルゴリズム思いつかなくてCは部分点狙いに行く作戦になりました。

解けた問題

A:テスト

if文で分岐しただけ！

B:ペア

if文で分岐しただけ！（2の剰余で分岐するだけ）

解けなかった問題

C:経路

アルゴリズムが思いつかなかったのでDFSで部分点を狙いに行くことにしました。 上下左右じゃなくて右か下にしか行かないので迷路を解くアルゴリズムよりはシンプルな実装になりました。 盤の外、もしくは目的地より外側にいるならたどり着けないのでreturn
50点分の得点はこれでもらえました。どうやって実装すればよかったんだろう…

int c;

using namespace std;

void DFS(int dist_x,int dist_y,int x,int y,bool board){
    //盤の外ならreturn
    if(x<0||x>dist_x||y<0||y>dist_y)
        return;
    if(x==dist_x && y==dist_y){
        c++;
        return;
    }
    DFS(dist_x,dist_y,x,y+1,board);
    DFS(dist_x,dist_y,x+1,y,board);
}

int main(void){
    int dist_x,dist_y;
    cin >> dist_x >> dist_y;
    bool** board = new bool*[dist_y];
    for(int i=0;i<dist_x;i++){
        board[i] = new bool[dist_x];
    }
    DFS(dist_x-1,dist_y-1,0,0,board);
    cout << c%1000000007 << endl;
}

解説を見てみる

C

追記： 動的計画法で実装してみた。これで100/101点でした。
__int64_t型の存在と初めてのvector2次元配列を知る。

vector<vector<T>> v_name(高さ、vector<T>(幅));

__int64_t型は組み込みの方で、環境によらず64bitの整数型を表すみたい。

// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    __int64_t W,H;
    cin >> W >> H;
    vector<vector<__int64_t>> board(H,vector<__int64_t>(W));
    for(int i=0;i<W;i++){
        board[0][i] = 1;
    }
    for(int i=0;i<H;i++){
        board[i][0] = 1;
    }
    for(int i=1;i<H;i++){
        for(int j=1;j<W;j++){
            board[i][j] = board[i-1][j] + board[i][j-1];
            board[i][j] %= 1000000007;
        }
    }
    cout << board[H-1][W-1] << endl;
}

満点をとるためには数学的に計算する必要がある。 (H+W-2)回移動するからH-1回移動する方法を求めればいい。
ってことは で求まる。あれー考えたんだけどなぁ…（多分どこかで間違ってたのかな
(H+W-2)!/(H-1)!(W-1)!

16日目 Beginner 33

16日目(2019/9/1)

AtCoder Beginner Contest 033

ずっと家から出かけていて、PCになかなか触れられなかったので2日空いてしまいました。

解けた問題

A:暗証番号

4桁のゾロ目を調べるということだったので、1111で割ったあまりが0ならSAMEそれ以外ならDIFFERENTと出力したよ

B:町の合併

いつもだったらint型の配列とstring型の配列を動的確保して出力、みたいにしてたけど、Townクラスとして定義して、vectorで追加して、計算してみた。
書きながら別にこれ最大と合計求めればいいだからメモリ的にも実行時間的にも読み込むたびに更新するのが最適解な気がしているけど…

// C++のテンプレート
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;

class Town{
    public:
    string name;
    int people,index;
    Town(string n,int p,int i){
        people = p;
        name = n;
        index = i;
    }
    bool operator<(const Town &another) const
    {
        return people < another.people;
    }
};

int main(void){
    int N,sum=0;
    cin >> N;
    string name;
    int people;
    vector<Town> elem;
    for(int i=0;i<N;i++){
        cin >> name >> people;
        elem.push_back(Town(name,people,i));
    }
    sort(elem.begin(),elem.end());
    //sum = accumulate(elem.begin(),elem.end(),0);
    for(int i=0;i<N;i++){
        sum += elem[i].people;
    }
    if(sum < elem[N-1].people*2)
        cout << elem[N-1].name << endl;
    else
       cout << "atcoder" << endl;
}

sort関数に自作クラスTownを適用するために、演算子のオーバーロードを実装したのがめちゃくちゃ久々でどうだったっけ？ってなってました。

 bool operator<(const Town &another) const{
        return people < another.people;
    }

sort関数では、与えられた要素を比較演算子<を使って比較しているため、新しく実装したclassで、比較するときはどの値を取り出すのかを定義してあげればいいんでしたね。 ほんとは与えられた要素の合計を求めるのにaccumulate関数を使って合計求められないかなって思って、+演算子をオーバーロードしたりしてたんですがちょっと上手く行かなかった。
いろいろ調べたりしてるうちに時間がそれなりに過ぎてしまったので今日はここまで。

15日目：Beginner 32

15日目(2019/8/29)

AtCoder Beginner Contest 032

解けた問題

A:高橋君と青木君の好きな数

青木くんと高橋くんの両方の好きな最小の数
問題の範囲が20000までなので、for文で全要素走査しても、O(n)なので、 n%a == 0 && n%b == 0でnをインクリメントしつつ合致したら出力してbreak;しました。

    while (true)
    {
        if (n % a == 0 && n % b == 0)
        {
            cout << n << endl;
            break;
        }
        n++;
    }

B: 高橋君とパスワード

sから長さkの部分文字列の数を探す問題。重複したものはカウントしないようにする。
stringのクラスに部分文字列を表示する関数ってあるのかな？と思って調べてみた所ありました。
それがsubstr(index,length)関数。第一引数で何文字目かを指定し、第二引数で長さを指定するとそれに合致してくれる文字列を返してくれるらしい。
C++にハッシュってあるのかな？って思ったけど（詳しく見てないけども）C++17~テンプレートで使えるらしい？のでvectorで一度出た単語を履歴として残して、出てきた要素と比較しつつ、出てなければ追加、という処理を書きました。
あとsの長さがk以下だったら0を表示して終了にしました。

    vector<string> log;
    cin >> s >> k;
    if(s.length() < k){
        cout << 0 << endl;
        return 0;
    }
    bool in;
    for(int i=0;i<s.length()-k+1;i++){
        in = false;
        for(int hash=0;hash<log.size();hash++){
            if(log[hash] == s.substr(i,k)){
                in = true;
                break;
            }
        }
        if(!in){
            log.push_back(s.substr(i,k));
        }
    }
    cout << log.size() << endl;

イメージとして、ハッシュが使えたらhash[単語]++みたいにして要素数を調べればいいのかな、なんて思ってました。

解けなかった問題

C:列

あまり時間が取れなくてA~40分ぐらいで切り上げました。40%くらいAC,50%くらいWA,10%くらいTLEをくらいました。 まず、数列に0が含まれるのならば、どれだけ掛けてもKより大きい値にはならないのでNを出力するようにしました。
次に、数列の先頭から最後までのループをiとして、tempを1で初期化。子のループj=0を定義して、i+j<Nを満たす限りループさせ、tempにs[i+j]を掛けて、temp > Kを満たしたらbreak、そうではなければ子のループの回数をカウントすることによって要素を取れるかなって思ったけど、微妙にうまくいきませんでした。
C.cpp (WA/TLE)

int main(void){
    int N,K,temp;
    vector<int> s;
    cin >> N >> K;
    bool zero=false;
    for(int i=0;i<N;i++){
        cin >> temp;
        if(temp == 0)
            zero = true;
        s.push_back(temp);
    }
    if(zero){
        cout << N << endl;
        return 0;
    }
    int max = 0;
    int count = 0;
    for(int i=0;i<N;i++){
        count = 0;
        temp = 1;
        int j=0;
        while(i+j < N){
            temp *= s[i+j];
            if(temp > K){
                break;
            }
            count++;
            j++;
            //cout << i+j << ":" << temp << endl;
        }
        if(max < count){
            max = count;
        }
        //cout << endl;
    }
    cout << max << endl;
}

うーん、どこで躓いているんだろう。

解説を見てみる

C:

全要素が2以上であれば候補数はたかだかlog_2^Kになるため問題ないが、1が並ぶ場合O(N)になってしまうため、1を圧縮する方法を考えて実装するとTLEにならないみたい。なるほど。
でも今回作成したプログラム困ったことにWA食らってるからデバックしないとだめですね、どこかが間違ってるみたい。
尺取法という方法を使う、左右にindexをもち、左が右を超えないように右を伸ばしていく実装をすると全体でO(N)で問題を解くことができるみたいです。

参考

【C++入門】substr関数で文字列の一部を得る方法

14日目：Beginner 31

14日目(2019/8/28)

AtCoder Beginner Contest 031

解けた問題

A:ゲーム

少ない方に1足して掛け算した結果を出力！

B:運動管理

与えられた数値がLより小さければL-数値を、
Lより大きければ-1を、
それ以外なら0を出力するのをN回繰り返す感じ！

解けなかった問題

C:数列ゲーム

高橋くんが0-Nまでの範囲を選択したときに、青木くんも0-Nただし、高橋君と同値ではない状況のときのスコアを全部計算してもいいかなって思って実装したけど上手く実装できなくて、時間切れのような形になりました。 はじめは、最高得点になる場合を考えたりしたけど、N<50なら多分そのまま計算してもオーダ的になんとかなるかなぁとちょっと思って実装を変えようとしたりしてました。うーん。

解説を見てみる

C:数列ゲーム

解説見る限り合ってるっぽい…？
実装力不足でしたね。今度再挑戦します。

13日目：Beginner 30

13日目(2019/8/27)

AtCoder Beginner Contest 030

解けた問題

A:勝率計算

double型でA~Dを受け取って、
B/A > D/C
の結果によって分岐させるだけー。

B:時計盤

はじめなんか難しく考えちゃったけど、とりあえず長針から考えることにする。
長針は60分で一周するので、一回の角度は360/60 = 6度になります。
これで長針の角度は12時を0として考えると6*mで求まる。
次に短針。まず与えられる数値から大雑把な位置を考えると、
12時間で一周するので、1時間あたり360/12 = 30度になります。24時間で与えれるけど、12時間後の数は変わらないので、ざっくりした位置(長針が0の時の位置)は、30*(n%12)でもとまります。
これに加えて、長針が進むと30度の間を徐々に進んでいくので、この30度を60分割してあげたものにmを掛けたものを足してあげればいい。
-> 30*(n%12) + 0.5*m あとは差分をとってあげればいいですね。差分が180度超えてたら360から引いてあげれば角度の小さい方が取れるはず！ あんまりきれいじゃないソース

    int n,m;
    cin >> n >> m;
    double n_dir,m_dir;
    m_dir = m*6;
    n_dir = (n%12)*30 + m*0.5;
    if(m_dir > n_dir)
        if(m_dir-n_dir > 180){
            cout << 360 - m_dir + n_dir << endl;
        }else{
            cout << m_dir - n_dir << endl;
        }
    else if(m_dir < n_dir)
        if(n_dir-m_dir > 180){
            cout << 360 - n_dir + m_dir << endl;
        }else{
            cout << n_dir - m_dir << endl;
        }
    else
        cout << 0 << endl;  

C:飛行機乗り

正直実装しながら部分解だろうなって思いながら実装してたけどACできました。
aとbを往復できる回数を考える問題。a->bにはX時間 b->aにはY時間かかる。 出発時刻はaはN個 bはM個与えられる。

考え方として、往復できる回数をカウントするcount,現在時刻を保存するtime,そして出発時刻のindexをそれぞれ保存するための変数a_idx,b_idxを定義。
whileでループを回して、a_idxかb_idxが配列サイズを超えたらそれ以上の出発時刻はない（飛行機が終わってる）ので終了。
どの飛行機に乗っても固定の時間で移動できるってことは、いま現状で最速の飛行機に乗ればいいよねっていう考えだからもしかしてこれは前に学んだ貪欲法ってやつなのかな？

time = (今現在で最速の出発時間) + (移動時間) 

で更新してゆく。b->aの移動が終わったタイミングでcount変数をインクリメントして最後に出力。

    int count = 0,time=a[0],a_idx=0,b_idx=0;
    //a[0]から飛ぶとすると、bにつくのは、a[0]+X
    while(a_idx<N && b_idx<M){
        //a[0]に乗るところから始まる。
        time = a[a_idx] + X;
        while(b[b_idx] < time && b_idx<M){
            //bの時刻が時間よりも小さいならば乗れないので飛ばす。
            b_idx++;
        }
        if(b_idx == M){
            break;
        }
        //bからaに移動するにはY時間かかる。
        time = b[b_idx] + Y;
        count++;
        while(a[a_idx] < time&& a_idx<N){
            a_idx++;
        }
        if(a_idx == N){
            break;
        }
    }
    cout << count << endl;

解けなかった問題

D:へんてこ辞書

きょうはあまり時間取れなかったので35分くらいで切り上げました。
問題を見る限りiterationがめちゃくちゃ多いから、これをすると現実的な時間で終わらせられなくなる。なので、ループになる部分をうまく検出して、そのループする単語の並びから剰余を求めて答えを出すんだと思うんだけど…
実装力が足りない。

解説を見てみる

A

ACはしたけど、少数比較だと浮動小数点の誤差に左右されるかもしれないので、微小な数epsilonを準備して実装するか、両辺にA*Cを掛けて大小比較するのが安心。
なるほどですねー

C

配列から今の時刻以上の最小の値を探せば良いっていう考えは一緒で、->std::lower_boundという関数があるらしいからそれを使えばいいみたい。

D

考え方としてはあってるみたい。グラフとして捉えると、ループする閉路と、その閉路にたどり着くための木の部分で構成されている。
支点aからk mod C回動けば答えが求まる。

12日目：Beginner 29

12日目(2019/8/26)

AtCoder Beginner Contest 029

D問題が解けそうで解けなかった…悔しい。
インターン通らなかったりで結構凹んだけどその分どうにかバネにして頑張らなきゃね。

解けた問題

A:複数形

stringで受け取って、sを付与して出力するだけ。

B:カキ

stringのfind関数を使ってstring::nposとifで比較。含まれていればcountを増やして出力。

C:Brute-force Attack

パスワードに全通り試して解除を試みる手法ですね。
再帰ではじめ出力してから自分のあとにa,b,cを出力する方法を考えたけどうまく行かなかったので、再起するたびにstringを渡すようにしてiteration == N(長さ)になったら出力するようにしたよ。

void pass(int N,int iter,string BF){
    if(iter == N){
        cout << BF << endl;
    }else{
        pass(N, iter + 1, BF + "a");
        pass(N, iter + 1, BF + "b");
        pass(N, iter + 1, BF + "c");
    }
}

解けなかった問題

D:1

1~Nまで出力した時1と出力する回数を述べよっていう問題。
0-9 -> 1回
0-99 -> 20回
0-999 -> 300回
から、数を最大の999... (pow(10,digit-1)-1)で割って、countを数える方法を考えたけどこれは抜けが多かったなぁ。例えば1000台に入ったら1000-1999までは全部1増えるもんね。うーん。どうすればよかったんだろう。

解説を見てみる

D

空き桁に0を埋めて考えると全部の桁が周期的に変化してると捉えることができる！ それで桁数ごとに結果を出すのが良さそう！とのことでした。

参考

【C++】std::stringで文字列が含まれるかどうかの判定【contains】url

11日目：Beginner 28

11日目(2019/8/25)

AtCoder Beginner Contest 028

昨日問題に取り組めなかったので連続記録が途切れてしまって悲しいけど、ここでやめてしまったら習慣じゃなくなっちゃうので気を取り直して、続きからやります。
今日はBeginner Contest 028でした。50分ほど問題に取り組んで予定外にDまでACできた！やった～

解けた問題

A:テスト評価

Nを受け取ってif文で分岐しました。それだけ！

B:文字数カウント

int型の配列を要素数6,0で初期化して定義。 string型のSを受け取って、文字列の長さでループ。 S[i]が指し示すものはchar型なので、A~Fしか問題に出てこないので、Aを引いてあげることでASCIIコードの引き算ができてその文字がAから数えて何文字目か分かる。
これを利用して次のように実装しました。

    int s[6] = {0,0,0,0,0,0};
    cin >> S;
    for(int i=0;i<S.size();i++){
        s[S[i]-'A']++;
    }
    for(int i=0;i<5;i++){
        cout << s[i] << " "; 
    }
    cout << s[5] << endl;

C:数を3つ選ぶマン

良い実装方法を思いつかなかったから問題文そのまま実装しました。3重ループを書きました。1~3番目の暫定解を保存して、1~3番目の値より大きい入力が来たら更新を行う。数の大きい順に合計値を求めていき、1~3番目の要素より結果が小さくなったらそれより下の数を足しても暫定解の更新はないのでbreakしました。

    int n[5];
    int one=0,two=0,three=0;
    for(int i=0;i<5;i++)
        cin >> n[i];
    for(int i=4;i>=2;i--){
        for(int j=i-1;j>=1;j--){
            for(int k=j-1;k>=0;k--){
                if(one < n[i]+n[j]+n[k]){
                    three = two;
                    two = one;
                    one = n[i]+n[j]+n[k];
                }else if(two < n[i]+n[j]+n[k]){
                    three = two;
                    two = n[i]+n[j]+n[k];
                }else if(three < n[i]+n[j]+n[k]){
                    three = n[i]+n[j]+n[k];
                }else{
                    break;
                }
            }
        }
    }
    cout << three << endl;

もっとスマートな実装方法流石にありそう…。

D:乱数生成

3回N以下の数で乱数を生成し、中央値がKになる確率を求める問題。中央値がKになるということは、K以上の数・K・K以下の数が出るときの確率を考えればいいとまず考えました。
K以上の数が出る確率をKp、Kが出る確率をK,K以下の数が出る確率をKmとすると、Kp,K,Kmの時を求めれば良い。しかし、このままだとKpでKが出た時、KmでKが出たときの処理を考えるのが面倒だったので、Kより大きい数とKより小さい数を考えることにしました。
そうすると、条件を満たすパターンは、(K,K,K)、(Kp,K,K),(K,K,Km)、そして(Kp,K,Km)の時になります。順列を考えると、

組み合わせ	順列P
(K,K,K)	1
(Kp,K,K)	3
(K,K,Km)	3
(Kp,K,Km)	6

となるので、それぞれの確率に順列を掛けたものを足してあげると答えが出ます。

int main(void){
    int N,K;
    cin >> N >> K;
    //(K以下,K,K以上)の組み合わせが出るパターンを考えればいいはず。
    // Kが出る確率は、1/Nの確率。Kよりおおきい数が出る確率は、N-K/N,K未満が出る確率はK-1/Nである。
    double K_p = 1/double(N);
    double Km_p = (K-1)/double(N);
    double Kp_p = (N-K)/double(N);
    cout << setprecision(10) << (K_p * Kp_p * Km_p*6 + K_p * K_p * K_p + K_p * K_p * Km_p*3 + Kp_p*K_p*K_p * 3) << endl;
}

解けなかった問題

初めて全部解けた…！

解説を見てみる

C:3つ選ぶマン

A B C D E
の5つの数がある中で作成できる数の中で一番大きいものは C D E
である。 2番目に大きいものは B D E
である。 3番目に大きいのは、 A D E か B C E になる。
これに気づくとmax(A D E,B C E);を出力すればいい！
これはめっちゃ短くなりますね…。

D:乱数生成

Kが何回出力されたかで考えるらしい。
アプローチの仕方は解いた方法と一緒かな。