おはようございます。しほみんです。
昨日に引き続き競技プログラミングの話しします。今日はこの前あったABC153について話します。このセットは冒険ものをシミュレーションした感じで結構面白かったです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは750目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約30回参加、8か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
とはいえ、今回は30分でABCDの4完でした。しかし、順位が3200位程度だったので、パフォーマンスも芳しくなく、レートは1下がった感じです。
今回、E問題も結構典型問題だったみたいなので多くの人が答えられていました。最近、ABCも最近、問題難度がセットで違うので毎回セットごとで得点したいものをきちんととっていきます....
今日はE問題まで復習して終わりにしようと思います。F問題もできそうですが、ちょっと時間がうまく取れませんでした。
ではここから復習します。
A問題
体力HのモンスターにAダメージを何回食らわせたら倒せるかです。
H/Aで割ったとき、割り切れるならH/A回です。それ以外はH/A+1回です。
構成は...
if(H%A == 0)
H/A;
else
H/A + 1;
B問題
体力Hのモンスターを倒せるかどうか判定です。
N種類の攻撃をもっていて、それぞれのダメージはAiです。
おなじ必殺技を使わないで倒せるか判定してください。
これは実際すべての攻撃をしたとき、倒せるかどうかを見比べればよいです。
つまりそうダメージ数がsumのとき、sum >= hなら倒せるし、それ以外は倒せないです。
構成は...
for(int i = 0;i < n;i++)
sum += Ai;
if(sum >= h)
Yes;
else
No;
C問題
N体のモンスターを倒す回数を求めます。それぞれ体力はHiです。
必殺技をK回まで使えて、一撃で倒せます。それ以外は通常攻撃で1与えます。
このとき、必殺技以外で最小で何回攻撃したら倒せるか求めます
最小なので、体力が多いK体を必殺技で倒して残りを地道に倒せばいいです。
よって、ソートして、小さい順からN-KまでのモンスターのHPを足します。
構成は
hはモンスターの体力の配列です。
Array.sort(h);
sum = 0;
for(int i = 0;i < N- K;i++)
sum += h[i];
sum;
D問題
体力Hのモンスターがいます。一度攻撃すると2体に分裂してH/2,H/2になります。
体力1のやつは消滅します。
このとき何回攻撃したら倒せますか？
ちょっと図で書くと考えやすいです。
H = 1-8で考えると分裂してなくなるフローとその過程は以下のようになります。
注目すべきはH=4-7でここは攻撃回数が同じです。さらにここは2で割る回数が同じということもわかります。
つまり、2で割る回数で依存して決まることが分かります。
あとは2で割る回数が1回増えるとその前の状態が再現できるのが分かります。
これはつまり漸化式です。anをn回2で割れる数とします。
すると、an+1 = 2*an + 1 です。
まとめると
1. Hの2で割れる回数をだす。
2. あとはその回数に応じて漸化式を適応して足す。
構成は...
count = 0;
sum = 1;
while( h != 1)
h /=2;
count++;
for(int i = 0;i <count;i++)
sum = 2*sum+1;
E問題
体力Hのモンスターがいます。
攻撃Aiで、コストBiの攻撃がN個あります。
これらは何度も使えます。この時モンスターを倒すのに最小のコストを求めよ
自分が全く理解してなかったのが悪いのですがナップサック法で解けます。
といっても動的計画法の一種なのですが...自分も勉強します。
動的計画法はとにかく求めたいものとどう推移するかを設定するのが大切です。
今回は最小コストで推移するといいみたいです。
つまり、体力iは最小コストでいくつで倒せるかを見ます。
これをi =1からやって考えていけばよいのです。
つまり、この攻撃セットで、どう魔法コストを使わないでダメージを与えられるかを順次検討するみたいな感じです。
ちなみに、自分は最も効率的な攻撃を続けて攻撃して最後に最も楽に倒す方法を考えるでできると思ったのですが、これはナップザック法的には効率的に求められないみたいです。
確かに、効率的に攻撃する回数を限界までやって余りを考えるのとその回数を限界引く1にして余りで攻撃するのでは効率のコストが違う気がします。
これは素直に動的計画をつかいましょうって気分です。ここら辺数学的にもきちんと知れたらいいのですが....
話は戻りますが、あとは下の状態遷移図をかけるかどうかです。
これさえわかればよいです。
ちなみに今回はHが10の4乗、Nが10の3乗なのでHNのオーダーの実装なら間に合います。ここからもこういう発想で解けると気が付きたいですね...
構成は...
a,bに攻撃とコスト
dpは動的計画のやつ
for(ini i = 0;i < n;i++)
dp[i] = 100000000;
for(int i = 0;i < h;i++)
for(int j = 0;j < n;j++)
if(i > a[j])
dp[i] = Min(dp[i], dp[i - a[ij] + b[j]);
else
dp[i] = Min(dp[i],b[j]);
dp[h]を出力する。
最後に...
典型問題はレベルにかかわらずやはり解けないと緑には難しいですね。とは言え毎週参加すれば典型問題をきちんと身に着けていけるので次はできるようにって気持ちで頑張っていきます。プログラミングの勉強ぐらい大学でやっておけばよかったなと今では思いますね....まあ前向きに行きましょうか。ではでは。
