Asa's Blog

ABC204

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.06.06. Last Modified on 2020.06.06.

前回のAHC003 に引き続き、競プロ振り返りますかね…。

今回解けたのは、A-C問題。Dも解けそうだったけどWA出た…。

問題概要

A

3人でじゃんけんして、あいこだった。2人の手が与えられるので、残り1人の手を求める。
なお、 0 はグー、 1 はチョキを、 2 はパーを表す。

B

$ N $ 本の木があって、 $ i $ 番目の木には $ A_i $ 個の実がある。
木の実が11個以上の時、 10個残してそれ以外すべて収穫するとき、全部で何個収穫するか。

C

1-indexedな $ N $ 個の都市と、1-indexedな $ M $ 個の道路。道路 $ i $ を通ると $ A_i \to B_i $ に一方通行できる。
0本以上の道路を使っていける、スタート地点とゴール地点の組としてあり得るのは何通り?

D

$ N $ 品の料理を作りたい。料理 $ i $ はオーブンを連続で $ T_i $ 分使って作れる。1オーブンで同時に作れるのは1料理のみ。2つのオーブンだけを使える。
すべて作るのにかかる最短時間は?

提出結果

ここから 提出結果がわかります。

A

提出 #23210769 - AtCoder Beginner Contest 204

#include <bits/stdc++.h>
using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  int c;
  if(a == b){ c = a; }
  else{ c = 3 - a - b; }
  cout << c << endl;
  return 0;
}

同じなら c = a にして、違うなら全部とは違う手にする。「0 はグー、 1 はチョキを、 2 はパー」なので、残りの手は、$ 3 - (a + b) $ で求められるという。
提出時刻は 21:01:12 なので、開始72秒で提出。前回よりも早くなった…!

B

提出 #23215639 - AtCoder Beginner Contest 204

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

int main(){
  int n;
  cin >> n;
  ull c = 0;
  loop(i,n){
    int a;
    cin >> a;
    if(a > 10){ c += a-10; }
  }
  cout << c << endl;
  return 0;
}

「木の実が11個以上の時、 10個残してそれ以外すべて収穫」、つまり $ A_i \gt 10 $ なら $ (A_i - 10) $ 個収穫できるので、全部の $ A_i $ に対してこの収穫数を加えればOK。
確認作業含め、提出時刻は 21:03:26 。前回より早く解けました!

C

提出 #23245855 - AtCoder Beginner Contest 204

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

vector<bool> seen;
ull2d Graph;
ull c = 0;

void dfs(ull v) {
  seen[v] = true;
  c++;
  for (ull next_v : Graph[v]) {
    if(seen[next_v]) continue;
    dfs(next_v);
  }
}

int main(){
  ull n,m;
  cin >> n >> m;
  seen.resize(n);
  Graph.resize(n);
  loop(i,m){
    ull a,b;
    cin >> a >> b;
    Graph[a-1].push_back(b - 1);
  }
  loop(i,n){
    seen.assign(n,false);
    dfs(i);
  }
  cout << c << endl;
  return 0;
}

DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita
こちらの記事を参考に(ほぼコピペ)して解けました。

解説より、計算量は $ O(N(N+M)) $ になるようです。一応TLEなしで解けました。

「グラフ苦手…」で飛ばした + 「DFS知らん…」で提出時刻は 22:08:16 。グラフをもっと学ばなければ……。

D(WAコード)

提出 #23248390 - AtCoder Beginner Contest 204

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

int main(){
  int n;
  cin >> n;
  ull1d t(n);
  loop(i,n){ cin >> t[i]; }
  sort(all(t),greater<ull>());
  int a=0,b=0;
  loop(i,t.size()){
    if(a+t[i] <= b){ a += t[i]; }
    else{ b += t[i]; }
  }
  cout << max(a,b) << endl;
  return 0;
}

えっと、大きい順にソートして、少ないほうに数字を加えるという雑手段()
一応サンプルだと全部通ったので、ワンチャンいけないかなーという…。
最初はbit全探索とか考えたんですけど、さすがに $ 2^{100} $ はTLEの未来しか見えないのであきらめました()

まじでこれでつまずきましたね……。

なるほど、この解法だと、A:[3,2] B:[3,2,2] になってしまうのか…とようやく理解……。

解説では動的計画法みたいです。動的計画法も学ばなければ…。

ちなみに、その前に提出していた 提出 #23238750 - AtCoder Beginner Contest 204 は、謎の二分探索しています()

結果と感想

微増しました。3,830位の+8です。

D問題での反例探しができていれば、思考が固定されなかったのかなぁと…。
このレートを維持できるように特訓しなければ…。

DFSを初めて使った。

keyboard_arrow_up