chigichan24に人権はあるだろうか,いやない

競技プログラミングやってます。

久しぶりにコンテストに参加して

こんばんは,chigichan24です.

高専プロコン近いですね.やばいですね.
私は,競技か自由のどちらかに出ます.本選で会って確かめてください.


さて,今日はTTPCに出ました.
久しくガチな感じで競技しておらず,CodeFestivalの予選も近いのでリハビリしないと
まずいね.というPelkira君の提案のもと,彼とチームを組みました.

結局4完0WAでした.最後の1時間くらいで撤退しました.つらい.


最終順位はさっき確認したら99位だったのでまずいですよって感じです.


A~Dのやるだけ問題のうち,A,C,Dを解きました.
Eは考察して累積和をとってほげれば良さそうで思考が止まってしまいました.
FはDPっぽいで終わりました.


ここはACするべき問題でした.つらい.


Pelkira様がGが貪欲っぽいと言って考察してくれたけど,その証明が自分にはできなくて申し訳なかったです.
Hの幾何も,よさ気なところまで考察はできてたので,なんだかモヤモヤする結果で終わってしまいました.



Cはどう考えても規則性があるのに,ゴリおそうとした結果,誤読もあり辛かったです.


唯一良かった点は0WAだったことです.
あとはDがすんなりと綺麗に書けました.

自分の書いたコード(と問題に対する感想)を一応載せときます.

A

UTPCみたいなのりで普通に軽めのDPとかからくると思ってたらif文ゲーだったので驚き.

int main(){
    string str;
    cin >> str;
    if(str[2] == 'B'){
        cout << "Bachelor" << " " << str[0] << str[1] << "\n";
    }
    else if(str[2] == 'M'){
        cout << "Master" << " " << str[0] << str[1] << "\n";
    }
    else{
        cout << "Doctor" << " " << str[0] << str[1] << "\n";
    }
    return 0;
}

C

goto文を使ってしまっていてつらみ.あとsub1,sub2の変数はやばい()
これは許してくれ.

Pii check(string str){
    if(str.size() <= 8)return Pii(-1,-1);
    string target = "ookayama";
    int mi = INF;
    int ma = -INF;
    rep(i,str.size()-7){
        bool flg = true;
        rep(j,8){
            //printf("%c %c\n",target[i],str[i+j]);
            if(str[i+j] != target[j]){
                flg = false;
            //    printf("%d\n",i);
                break;
            }
        }
        if(flg){
            int cnt = 0;
          //  cout << i << "\n";
            for(int j = i-1; j >= 0; --j){
                if(str[j] == 'o'){
                    ++cnt;
                }
                else{
                    break;
                }
            }
            if(cnt > 0){
                if(ma < cnt){
                    ma = cnt;
                    mi = i-cnt;
                }
            }
        }
    }
    if(mi == INF)return Pii(-1,-1);
    return Pii(mi,ma);
}
 
string check2(string T){
    char c = T[0];
    string ch = "@";
    reps(i,1,T.size()){
        if(c == 'o' && T[i] == 'o'){
            ch = "";
            rep(j,i-1){
                ch += T[j];
            }
            ch += "O";
            reps(j,i+1,T.size()){
                ch += T[j];
            }
            break;
        }
        else{
            c = T[i];
        }
    }
    return ch;
}
 
string check3(string T){
    char c = T[0];
    string ch = "@";
    reps(i,1,T.size()){
        if(c == 'O' && T[i] == 'O'){
            ch = "";
            rep(j,i-1){
                ch += T[j];
            }
            ch += "o";
            reps(j,i+1,T.size()){
                ch += T[j];
            }
            break;
        }
        else{
            c = T[i];
        }
    }
    if(ch == "@"){
        ch = T;
    }
    return ch;
}
 
int main(){
    string str;
    cin >> str;
 
    while(true){
        Pii idx = check(str);
     //   cout << str << "\n";
        if(idx.first == -1)break;
        string T="";
        string sub1="";
        string sub2="";
        rep(i,idx.first){
            sub1 += str[i];
        }
        reps(i,idx.first,idx.first+idx.second+8){
            T += str[i];
        }
        reps(i,idx.first+idx.second+8,str.size()){
            sub2 += str[i];
        }
    //    cout << T << "\n";
        again:;
        string f = check2(T);
    //    cout << f << "\n";
        if(f == "@"){
            str = sub1+T+sub2;
        }
        else{
            string x = check3(f);
            T = x;
            goto again;
        }
    }
 
    cout << str << "\n";
 
    return 0;
}

D

最初10^10の素数判定やばくない?みたいな感じで聞かれたけど,使われる数字が5個しか無いし,
ぶん回すだけじゃねとなったので私が実装した.特に詰まることなく解けた.
A,C,Dの中で一番簡単だった(if文ゲーは変なところでミスりそうになるのでむずい)
個人的に,綺麗に書けたと思っている()

bool isPrime(ll n){
    for(ll i = 2; i * i <= n; ++i){
        if(n % i == 0)return false;
    }
    return n != 1;
}
 
ll convert(string a){
    return atoll(a.c_str());
}
 
void solve(string str,int depth,int bit){
    if(depth == str.size()){
        if(isPrime(convert(str))){
            cout << str << "\n";
            exit(0);
        }
        return ;
    }
    string copy = str;
    char x = str[depth];
    if(isdigit(x)){
        solve(str,depth+1,bit);
    }
    else{
        string num = "13579";
        rep(j,5){
            if(1&(bit>>j))continue;
            str = copy;
            rep(i,str.size()){
                if(str[i] == x){
                    str[i] = num[j];
                }
            }
            solve(str,depth+1,bit|(1<<j));
        }
    }
    return ;
}
 
int main(){
 
    string str;
    cin >> str;
 
    solve(str,0,0);
    cout << "-1" << "\n";
    return 0;
}

まとめ

CodeFestivalまで時間ないし,やばい.
DPをつめて鍛え直さないと()
高専プロコンもやばいぞ
なんやかんやペアプロ楽しいなあ