C - パズルのお手伝い (8 queens, 8クイーン問題)

Quiz

https://atcoder.jp/contests/arc001/tasks/arc001_3

AC Code

https://atcoder.jp/contests/arc001/submissions/6028256

解法

  • 最初の3つが条件を満たして置かれているなら、まだ空いているX座標、Y座標は共に5つ候補がある
  • それらをnext_permutationで全探索してQueenを配置
  • 配置した盤面が条件を満たすかチェック
    • 満たせばそこで終了
    • 満たすものがなければNo Answer

一般的なポイント

  • 配置の状態数が少ないので全探索すればいい

私のコードのポイント

  • 空いているX座標、Y座標をそれぞれ1回ずつしか使わないことにより、縦横の条件は最初から満たされているので、斜めのチェックだけすればいい

リモコン押下の最小回数、ワーシャルフロイドで求める

Quiz

https://atcoder.jp/contests/arc001/tasks/arc001_2

AC Code

https://atcoder.jp/contests/arc001/submissions/6027127

解法

  • ワーシャルフロイドでも解けると解説に書いてあったので、その方法をあえて使ってみる
  • -10, -5, -1, 1, 5, 10度差の状態へは、距離1で到達できるグラフと考える
  • O(N3)なのでN=100程度なら間に合う

エラトステネスのふるい ver 2

const int N_MAX = 1e7 + 10;
bool is_prime[N_MAX];

// エラトステネスのふるい
void Eratosthenes(){
    FOR(i, 0, N_MAX){
        is_prime[i] = true;
    }
    is_prime[0] = false;
    is_prime[1] = false;
    for(ll i=2; i*i<=N_MAX; i++){
        if(is_prime[i]){
            int p = i;
            int step_p = p;
            // それの倍数を消していく
            while(p < N_MAX){
                p += step_p;
                if(p<N_MAX){
                    is_prime[p] = 0;
                }
            }
        }
    }
}

二分探索と凸関数とマンハッタン距離

Quiz

ACコード

https://yukicoder.me/submissions/351288

x, yは独立に求められる

  • 以下ではxを求める方法について述べる

凸関数は三分探索が定石

  • しかしクエリ数をオーバーしてしまう
  • 探索範囲を2/3にするために、2クエリを消費する

二分探索でいける

  • 探索範囲をleft, rightとする
  • leftでの距離を測る
    • left_d = query(x=left, y=0)
  • center = (left+right)/2とする
  • マンハッタン距離なのでcenterでの距離も予測できる
    • center_d = left_d - (leftとcenterの距離)
  • centerより向こう側(right側)に答えがある場合、予測とクエリ結果が一致する
    • 一致しなければcenterより手前に答えがある

E. Product Oriented Recurrence

Quiz

https://codeforces.com/contest/1182/problem/E

Note

f:id:peroon:20190613015237j:plain

Editorial

https://codeforces.com/blog/entry/67614

天才かよ!?と思った点

  • cxを分解(分配)することでcx fxの形にできる
  • 三項の積になるが、g(x, p)を導入して三項の和にする
  • するとトリボナッチとなり、行列累乗の二分自乗法が使えてO(logN)で第N項が求まる
  • あとはcxの逆元をフェルマーの小定理から求めればいい

バブルソート

Quiz

https://yukicoder.me/problems/no/397

ACコード

https://yukicoder.me/submissions/351014

その他

  • バブルソートは関数化しておくと、今回のように交換したインデックスの組 (i, j) や、交換回数をカウントして反転数を求めるときに少し付け足すだけで済む
void bubble_sort(vector<ll> &A){
    ll N = A.size();    
    // iまで見る
    for(int i=N-1; i>=0; i--){
        FOR(j, 0, i){
            if(A[j] > A[j+1]){
                swap(A[j], A[j+1]);
            }
        }
    }
}