AtCoder Regular Contest (ARC) #034 参加記

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点の状態でカードをシャッフルしてカードを引いていき、以下のルールで点を付けた時の期待値を求める。(引いたカードは破棄する)

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

解法

解けなかった。

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>