日記0313

夜になるまでほとんど寝ていた。

12時に親に起こされて昼ごはんを食べたが眠気がなくならなかったので布団でぼーっとしていた。 していたら18時になってしまった。きびしい

夜は花譜不可解弐Q2を見た。

編入勉強は英語をやらないと(短期間で伸ばすのは難しいので)いけないなあと思って高専1,2年生のときの担任の一押しの教科書を出して、読んだ。 全部で16chapterまであったので1日1chapterやって1か月で2週出来たらいいなあと思った。 日記を書いている時点で1chapter終わってないので無理ですね。

ありがとう。

AtCoder Beginner Contest 195に参加した。

A

倍数判定をする

B

難しい。解法を思いつくまでにも時間がかかったしわかってから2ペナつけた。

みかんをi個選んだ時、重さの最小値、最大値はになる。 を満たすiの最小と最大が答え。Wはキログラムなので1000倍しておく。

探索するiの範囲が小さすぎて1ペナ。大きくしたら32bitからはみ出て1ペナをした。

signed main() {
  i64 a, b, w;
  cin >> a >> b >> w;
  w *= 1000;
  i64 ansmin = inf, ansmax = -inf;
  for (i64 i = 1; i < 100000000; ++i) {
    if (a * i <= w and w <= b * i) {
      chmin(ansmin, i);
      chmax(ansmax, i);
    }
  }
  if (ansmin == inf)
    cout << "UNSATISFIABLE" << endl;
  else
    cout << ansmin << " " << ansmax << endl;
}

C

難しい。

1
2
...
999
1,000
1,001
...
999,999
1,000,000
1,000,001
...

を見るろ、一番右側にある,はN-999個であることがわかる。同様に右から2番目に存在する,はN-999999こである。

int main() {
  i64 n;
  cin >> n;
  i64 ans = 0;
  ans += max(0_i, n - 999_i);
  ans += max(0_i, n - 999999_i);
  ans += max(0_i, n - 999999999_i);
  ans += max(0_i, n - 999999999999_i);
  ans += max(0_i, n - 999999999999999_i);
  cout << (ans) << endl;
}

D

N,M,Qが小さいので何してもよさそうな感じがする。

荷物は価値の大きい順、重さの軽い順でソートする。

箱は毎回multisetで管理する。 荷物を価値の大きい順にみていってその荷物を入れることが出来るはこのうちもっとも 容量が小さいものに入れるという貪欲で答えが出る。

int main() {
  int n, m, q;
  cin >> n >> m >> q;
  vector<pii> wv(n);
  vector<int> x(m);
  cin >> wv;
  cin >> x;
  sort(begin(wv), end(wv), [](pii a, pii b) {
    return a.second == b.second ? a.first < b.first : a.second > b.second;
  });
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--, r--;
    multiset<int> box;
    rep(i, m) if (i < l or r < i) box.emplace(x[i]);
    int ans = 0;
    for (auto [w, v] : wv) {
      if (box.empty())
        break;
      auto itr = box.lower_bound(w);
      if (itr == end(box))
        continue;
      box.erase(itr);
      ans += v;
    }
    cout << ans << newl;
  }
}

E

わからなかった。 DP[i][j] := i桁目まで見て余りがjになるものが存在する。

というDPを考えたが何にもならない。

解説を読んで通した。