ARC #034参加しました。 ARCは公式解説があるので、解けなかった問題は概要のみです。解き直ししたら、追記または別途記載します。

• コンテストページ
• 公式解説スライド
• 公式ニコ生解説放送
• chokudaiさん解説ソースコード

A - 首席

問題概要

N人分のテストの点数が与えられるので、4教科の合計とマークシート塗り絵の点数*(110⁄900 )を合計が最も高い点数を答える。

解法

N<3049なので全員分の点数を持っていても問題ありませんが、必要なのは最大値だけなので、1人ごとに最大値判定をして現在の最大値だけを持っていればOKです。ただ、塗り絵の点数分が実数になる場合があるので、答えを保持する変数は実数型である必要があります。また、出力時の小数点以下の精度にも注意が必要です。

コード

#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;
}a.cpp

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にはなっていません。

#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;
}b.cpp

C - 約数かつ倍数

問題概要

2 個の正整数 A,B が与えられる。 A! (A * A-1 * … * 2 * 1) の約数かつ、かつ B! の倍数である正整数の個数を 1,000,000,007 で割った余りを求めよ。

解法

解けなかった。

D - インフレゲーム

問題概要

赤い整数の書かれたカードがA枚、青い整数の書かれたカードがB枚、’湯たんぽ’と書かれたカードがC枚ある。 初期点数を0点の状態でカードをシャッフルしてカードを引いていき、以下のルールで点を付けた時の期待値を求める。(引いたカードは破棄する)

• 赤いカードを引く:書かれた整数分、点数を加算
• 青いカードを引く:書かれた整数*点数を点数とする
• ‘湯たんぽ’カードを引く:ゲームを終了する

解法

解けなかった。