読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC #020

昨日参加したコンテスト。
D問題が難しすぎたため全完ならず315点。

- A問題「クイズ」

(http://abc020.contest.atcoder.jp/tasks/abc020_a)

問題概要:
1が入力されたら大会の名前、2が入力されたらAtCoder社長のハンドルネームを出力するというもの。
社長の本名はchokudaiではありません。あくまでもハンドルネームです。

解法:
if文で場合分けしましょう

ソースコード:
https://abc020.contest.atcoder.jp/submissions/364225



- B問題「足し算」

(http://abc020.contest.atcoder.jp/tasks/abc020_b)

問題概要:
整数AとBが与えられ、AとBを連結してできた数字の2倍の数字を答えよ。

解法:
intとして受け取らずにstringとしてAとBを受け取れば連結が簡単です。
A,Bが1以上の値なのでこの連結で問題ないです。
stringをintに変換し、その倍の値を出力すればAC。
std::stoiを使えば変換できます。この関数はC++11の関数なので言語に注意。

ソースコード:
https://abc020.contest.atcoder.jp/submissions/364293


- C問題「壁抜け」

(http://abc020.contest.atcoder.jp/tasks/abc020_c)

問題概要:
縦H,横Wでマス目に区切られた長方形が与えられます。
長方形には白マスと黒マスが存在し、隣の白マスに進むには1秒かかり、隣の黒マスに進むのはx秒かかります。
スタート地点とゴール地点は白マスです。T秒以内にゴールが可能なxの最大値を求めよ。

解法:
xが決まっていればT秒以内にたどり着けるかどうかはダイクストラ法を使えばO(HW \log {(HW)})で求められます。
xの最大値はT-1、Tの最大は10^9なので全てのとりうるxについて判定を行うわけにはいきません。
ただしx=iのときT秒以内にたどり着けるならばj < iを満たすx=jのときにもT秒以内にたどり着くことが可能です。
x=iのときT秒以内にたどり着けないならばj > iを満たすx=jのときにもT秒以内にたどり着くことは不可能です。
この条件を満たすとき、xについての二分探索が可能なので二分探索とダイクストラ法を組み合わせるとO(HW \log {(HW)}\log T)で求められます。

ソースコード:
https://abc020.contest.atcoder.jp/submissions/364844


- D問題「LCM Rush」

(http://abc020.contest.atcoder.jp/tasks/abc020_d)

問題概要:
N,Kが与えられ、[tex:\sum_{i=1}^N LCM(i,K) を求めよという問題です。

解法:
解けなかったので解説生放送の受け売りです。
Nの値が10^9なのがやっかいです。
ここで、LCM(m,n)=\frac{mn}{GCD(m,n)}であることに注目します。
解は、\sum_{X} \sum_{GCD(i,K)=X} \frac{i*K}{GCD(i,K)}=\sum_{X} \sum_{GCD(i,K)=X} \frac{i*K}{X} = K*\sum_{X} \frac{1}{X} \sum_{GCD(i,K)=X} i
GCD(i,K)のとる値はKの約数です。
10^9以下の値の約数の個数の最大は1344個らしいのでKの約数を事前にO(\sqrt{K})で列挙しておき、GCD(i,K)=Xを満たすiの総和を計算すれば良さそうです。
ここで、GCD(i,K)=Xについて、i=n*XかつXよりも大きいKの約数YについてGCD(i,K)=Yを満たさないiがこれを満たす。
i=n*Xを満たすiの総和はO(1)で求められる。
i=n*Xを満たすがXよりも大きいKの約数YについてGCD(i,K)=Yも満たすiはY=m*Xが成り立つはずなので、
Y%X==0を満たしYで、GCD(j,K)=Yを満たすjの総和を上で求めた和から引いてやれば良い。
このXの大きい順から求めていけば計算量は約数の個数の2乗程度なので十分間に合う。

ソースコード:
https://abc020.contest.atcoder.jp/submissions/366341