結果

問題	ACまでに要した時間	AC
A	02:21	1
B	06:31	1
C	11:26	1
D	21:10	1

Rating	順位
641 (+23)	2663

初4完答を達成したが，えらく簡単でD問題ですら正答率が 5145/5366 という具合でこれをカウントしていいのか．．という気持ちではある．

ratingは黒字になったのでまぁ良かった．できればE問題まで解きたかったがdpをどう適用するか悩んだ挙げ句わからずに終了．当たり前だが貪欲法では解けない．

解答

C

強いやつに優先して必殺技を使えばよいので，昇順sortして戦闘からN-K番目まで通常攻撃で殴ってその回数をカウントすればおｋ．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;
  vector<ll> H(N);
  REP(i, N) { cin >> H[i]; }
  sort(H.begin(), H.end());
  ll ans = 0;
  REP(i, N - K) { ans += H[i]; }
  cout << ans << endl;

  return 0;
}

D

一度の攻撃の後に残るモンスターのHPを並べていくと完全二分木を作っていく作業であることが分かる．あとはそのとおりに実装すればいい．

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

ll f(ll h) {
  if (h == 1) {
    return 1;
  }
  return 1 + f(h / 2);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll H;
  cin >> H;
  if (H == 1) {
    cout << 1 << endl;
    return 0;
  }

  ll depth = f(H);
  ll ans = 0;
  REPI(i, 1, depth + 1) { ans += pow(2, i - 1); }
  cout << ans << endl;

  return 0;
}

ダメだった点

E問題は 制限なしナップザック問題 という典型問題だったようだが，知らなかったので解けなかった．まだまだ知識不足．

トキ「E問題は私よ。
DP[i]=(ダメージをi与えるまでに消耗する魔力)
としてDPで解けるわ。EDPC Eみたいなイメージね。DPの基礎だからちゃんと復習してね。ところで、問題の設定はサーバルに決めてもらったんだけど、私には魔法なんか使えないわよ？」
サーバル（歌のことだなんて言えない……）
— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年1月26日