Educational Codeforces Round 84 (Rated for Div. 2)

codeforces.com

A. Sum of Odd Integers

問題文

ある整数nとkが与えられる
k個の異なる奇数の総和がnに出来るかどうかを判定せよ

解法

いつもの偶奇見るやつね、と提出したらWA
異なる奇数でないといけないのが罠
nとkの偶奇が異なっていたらまず作れない
それ以外は、小さい奇数から使っていって、最後にnになるように調整できる
ただし、小さい方からk個使ってnを超える時があるので、そのときはNO

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        ll n, k;
        cin >> n >> k;
        if(n%2 == k%2){
            ll sum = k * k;
            if(n >= sum) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else cout << "NO" << endl;
    }
}

B. Princesses and Princes

問題文

n人のプリンセスとプリンスがいる
i番目のプリンセスは結婚したい人のプリンスの番号が書かれたリストを持っている
i番目のプリンセスは「残っているプリンス」の中でもっとも番号の若いものと結婚する
順番にプリンセスに対しプリンスを割り当てていった時に、余った人が出ないように割り当てられる時"OPTIMAL"を
割り当てられない場合は"IMPROVE"を出力せよ
ただし、"IMPROVE"の時1組だけ追加でプリンセスに対しプリンスを割り当てることが出来るのでその組を出力せよ

解法

読解がしんどい
読めると言われたとおりに割り当てていき、余っているプリンセスとプリンスがいれば
適当に1組出力すればいい

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int Q;
    cin >> Q;
    while(Q--){
        int n;
        cin >> n;
        vector<int> male(n, 1);
        vector<int> restFemale;
        REP(i,n){
            int k;
            cin >> k;
            bool ok = false;
            REP(i,k){
                int c;
                cin >> c;
                c--;
                if(ok) continue;
                if(male[c]){
                    male[c] = 0;
                    ok = true;
                }
            }
            if(!ok) restFemale.push_back(i+1);
        }
        vector<int> restMale;
        REP(i,n) if(male[i]) restMale.push_back(i+1);
        int mi = min((int)restMale.size(), (int)restFemale.size());
        if(mi == 0){
            cout << "OPTIMAL" << endl;
        }
        else{
            cout << "IMPROVE" << endl;
            cout << restFemale[0] << " " << restMale[0] << endl;
        }
    }
}

C. Game with Chips

問題文

のグリッド上にk個のチップがある
i番目のチップは最初、座標に存在し
最低一度は座標を通る必要がある
一回の操作で上下左右の4方向のどれかを選び、選んだ方向に対し、全てのチップを今いる位置からその方向へ移動させる
操作回数を以下で全てのチップに対し条件を満たせるかを判定せよ
ただし、各チップは同一座標に同時に存在することが出来る

解法

本番解けなかったけどこれはギャグ…
制約がなので全部のマスを2回通ることが出来る
そのため、最初に4隅のどこかにチップを集合させ、その後全部のマスを通るように移動させれば達成可能

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W, k;
    cin >> H >> W >> k;
    REP(i,2*k){
        int x, y;
        cin >> x >> y;
    }
    string ans = "";
    ans += string(H-1, 'U');
    ans += string(W-1, 'L');
    REP(i,H){
        if(i % 2 == 0) ans += string(W-1, 'R');
        else ans += string(W-1, 'L');
        if(i != H - 1) ans += 'D';
    }
    cout << ans.size() << endl;
    cout << ans << endl;
}

D. Infinite Path

問題読んでないですごめんなさい
約数を使ってこねこねするっぽい？ちゃんと解いておきます

E. Count The Blocks

問題文

整数nが与えられる
からまでの全ての数字を0埋めしたもので全て書いていく
ex) 000, 001, 002, ... (n = 3)
同じ数字が連続で並んでいるものをブロックし、その連続して並んだ数字の個数をブロックの長さとする
この時、1からnまでの長さのブロックがそれぞれ何個存在するかを数えよ
ただしmod 998244353 を取ったものを出力

解法

かなり綺麗に規則性が出そうだなと思ったのでとりあえず小さい数字で手元で実験プログラムを書いてみた
その結果10, 180, 2610, ...,と続いていくことがわかるので、エスパーして求めてあげると通ります（？）
正攻法だとDPとか場合分けして数えてあげれば良い

提出コード

const int mod = 998244353;
using mint = Fp<mod>;
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<mint> res(n);
    mint cum = 10;
    res[0] = 10;
    for(int i=2;i<=n;i++){
        mint tmp =  mint(i) * modpow(mint(10), i);
        tmp -= mint(i - 1) * modpow(mint(10), i-1);
        tmp -= cum;
        cum += tmp;
        res[i-1] = tmp;
    }
    reverse(res.begin(), res.end());
    REP(i,n) cout << res[i] << " ";
    cout << endl;
}

おわりに

こどふぉのギャグをギャグと認識できない…
div2AとかBでもよく死ぬのでなんとかしないとなあ（なんとかなるんですか）