草体にぼ日記

だらだらと

12月11日 精進ロク

12月11日
 まえがき

やる気でねえなあ

  • 解いた問題
    • ABC069 C- 4- adjacent
    • ARC003 B-さかさま辞書
    • ABC134 D- Preparing Boxes

ABC069 C- 4- adjacent

problem

解法

→→→↓

↓←←←

→→→↓

こんな感じに埋めていけば。

ARC003 B-さかさま辞書

problem

解法

頭回らなくてなんか難しいことするのか?ってなったけど別にって感じ ひっくり返してソートしてひっくり返して出力

かんたん(当社比)

ABC134 D- Preparing Boxes

problem

解法

後ろからいれていくことを考えればいい。 例えば、箱が9個あるとして、1〜8の箱に球を入れたとしても、9の倍数が書かれた箱に入っているボールの個数の和には影響しない。

よって、N個の箱があったとき、Nが書かれた箱から順に球を入れていく事を考える。

kが書かれた箱に球を入れたときは,(kの約数)の倍数が書かれた箱に入ってるボールの個数の和に影響する。 例えば、9が書かれた箱に入れたら、9の約数の1,2,3(と9)の倍数が書かれた箱に入っているボールの個数の和に影響。

以下のようなコードを実装しました

kが書かれた箱に球を入れたとき、 kの約数が書かれた箱に球を1個追加したものとする。

(L < k) Lが書かれた箱に入っている球の数 % 2 != a[L - 1]のとき、 Lの約数が書かれた箱に球を1個追加したものとする( さっきまでのkがLになったって感じ) これを、Nから1までやっていく。

コード上でi番目の箱には、i+1が書かれているので添字に注意 約数列挙は、各Kについて、計算量(√K)で可能。

それでは、天才が書いたコードを見ていこう

int main()
{
    cin >> n ;
    int a[n];
    rep(i,n){
        cin >> a[i];
    }
    int ans = 0;
    vector<int> num(0);
    for(int i = n -1 ; i >= 0 ; i -- ){
        //いれたとき、そいつの約数のカウンタに+1する
        if(a[i] % 2 == 1) {
            ans ++ ;
            int now = i + 1;
            num.push_back(now);
            //now の約数となるものの値をkとして、a[k-1]を++
            for(int j = 1 ;j * j <= now ; j ++){
                if(now % j == 0){
                    if(a[j-1] == 0) a[j-1] = 1;
                    else a[j-1] = 0 ;
                    if(j*j!=now){//約数が√nowのときに注意
                        int yakusuu = j;
                        yakusuu = now / j; 
                        if(a[yakusuu-1] == 0) a[yakusuu-1] = 1;
                        else a[yakusuu-1] = 0 ;
                    }
                }
            } 
        }
    }
    cout << ans << endl;
    rSORT(num);
    for(int i = 0 ; i < ans ; i++){
        cout << num[i];
        if(i == ans - 1) cout << endl;
        else cout << " " ;
    }
}

箱に入れた球の数、本来なら2,3ってなってくんだけど、どうせ奇数か偶数かしかみないから01だけで 管理しました

約数が√kのときの扱いに注意