Asa's Blog

ABC209

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.07.10. Last Modified on 2021.07.10.

入 緑 フ ラ グ 回 収 再 び

問題概要

A

A 以上 B 以下の整数の個数

B

$N$個の商品があって、$i$番目の定価は$A_i$円。セール中で$i$が偶数なら 1 円引きで買える。$X$円持っているとき、全部買える?

C

長さ$N$の整数列$C$で、以下の条件をすべて満たす長さ$N$の整数列の個数を、$(10^9)+7$で割った余りを出力

  • $1 \le A_i \le C_i$
  • $A_i \ne A_j (i \lt j)$

D

$N$個の街と$N-1$本の道。$i$本目の道は街$a_i$と$b_i$を双方向に結んでいる。なお道の長さは全部同じ。
$Q$個のクエリで$c_i$と$d_i$が与えられる。1 人が$c_i \rightarrow d_i$に、もう 1 人が$d_i \rightarrow c_i$に同じ速さで移動すると、2 人は街で出会うか、道で出会うか。

提出

いつも通りここから全部見れます。

A

提出 #24101976 - AtCoder Beginner Contest 209

さんすう。$B-A+1$を出力する。ただし、$B \lt A$なら、存在しないので 0 を出力。

#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  if(b < a){ cout << 0 << endl; }
  else{ cout << (b-a+1) << endl; }
  return 0;
}

提出時刻は 21:01:02 でした。危うく場合分けをせずに提出するところだった…。入力例に感謝。

B

提出 #24109664 - AtCoder Beginner Contest 209

制約が$N \le 100$なので、素直に計算して間に合います。なお、問題文中では商品は 1-indexed ですがプログラム中では 0-indexed なので、「偶数番目」を「i が奇数の時」とする必要があるので注意。

#include <bits/stdc++.h>
using namespace std;
#define loop(i, n) for (ull i = 0; i < n; i++)

int main() {
  int n, x;
  cin >> n >> x;
  loop(i, n) {
    int a;
    cin >> a;
    if (i % 2 == 1){ a--; }
    x -= a;
  }
  if (x < 0) { cout << "No" << endl; }
  else { cout << "Yes" << endl; }
  return 0;
}

提出時刻は 21:03:48。念のためコンパイルしてテストしたので、ちょっと遅れた。

C

提出 #24119034 - AtCoder Beginner Contest 209

C 問題で「$(10^9+7)$で割った余りを出力してください」って見たことなかったのでちょっと驚いた。1 回ソートして、$C_i - i$を順番に掛けていけば、「場合の数」的に OK(提出時ちょっと不安だった)。

あと、AtCoder Libraryを使ってみた。これは AtCoder の公式ライブラリで、いろいろ便利なのが入ってる(語彙力)。

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define loop(i, n) for (ull i = 0; i < n; i++)
#define all(vec) vec.begin(), vec.end()

typedef modint1000000007 mint;

int main() {
  int n;
  cin >> n;
  ull1d c(n);
  loop(i, n) { cin >> c[i]; }
  sort(all(c));
  mint ans = 1;
  loop(i, n) { ans *= c[i] - i; }
  cout << ans.val() << endl;
  return 0;
}

提出時刻は 21:11:00。割と早めに解けた印象。

D

○─○─○○─○─○─○ のようなグラフを描けばわかりますが、道数が偶数なら街で、奇数なら道で出会うことになります。
そこまではよかったんだ…。

提出 #24133655 - AtCoder Beginner Contest 209
最初、全部の点について、点から点の最短道数を数えたんですよね。サンプルなら大丈夫だったんですが、当然TLEが出ますよね。…かと思ったらREですよ。

提出 #24138951 - AtCoder Beginner Contest 209
その後、「えー RE ってなんで出てるんだーー??」って悩んだ挙句、「よくよく考えたらある 1 点からの道数数えればよくね?」ってなり、実装すると、計算量的にセーフになりました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> ll1d;
typedef vector<ll1d> ll2d;
#define loop(i, n) for (ull i = 0; i < n; i++)
#define all(vec) vec.begin(), vec.end()

ll2d Graph;
ll1d dp;
vector<bool> seen;

void dfs(ll i, ll c) {
  seen[i] = true;
  c++;
  for (ll x : Graph[i]) {
    if (seen[x]) { continue; }
    else {
      dp[x] = c;
      dfs(x, c);
    }
  }
}

int main() {
  ll n, q;
  cin >> n >> q;
  Graph.resize(n);
  dp.resize(n);
  seen.resize(n);
  loop(i, n - 1) {
    ll _, __;
    cin >> _ >> __;
    _--;
    __--;
    Graph[_].push_back(__);
    Graph[__].push_back(_);
  }
  dfs(0, 0);
  loop(i, q) {
    ll c, d;
    cin >> c >> d;
    if (abs(dp[--c] - dp[--d]) % 2 == 0) { cout << "Town" << endl; }
    else {
      cout << "Road" << endl;
    }
  }
  return 0;
}

ちなみに dp っていう変数があるのは適当に名付けたからです。多分動的計画法ではない気がします。

ミス解法の提出時刻が 21:53:28 で、AC 解法が 22:19:19 でした。すぐに気づければよかった…。

結果と感想

この通り逆ボーダーです。はい。普通に悲しいです。次回こそ入緑します。

ちなみに E 問題、解き方はすぐにわかりました。でも 15 分で解けるほどの実力がありませんでした。はい。悲しい。

再び「入緑フラグ」を建築しました。

keyboard_arrow_up