ARC #034参加しました。
ARCは公式解説があるので、解けなかった問題は概要のみです。解き直ししたら、追記または別途記載します。
A – 首席
問題概要
N人分のテストの点数が与えられるので、4教科の合計とマークシート塗り絵の点数*(110⁄900 )を合計が最も高い点数を答える。
解法
N<3049なので全員分の点数を持っていても問題ありませんが、必要なのは最大値だけなので、1人ごとに最大値判定をして現在の最大値だけを持っていればOKです。ただ、塗り絵の点数分が実数になる場合があるので、答えを保持する変数は実数型である必要があります。また、出力時の小数点以下の精度にも注意が必要です。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| int n; | |
| cin>>n; | |
| double ans=0; | |
| for (int i=0; i < n; i++) { | |
| int a,b,c,d,e; | |
| cin>>a>>b>>c>>d>>e; | |
| ans=max(ans,a+b+c+d+(e*(110.0/900.0))); | |
| } | |
| // cout<<ans<<endl; | |
| printf("%.6lf\n",ans); | |
| return 0; | |
| } |
B – 方程式
問題概要
数値nに対して、i+f(i)=nとなるiの個数を答える。
ただし、f(i)はiの全ての桁の数値を合計した数である。(ex.f(123)= 1+ 2 + 3 = 6)
解法
n<10^18なので、全ての探索は不可能です。
しかし、f(i)の最大はf(10^18)=9*19=171なので、n-171より小さい値については絶対にi+f(i)=nにならないので、その部分だけ=nになるか判定すればOKです。
コード
本番中は、f(10*18)よりもすこし多めに見積もったので差が181にはなっていません。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| long long int n; | |
| cin>>n; | |
| vector<long long int> ans; | |
| long long int j=max((long long int)0,n-181); | |
| for (; j <= n; j++) { | |
| bool flag=false; | |
| long long int tmp=j,sum=0; | |
| while (tmp>0) { | |
| sum+=tmp%10; | |
| tmp/=10; | |
| } | |
| if(sum+j==n) | |
| ans.push_back(j); | |
| } | |
| cout<<ans.size()<<endl; | |
| for (int i=0; i<ans.size(); i++) { | |
| cout<<ans[i]<<endl; | |
| } | |
| return 0; | |
| } |
C – 約数かつ倍数
問題概要
2 個の正整数 A,B が与えられる。
A! (A * A-1 * … * 2 * 1) の約数かつ、かつ B! の倍数である正整数の個数を 1,000,000,007 で割った余りを求めよ。
解法
解けなかった。
D – インフレゲーム
問題概要
赤い整数の書かれたカードがA枚、青い整数の書かれたカードがB枚、’湯たんぽ’と書かれたカードがC枚ある。
初期点数を0点の状態でカードをシャッフルしてカードを引いていき、以下のルールで点を付けた時の期待値を求める。(引いたカードは破棄する)
- 赤いカードを引く:書かれた整数分、点数を加算
- 青いカードを引く:書かれた整数*点数を点数とする
- ‘湯たんぽ’カードを引く:ゲームを終了する
解法
解けなかった。