ARC #034参加しました。
ARCは公式解説があるので、解けなかった問題は概要のみです。解き直ししたら、追記または別途記載します。
A – 首席
問題概要
N人分のテストの点数が与えられるので、4教科の合計とマークシート塗り絵の点数*(110⁄900 )を合計が最も高い点数を答える。
解法
N<3049なので全員分の点数を持っていても問題ありませんが、必要なのは最大値だけなので、1人ごとに最大値判定をして現在の最大値だけを持っていればOKです。ただ、塗り絵の点数分が実数になる場合があるので、答えを保持する変数は実数型である必要があります。また、出力時の小数点以下の精度にも注意が必要です。
コード
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にはなっていません。
C – 約数かつ倍数
問題概要
2 個の正整数 A,B が与えられる。
A! (A * A-1 * … * 2 * 1) の約数かつ、かつ B! の倍数である正整数の個数を 1,000,000,007 で割った余りを求めよ。
解法
解けなかった。
D – インフレゲーム
問題概要
赤い整数の書かれたカードがA枚、青い整数の書かれたカードがB枚、’湯たんぽ’と書かれたカードがC枚ある。
初期点数を0点の状態でカードをシャッフルしてカードを引いていき、以下のルールで点を付けた時の期待値を求める。(引いたカードは破棄する)
- 赤いカードを引く:書かれた整数分、点数を加算
- 青いカードを引く:書かれた整数*点数を点数とする
- ‘湯たんぽ’カードを引く:ゲームを終了する
解法
解けなかった。