Asa's Blog

ABC208

Tags: AtCoder  ABC  Competitive-Programming 

Published on 2021.07.04. Last Modified on 2021.07.04.

入 緑 フ ラ グ を 回 収 し ま し た

問題概要

A

サイコロを $A$ 回振ったら $B$ になりえる?

B

$1!, 2!, \ldots 10!$ 円硬貨があって、 $P$ 円をおつりなしで支払うとき、最小で何枚?

C

それぞれに国民番号 $a_i$ がついた $N$ 人の国民がいる国。$K$ 個のお菓子を配るとき、$i$ 人目の人は何個お菓子がある?
配り方:残りのお菓子が $N$ 個以上なら、みんなに 1 個ずつ配る。それ以外なら、国民番号が小さい順に 1 個ずつ残りを配る。

提出

A

提出 #23949227 - AtCoder Beginner Contest 208

$A$ 回振ったときの最小値は、全部 1 が出たときの $A$。同じように、最大値は $6A$ 。この範囲内なら全部がなりえるので、この場合に Yes。それ以外は No

#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  if(6*a < b || a > b){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
  return 0;
}

提出時刻は 21:01:14。A 問題 1 分半以内が安定してきた…!

B

提出 #23958309 - AtCoder Beginner Contest 208

$10! = 10 \times 9!$ などとすると、一般に $n!$ 円硬貨は高々 $n$ 枚しか使わなくて OK です。
$10! = 3,628,800$ で、$P \le 10^7$ なので、こちらは 3 枚で済みそう。

そして $i=10$ から順に ans に $\lfloor \frac{P}{i!} \rfloor$ を足して、$P$ から $i! \times \lfloor \frac{P}{i!} \rfloor$ を引きます。つまり $P$ に $P \mathrm{mod} i!$ を代入します。

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

ull fact(int a){
  ull res = 1;
  for(int i=1;i<=a;i++){
    res *= i;
  }
  return res;
}

int main(){
  ull p;
  cin >> p;
  int ans = 0;
  for(int i=10;i>=1;i--){
    ull a = fact(i);
    ans += p/a;
    p %= a;
  }
  cout << ans << endl;
  return 0;
}

最初 10! = 3,628,800 で、9! = 362,880 で、…を手書きでやろうとしたので、 提出時刻は 21:06:41 です。ただのバカです。

C

提出 #23964293 - AtCoder Beginner Contest 208

みんなに分けられる$\lfloor \frac{K}{N} \rfloor$個を最初に分けちゃいます。そして、国民番号を昇順にソートして、余りを順番にあげます。そのあとに $i$ の順でソートして出力します。

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

int main(){
  ull n,k;
  cin >> n >> k;
  ull2d v(n, ull1d(3));
  loop(i,n){
    v[i][0] = i;
    cin >> v[i][1];
    v[i][2] = k/n;
  }
  sort(all(v),[](auto& a, auto& b){ return a[1] < b[1]; });
  k %= n;
  loop(i,k){ v[i][2]++; }
  sort(all(v),[](auto& a, auto& b){ return a[0] < b[0]; });
  loop(i,n){
    cout << v[i][2] << endl;
  }
  return 0;
}

上のコードでは、$v[i][0]$ は $i$ の番号、 $v[i][1]$ は国民番号、$v[i][2]$はもらったお菓子の個数を入れています。

提出時刻は 21:13:12。ちなみに実行時間は 1082ms でした。
制約が倍だったら間に合わなかったかも…?あぶない…

結果と感想

今回のフラグ回収要因は、F 問題を見て「あっこれ授業でやったところだ!」ってなったせいです。解説見たらまったくやっていないところでした。つらい。

そして、またフラグを建てました。あと 10 なので、まあ次回もこのペースで解ければ大丈夫な気がしますが。

前回の「入緑フラグ」を回収しました...つらみ...

keyboard_arrow_up