12月11日
まえがき
やる気でねえなあ
- 解いた問題
- ABC069 C- 4- adjacent
- ARC003 B-さかさま辞書
- ABC134 D- Preparing Boxes
ABC069 C- 4- adjacent
解法
→→→↓
↓←←←
→→→↓
…
こんな感じに埋めていけば。
ARC003 B-さかさま辞書
解法
頭回らなくてなんか難しいことするのか?ってなったけど別にって感じ ひっくり返してソートしてひっくり返して出力
かんたん(当社比)
ABC134 D- Preparing Boxes
解法
後ろからいれていくことを考えればいい。 例えば、箱が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のときの扱いに注意