2021年 7月 3日
まえがき
エキセントリックしんせてぃっくかどまつ
合成数は英語で
こんぽしっとなんばー
Synthetic は合成って意味の英単語
迷子の迷子の迷子迷子の子猫チャン
最近、エキセントリックっていう言葉を使っています。
意味は知らないので今調べてみます。
エキセントリック
《ダナ》普通のものとひどく変わったさま。風変わりなさま。奇矯。
ダナって何 笑
つまり普通じゃないってことダナ
健康管理
前略お母様って感じ。
何した
大学に行ったよ
具体的に
徒歩で5分
自慢したいこと
- エキセントリックカドマツをbit全探索みたいに(イメージ)解きました。
以下は、SyntheticKadomatuの解き方の大枠は分かっているものとして俺がイキるだけです。
bit全探索みたいにっていうのは、bit全探索だと、あるbit = 1011(2進数表記) が会った時、0番目は1だからuse,1番目をuse,2番めをnot use, 3番目をuseってするじゃないですか、 その要領で今回は, mask = 0213(4進数表記) があったとき、0番目を長さCの竹を作るために使う,1番目を長さAの竹をつくるために使う、..., 3番目の竹は使わない。みたいにした。っていうのが僕のいうbit全探索みたいな解き方です。(0と1ではないのでbitではない)
まあ、結局やりたいことは4nの全探索なので、ループの回数はn4です。
よって
for(int mask = 0; mask < (1 << 2 * n); mask++)
のループです。ちなみに、maskっていう変数名を使っているのは、maskって変数名をbit全探索で使っている人を見たことがあるからです。
(1 << n)が2nを表していて、4n = (22n)(2の二乗のn乗)なので,(1 << n * 2) で 4のn乗を表せます。
int main() { int n, a, b, c; cin >> n >> a >> b >> c; vector<int> l(n); rep(i, n)cin>>l[i]; ll ans = 1e9; for(int mask = 0; mask < (1 << 2 * n); mask++){ int A = 0, B = 0, C = 0; ll tmp = mask; // tmpを用意しないと、mask /= 4;の処理を行うことになってしまって、バグる int synthetic = 0; // Aに使う竹の数とBに使う竹の数とCに使う竹の数を持つ変数。 rep(i,n){ int now = tmp % 4; if(now == 0) ;// not use else synthetic++; if(now == 1) A += l[i]; if(now == 2) B += l[i]; if(now == 3) C += l[i]; tmp /= 4; } if(A != 0 && B != 0 && C != 0){ chmin(ans, (ll)(abs(a-A)+abs(b-B)+abs(c-C)+10*(synthetic-3))); } } cout << ans << endl; }
コメントを続けます。
まぁ、要するにsyntheticは4進数n桁でmaskを表したときに、何桁が1以上(0 つまり "その竹を使用しない"ではない)かを持っているだけです。
10 * synthetic - 3;
の部分は、Aに3本の竹を使っているとき、合成魔法を使った回数は2回なので、AとB,Cで3回分マイナスしましょね。ってこと。
今日解いた問題
ABC063 D- Widespread
- [二分探索]
常に体力が最も大きい魔物を爆心地として選ぶ。という操作をしたときに最短手数で全ての魔物を消せる。それはそうですが、明らかに計算量的にダメそうです。
このときの計算量をテキトウに考えてみます。
まず、1回の操作でN体のHPを更新します。このときの計算量はO(N),さらに、この後に次に体力が多いやつを知りたいので体力の配列をソートしますO(NlogN)
つまり、1回の爆発ごとにO(NlogN)かかる。
で、爆心地と選んでもA=2の時、体力が2ずつしか減らないので、h[i] = 1e9のとき、1e9/2回爆心地としなきゃ行けない。だからやべえときは1e9 * (NlogN) になってまぁ無理だろ。って感じ
じゃあ二分探索でどう解くかって考える。
とりあえず、K回の操作で倒せるならK+1回の操作でも倒せる的なのは分かるから、そういう単調性から二分探索が使える。
必要なのは、ある爆発回数K回で全てのモンスターを全滅させるかどうかを判定する方法。
K回(コード中ではmid回)の爆発で全部ぶっ殺せるかを判定する方法を述べます。 1. K回爆発させるから、少なくともB(爆心地以外のモンスターが受けるダメージ) * mid のダメージを全てのモンスターが受ける 2. 上のダメージをモンスターが受けた後の体力に対して、何回爆心地としてそのモンスターを選べば殺せるかを考えてtmpに足す(このとき、a-bの追加ダメージを爆心地として選んだ回数だけモンスターに与えられる) 3. tmp が mid回以下なら、mid回の爆発で全滅させれる。
int main() { int n, a, b; cin >> n >> a >> b; vector<int> h(n); rep(i, n)cin>>h[i]; //sort(h.rbegin(),h.rend()); ll fire = a - b; // 爆心地として選ぶことでa-bの追加ダメージ ll ng = 0, ok = 1e9+5; // 体力が各モンスタ- 1e9以下なので、1e9回の爆発をさせれば絶対全滅出来る。のでok=1e9+5(5は予備) while(ok - ng > 1){ ll mid = ok + ng; mid /= 2; ll tmp = 0; rep(i,n){ ll hp = h[i]; hp -= mid * b; if(hp <= 0) continue; tmp += (hp + fire - 1) / fire; } if(tmp <= mid){ ok = mid; } else { ng = mid; } } cout << ok << endl; }
俺は天才です。
第16回日本情報オリンピック予選(オンライン)
- [bitDP]
ABC142 E- Get Everything
- [bitDP]
あとがき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)