Codeforces Round #176 (Div. 2)

結果

oxo-- (+0/-0) 322th
レートは1639->1597(-42)

凡ミスにより敗北…

A

やるだけ
(at most oneをat least oneと何故か勘違いして提出遅れた。死にたい。)

B

やるだけの筈だったんだけどなぁ…
問題文誤読した上に実装ミスってて落とされた。

初め1本の水道管にセパレータをいくつかつけて丁度n本の出力にしたい。
セパレータは1入力を2,3,…,k本の出力にわけられるもので、カスケードが可能。
このとき、必要なセパレータの数の最小値を求める。

誤読してたのは、n本入力があってそれのそれぞれにセパレータをつけていくのかと思った…。
t本の出力に分けるセパレータ=入力をt-1本増やすセパレータ　と考えればよい。

セパレータは出力本数の多いものから使っていけばよい。
出力の多い方からp本使った時の出力がn本以上になる最小のpを求めればよい。
これは感覚的にも明らかで、p-1本使った時には足りなく、
p本使うと丁度or余るのだからp本めに合計が
n本になるようなセパレタが必ず存在する。

あとはにぶたんすればいいんだけどここで何故かオーバーフローすっから変型してdouble使うか
とかいう謎なことを考えた上に式が間違ってて落とされたのであった。

あとで通したコードは以下

int main(){
    std::ios_base::sync_with_stdio(false);

    ll n,k;
    cin >> n >> k;
    ll ub=k+1,lb=-1, mid;

    while(ub - lb > 1){
        mid = (ub + lb) / 2;
        if(1+(2*k-1-mid)*mid/2 >= n){
            ub = mid;
        }else{
            lb = mid;
        }
    }

    if(ub == k+1){
        cout << -1 << endl;
    }else{
        cout << ub << endl;
    }
}

C

個人的によく頑張った。
問題文が初め理解し難いのでn=5の時を丁寧に書いてみる。
巡回っぽい感じかなぁと思ってn=4,5,6あたりのをひたすら書いていくと

ind   | 1   2   ...         n-1 n
p(ind)| n-1 1   ...         n   2

という4つで1セットができているのが解る。
あとはn=2のときとn=3のときにできないことを確かめて、n=8のときに4つ*2セットで
順列が生成できることを確かめてからコードを書く

• >AC.

int main(){
    int n;
    cin >> n;

    if(n % 4 == 2 || n % 4 == 3){
        cout << -1 << endl;
    }else{
        int ans[n];
        int times = n / 4;
        
        for(int i=0;i<times;i++){
            ans[2*i] = n - 1 - 2 * i;
            ans[n-2-2*i] = n - 2 * i;
            ans[n-1-2*i] = 2*i+2;
            ans[2*i+1] = 2*i+1;
        }
        if(n%4 == 1){
            ans[n/2] = n/2+1;
        }
        for(int i=0;i<n;i++){
            if(i){
                cout << " " << ans[i];
            }else{
                cout << ans[i];
            }
        }
        cout << endl;
    }
}

感想

へこまずにがんばる…。