DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選（A,B)

２完＋部分点１０点でした。

A - DISCO presents ディスカバリーチャンネル プログラミングコンテスト 2016

問題概要

"DiscoPresentsDiscoveryChannelProgrammingContest2016"という文字列を表示するが、１行にw文字までしか出力できない。w文字以降は折り返して表示される。どのように表示されるか。

A: DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016 - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 | AtCoder

解法

素直にシミュレーション。ループ回すだけなのでこれは出来ると思う。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s="DiscoPresentsDiscoveryChannelProgrammingContest2016";
    int w; cin>>w;
    int i=0;
    while(i<s.size()){
        for(int j=0;j<w;j++){
            if(i<s.size()){
                cout<<s[i];
                i++;
            }
            else  break;
        }
        cout<<endl;
    }
    return 0;
}

B - ディスコ社内ツアー

問題概要

ディスコ社内には部屋がn部屋、環状に並んでいる。部屋１から番号が増える順に並んでいて、ツアーでは部屋１から部屋の面白さが単調増加するように訪れ、部屋１で終わる。最低何周するか。

B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 予選 | AtCoder

解法

普通、部屋が近い順に訪れますよね…ということで最初にmapで部屋の面白さ毎にまとめ、後は頑張って処理。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    map<int,vector<int>> mp;
    for(int i=0;i<n;i++){
        mp[a[i]].push_back(i);
    }
    int cnt=0,cur=0;
    for(auto it:mp){
        auto v=it.second;
        auto next=lower_bound(v.begin(),v.end(),cur);
        if(distance(v.begin(),next)==0){
            cur=v[v.size()-1];
        }
        else{
            cnt++;  next--;
            cur=*next;
        }
    }
    if(0<cur){
        cur=0; cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

感想

B問題はもっと良い解法がありそう…

C,Dは全く歯が立たなかったです。Cに至っては部分点狙っても１ケースWAされる始末。（最初にaの文字列を読み飛ばして処理させたことが原因）

今日は昨日寝落ちして解けなかったyukiを解いて余裕があればこちらもやりたいです。