私というにんげんが初めて水パフォを取ったABC449の記録

こんにちは、michikusamichiyaです。私というにんげんはついに初めて水色perfを取りました。

これを記念して記録を書きます。

成果

• 70:31 1ペナ ABCD完
• コンテストのリンク ABC449

問題A - π

正の整数$D$が与えられるので、直径が$D$の円の面積を求めよ。

簡単ですが、半径ではないことに注意です。
円の面積は、半径を$r$として$S=\pi r^2$ですが、今回は直径を半径に変換する必要があるので、$r=D/2$で面積は$S=\dfrac{\pi D^2}4$です。

また、念のためfixedとsetprecisionを付けておきましょう。誤差によるWAを防ぐための安心材料となります

using ld = long double
namespace mat {
  const ld PI = 3.141592653589793238462643383279502884L;
}
int main(void) {
  double D; cin >> D;
  cout << fixed << setprecision(11) << D*D*mat::PI / 4 << endl;
}

問題B - Deconstruct Chocolate

$H\times W$の長方形のチョコレートがあります。

1. 下$R$行のチョコレートを食べる。
2. 右$C$列のチョコレートを食べる。

というクエリが与えられるので、実際にクエリを行い、食べたチョコレートブロックの個数を求めよ

という概要です。

残っているチョコレートのサイズを$h\times w$とします。そうすると、それぞれのクエリで

1. $wR$個
2. $hC$個

のチョコレートを食べることになります。また、チョコレートを食べると

1. $H$が$R$減る。
2. $W$が$C$減る。

ので、それをそのまま実行するといいです。また、どんな食べ方でもチョコレートは長方形なのでOK。

int main(void) {
  int H, W, Q; cin >> H >> W >> Q;
  while (Q--) {
    int qt; cin >> qt;
    if (qt == 1) {
      int R; cin >> R;
      cout << R*W << endl;
      H -= R;
    } else {
      int C; cin >> C;
      cout << C*H << endl;
      W -= C;
    }
  }
}

問題C - Comfortable Distance

長さ$N$の文字列$S$と整数$L\leq R$が与えられます。ここで、

• $1\leq i\leq j\leq N$
• $S_i=S_j$
• $L\leq j-i\leq R$

を満たす$(i,j)$の組を求めよ。

愚直にやると$O(N^2)$の時間を食いそうです。$N\leq 5\times10^5$なので制限時間に間に合いそうにありません。
たいていこういうのは各アルファベットごとに処理すればどうにかなります。これはどういうことかというと、

vector<vector<int>> cnt(26);
rep(i, N) cnt[S[i] - 'a'].push_back(i);

というように、各アルファベットごとに「そのアルファベットのインデックス一覧」を作っておくことで、各「等しい」成分に分けることができます。

そして、すべての$\text{cnt}[i]$は昇順なので、$L\leq j-i\leq R$という条件は二分探索で数え上げられます。
upper_bound(..., cnt[i] + R) - lower_bound(..., cnt[i] + L)で出せますね。
計算量は大体$O(N \log N)$です。

int main(void) {
  ll N, L, R; cin >> N >> L >> R;
  string S; cin >> S;
  // solve
  vector<vector<int>> cnt(26);
  rep(i, N) {
    it[S[i] - 'a'].push_back(i);
  }
  ll ans = 0;
  rep(d, 26) {
    vector<int> c = cnt[d];
    for (const auto f : c) {
      ans += upper_bound(all(c), f + R) - lower_bound(all(c), f + L);
    }
  }
  cout << ans << endl;
}

問題D - Make Target 2

こういう的っぽい奴の中で、ある領域に囲まれたやつを求めよ。
縦横の長さは最大で$2\times 10^6$

これは結構見つけてしまえば簡単です。コードを見た方が速いかと思われます。

int main(void) {
  ll L, R, D, U; cin >> L >> R >> D >> U;
  // まずは横軸方向
  /***************
   * 考察メモ
   * 正方形が何重にも重なっているような形。
   * 内側からt番目 (0-based)の正方形の横線はy=2|t|にある
   * またその成分の長さ(?)は4|t|+1。
   * sum(i in [D,U])だね殺します
   * ただ制約上forループは少なくて済む
   * 一応線分が範囲内にいるかだけ確かめる
   */
  ll ans = 0;
  for (ll i = D; i <= U; i++) {
    if (i % 2 == 0) ans += max((min(abs(i), R) - max(-abs(i), L))+1, 0ll);
    // [-|i|, |i|]と[L, R]の共通区間なんだよな?
    // だったらそれは[max(-|i|, L), min(|i|, R)]で、
    //  BREAKPOINT;
  }
  /********************
   * 考察メモ2
   * これを縦方向に対しても行う
   * ただかぶりが発生するのでとりあえずいい感じにする
   * えーとなんだっけほうじょげんり?か
   * 余事象のアレ
   */
  for (ll i = L; i <= R; i++) {
    if (i % 2 == 0) ans += max((min(abs(i), U) - max(-abs(i), D))+1, 0ll);
    // BREAKPOINT;
  }
  /****************
   * 考察メモ3
   * さあ実際に取り除くことを考える
   * 正方形のかどっこ、取り除かないといけないのはそれ
   * x-->+に見ていって、正方形の範囲内にいるかどうかを確かめることにする
   * ｽﾋﾟｷｦｲｼﾞﾒﾅｲﾃﾞ!!
   */
  for (ll i = L; i <= R; i++) {
    /*********
     * 考案メモ4
     * iが偶数の時を考える
     * この時、触れてる正方形の角の、x=i上(伝われ)の点は(i,i),(i,-i)
     * これが範囲内にいるか
     */
    if (i % 2 == 0) {
      if (D <= i and i <= U) ans--;
      if (D <= -i and -i <= U) ans--;
      // BREAKPOINT;
    }
  }
  if (L <= 0 and 0 <= R and D <= 0 and 0 <= U) ans++;
  cout << ans << endl;
}

(提出した奴をそのまま書いてます)