Asa's Blog

ABC203

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.05.31. Last Modified on 2020.05.31.

ABC203振り返りします。(唐突)

今回解けたのは、A-C問題です。もうちょっと解きたかった…。

問題概要

A

サイコロを3つ振った。出た目は $ a,b,c $。これらのうち、ある2つが同じなら残りの1つを、同じものがなければ0を出力する。

B

$ 1 \leq (N, K) \leq 9 $ 。 $ i \in N , j \in K $ に対して、i0j(3桁の数字)の総和は?

C

村 $ i $ で 1円払うと、村 $ (i+1) $ に移動できる。 $ N $ 人の友だちがいて、友だち $ i $ は、村 $ A_i $ に着くと $ B_i $ 円をくれる。 最初、 $ K $ 円持って村0にいる。 最終的にたどり着ける村は?

提出と結果

こちらから 私の実装を見れます。

A

提出 #23034219 - AtCoder Beginner Contest 203(Sponsored by Panasonic)
問題で指示されたように、if文で場合分けすれば十分です。

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

提出時刻は 21:01:20 なので、開始80秒で提出できました。爆速!!
実行時間は7ms、メモリは3628KBになりました。

B

提出 #23040604 - AtCoder Beginner Contest 203(Sponsored by Panasonic)
$ (N,K) \leq 9 $ という制約から、2重ループでも十分間に合いそうです。
i0j という3桁の数字は、 $ 100 \cdot i + j $ で表せます。

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int main(){
  int n,k;
  cin >> n >> k;
  ull c=0;  // 出力する総和
  for(int i=1;i<=n;i++){
    for(int j=1;j<=k;j++){
      c += i*100 + j;  // 「i0j」を加える
    }
  }
  cout << c << endl;
  return 0;
}

提出時刻は 21:04:06、実行時間は9ms、メモリは3596KBになりました。

かなり早く解けるようになったと思います。

C

提出 #23048601 - AtCoder Beginner Contest 203(Sponsored by Panasonic)
$ N \leq 2 \times 10^5, (K, B_i) \leq 10^9 $ なので、たどり着ける最大の村は $ 2 \times 10^{14} + 10^9 $ となるので、いちいち「たどり着いたらお金をプラスして、1村渡るごとにお金をマイナスして…」としても当然間に合わないですよね…
そこで、現在の所持金で次の友だちがいるところまでたどり着けるかを考えます。
友だちの数は $ N (\leq 2 \times 10^5) $ なので、1重ループ(?) なら間に合います。

ここで、村を1つ通過するには1円しかかからないことから、一般に村を $ n $ 個通過するには $ n $ 円必要だとわかります。
なので、村0から村 $ A_1 $ に行くには $ A_1 $ 円が必要で、村 $ A_1 $ から 村 $ A_2 $ に行くには $ (A_2 - A_1) $ 円が必要で、…と繰り返すと、村 $ A_n $ に行くには $ A_n $ 円が必要なわけです。
よって、友だちのいる村で着くまでの経費( $ A_{i} - A_{i-1} $ )を求めて、所持金と比較して、足りるなら所持金を $ B_i $ 増やして、…としなくても、所持金に貰った金額を足して、その金額が次の村番号より小さいことを確認できればよくなります。

私の場合の実装はこうです。

  1. 入力を取り込みます。ここで $ O(N) $ かかります。
  2. 「累計金額」を $ K $ (現在の所持金)に設定します。
  3. 友だちを近い順($ A_i $ が小さい順)にソートします。$ O(N \log N) $ かかります。
  4. 友だちが待っている村 $ A_i $ にたどり着ければ、「累計金額」に $ B_i $ を加えます。たどりつけなければ、ループを抜けます。ループを抜ける最大時間は $ O(N) $ です。
  5. 上述したように、「累計金額」が、最終的にたどり着ける村番号になります。全体で $ O(N \log N) $ なので、実行時間制限には間に合います。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ull1d = vector<ull>;
using ull2d = vector<ull1d>;
#define loop(i,n) for(ull i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()

int main(){
  int n,k;
  cin >> n >> k;
  ll c=k;  // 「累計金額」
  ull2d v(n,ull1d(2,0));
  loop(i,n){  // 入力
    ull a,b;
    cin >> a >> b;
    v[i] = {a,b};
  }
  sort(all(v), [](ull1d& a, ull1d& b){ return a[0] < b[0]; });  // 近い順にソート
  loop(i,n){
    if(c < v[i][0]){ break; }  // たどり着けないなら、ループを抜ける
    else{ c += v[i][1]; }  // たどり着けるなら、「累計金額」を加える
  }
  cout << c << endl;  // 「累計金額」を出力
  return 0;
}

提出時刻は 21:11:14、実行時間は516ms、メモリは20348KBになりました。
やっぱり時間とメモリ食いますね…

その後、D-Fをいろいろ試すも答えが合わず、諦めた。

結果と感想

1,393位で、レーティングは+121。7級になりました。

今回の問題が比較的簡単だったのかもしれませんが、C問題までを解くのに10分強しかかかっていないのは、かなり成長を感じました。このペースを維持できるように精進していきたいですね。

それと、今回初の振り返り記事。振り返ると記憶に定着し、また他者にもわかるように説明することでより理解が深まるという、誰かが言っていたメソッド。三日坊主にならないよう頑張りたいですね。

三日坊主にならないかが心配...

keyboard_arrow_up