草体にぼ日記

だらだらと

三井住友信託銀行プログラミングコンテスト2019

三井住友信託銀行プログラミングコンテスト2019

f:id:niboshi_bisyoujo:20191202004028p:plain 5完

perf 1346

毎度のことですが、ブログ内にあるコードはメイン関数内だけをぴょぴょっと引っ張ってきたので、マクロとかあります。それは提出リンクから見てください

A問題 A-November30

問題

提出

解法

月が変わっているかを見ればいいだけ

B問題 Tax Rate

問題

提出

解法

ちょっとめんどくさい。小数を扱わないといけない問題

 
int main()
{
    cout << setprecision(10);
    double N ;
    cin >> N;
    for(int i = 0 ; i <= N ; i++){
        int money = i * 1.08;
        if( (int)(i * 1.08) == N){
            cout << i << endl;
            return 0 ;
        }
    }
 
        cout << ":("<<endl;
}

i(つまりは税抜き価格)を全探索したのですが、i * 1.08 つまり税込み価格を小数点切り捨てで 整数にする方法が分からなくて時間をかけてしまった。

よくわからんけど、 (int) (i * 1.08)で型変換してくれって祈りながら実行したら型変換してくれました。

:( コピペがうまくいかなくて時間かかった。ダメ人間。

補足

なんか、1.08じゃなくて108をかけて、そのうえで100で割ればうまくいくっぽい。

C問題 100 to 105

problem

submit

int main()
{
    cout << setprecision(10);
    ll x;
    cin >> x;
    int check = x % 100;
    int num = x / 100 ;
    if ( x < 100 ){
        cout << 0 << endl;
        return 0 ;
    }
    //下2桁さえ合えばいい
    int need = 0 ; 
    //まず5で割った余りを求める
    need += check / 5 ;
    check %= 5;
    need += check /4 ;
    check %= 4;
    need += check /3 ;
    check %= 3;
    need += check /2 ;
    check %= 2;
    need += check /1 ;
    check %= 1;

    if(num >= need){
        cout << 1 << endl;
    }
    else {
        cout << 0 << endl;
    }
}
解法

買うものの個数はMINで x / 100 ;個

x = 1360 のとき、品物は13個買える

その時に 0 , 1, 2, 3, 4, 5 の中から重複を許して13個使って60が作れるかを考える

みたいなことをやっていく。

ちなみに、品物を13個買うとき、下二桁は65(=5*13)まで作ることが出来る。

よってこの問題は、

x / 100 = y としたとき

xの下二桁がy*5以下ならxを作れる

D 問題 Lucky PIN

problem

submit

int main()
{
    cout << setprecision(10);
    cin >> n >> s;
    //n - 3 桁を消す <- 難しいのでダメ
    vector<string> search(1000);
    for(int i = 0 ; i < 1000 ; i++){
        if(i<10){
            search[i] = "00" + to_string(i);
        }
        else if( i< 100){
            search[i] = "0" + to_string(i);
        }else{
            search[i] = to_string(i);
        }
    }
    int ans = 0 ;
    rep(i,1000){
        string look = search[i];
        int index = 0 ;
        int now = 0 ;
        for(int index = 0 ; index < n ; index ++){
            if(s[index] == look[now]){
                now ++ ;
            }
            if(now == 3){
                ans ++ ;
                break;
            }
        }
    }
    cout << ans << endl;
}
解法

N桁のラッキーコードのNは最大30000桁。

例えば、N桁のラッキーコードから123を作れるかを見るときは

1桁目から順に1を探す。

次に

1を見つけた次のところから順に2を探していく

次に

2を見つけた次のところから順に3を探していく。

この操作は最大で3万回です。

ですので、000 から 999 までの1000通り全部についてこの探す操作を行えば

計算量は1000 * 30000 = 30,000,000

で三千万回なのでC++なら計算は間に合います。

よって、000から999まで全探索。それぞれ作ることが出来れば+1していく。って感じで

(計算量を減らすことを考えるなら、000 ~ 099までは,最初に出てきた0の位置を保持しておいて使いまわす。100~199までは最初に出てきた1の位置を保持しておいて使いまわす。みたいなことするのも面白いかもね)

 vector<string> search(1000);
    for(int i = 0 ; i < 1000 ; i++){
        if(i<10){
            search[i] = "00" + to_string(i);
        }
        else if( i< 100){
            search[i] = "0" + to_string(i);
        }else{
            search[i] = to_string(i);
        }
    }

で、このコードでは探すもの文字列として保持しておきました。

search[0] = "000"

search[255] = "255"

って感じです。この、0~99までは先頭に0を一つか二つ足さなきゃいけないっていう操作がめんどくさいですね。

printfで0埋め出力ならできるんですけど…

for(int i = 0 ; i < 1000 ; i ++){
    int zero  ;
    if(i / 10 < 1){
        zero = 2 ;
    }
    else if (i / 100 < 1){
        zero = 1;
    }
    else zero = 0 ;
    for(int j = 0 ; j < zero ; j ++){
        search[i] += "0" ;
    }
    search[i] += to_string(i); 
}

みたいなことでもするんですかね?いやめんどくさくない?

なんか楽な方法ないのかな?

ポイント

答えは最大で1000って気づけたから勝てたんだと思う

おまけ

PIN コードのPIN って、

Personal Identification Number 個人識別番号の略らしいですよ。

E問題 Colorful Hats 2

problem

submit

Colorful Hats 1 はあるのかと突っ込みたくなるような問題ですね。

AGC016 B - Colorful Hats

あった…

int main()
{
    cout << setprecision(10);
    cin >> n ;
    ll ans = 1 ;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
 
    map<int,int> hat;
 
    for(int i = 0 ; i < n ; i ++){
        int now = a[i];
        hat[now] ++ ;
        if(hat[now] == 0){
            break ;//なんだこのコード。絶対不要
        }
        if(a[i] == 0){
            ans *= 3-hat[now]+1;
            ans %= mod;
        }
        else {
            ans *= hat[now - 1] - hat[now] + 1;
            ans %= mod;
        }
    }
    cout << ans << endl;
}
解法

まず、0 0 0 2 みたいなことはあり得ません。

4人目の人は例えば三色、何色があったかおぼえてないから赤 白 青だとします

0 0 0 の1~3人目は絶対色違いの帽子をかぶっています。

ですので4人目の人が「自分と同じ色をかぶっている人が二人いる」と言ったらそれは嘘なので答えを0にします。

それ"も"やってくれているコードが

後ろのほうの行の

else{

    ans *= hat[now - 1 ] - hat[now] + 1 ;

    ans %= mod;

}

ココです。for ループのiが3になったとき(見るのは4人目)

now = 2 です

hat[now]には、4人目が唱えた数字が、4人目が唱えたときを含めて何回唱えられたかが入っています。

hat[now - 1] - hat[now] + 1 は、hat[1] - hat[2] + 1 = 0 - 1 + 1 = 0

これで答えが0になってくれます(この後はイクラ掛け算をしても0になる)

追記

そういえばこれ、 2 2 2 2 みたいな感じで4人の人が2 って言ったときの処理をしてないな…

(追記ここまで)

ここまでは例外処理。(嘘つきがいた場合)のお話をしました。

以下は嘘つきがいない場合について。

まず、一番最初の人は0しか唱えようがありません。

一人目は赤 白 青 の3色選びます

2人目は、1人目と同じ色を選ぶなら1を唱えます。この時は、一人目と同じ色なので1通り。

違う色を選ぶなら0を唱えます。 0を唱えたとき、1人目が選んだ色以外の二色から選べます。

例えば,k番目の人の前までに

赤が4人

白が3人

青が7人

いたとします。

このときkさんが唱える数字として考えられるものは、赤の4か、白の3か、青の7です。

そして、3を唱えたならkさんは白をかぶっている。

4なら赤を、7なら青を被っています。3を唱えたときにkさんが赤や青を被っているというのはありえない話です。

ですのでk-1番目の人までの並び方に1を掛けたものとしてansを更新します。

今ここでkさんが3を唱えたとしたとき、

k+1番目のひと(k+1さん)の前には

赤が4人 白が 4人 青が7人います。

このときk+1さんは4か7を唱えます。

4人を唱えたなら赤か白、

7を唱えたなら青を被っている。

だから4を唱えたときはansに2を掛けて更新。

ここで、上の処理をどうやって実装するか考える。

上の例でk+1さんが4を唱えたとき、すでに青を被っている人の誰かは4を唱えているはずです。

ですので、前から順に各値が何回唱えられたかをmap , hat[]に入れていきます。

k + 1 さんが4唱えたとき

hat[4] = 2 (k+1さんは2回目に4を唱えたので)

hat[3] = 3 (どの色も3人以上いる)

で、賭ける値はhat[3] - hat[4] + 1 なんです。

う~ん、うまく説明できないけど、3は3回唱えられてるけど、そのうち1個は青で使われてるから残りの二色の中から選んでね~見たいなノリ

分かれ!!!