AtCoder Beginner Contest 182回目のA・B問題
AtCoder Beginner Contest 182回目、A問題、ツイブラーかな。問題文、あなたはツイブラーというSNSをしています。
ツイブラーでは、フォロー数が2×フォロワー数×100を超えない範囲でフォロー数を増やすことができます。
あなたの現在のフォロワー数はAで、フォロー数はBです。 フォロー数はあといくつ増やせますか?
AとBが与えられますので、コードテストで使おうか。
AとB、マップ、インとインプット、ロット、スプリット。
で、AとBが200、300だったら200を出力する。
フォロー数は2×200×100、イコール500まで増やせるので、あと200増やせます。
じゃあ、Cイコール2×A×100、プリント、マックス0でB-Cかな。
マイナスにいっちゃうと意味ないのでね。あれ?0になった。逆?
フォロワー数がAでフォロー数がBです。
2×フォロワー数×2×A×100でしょ。
絶対値取った方がいいのか?逆か。
C-Bか。入力例2は2万100。
マックス0で取る必要ないか。なかった気がする。
提出。ACしたのでB問題いきます。
B問題。オールモストGCD問題文。数列Aが与えられます。
正の整数KのGCD度をA1からANのうちKで割り切れるものの数と定義します。
2以上の整数のうちGCD度が最大になるものを1つ求めてください。
GCD度が最大のものが複数ある場合、どれを出力してもかまいません。
入力例1、3、Nが3のAの数列は3、12、7で出力は3。
3、12、7のうち3、12の2つが3で割り切れるので3のGCD度は2です。
2以上の整数でこれより大きいGCD度を持つものは存在しないので3は正答です。
GCDというのが最大公約数のこと。
最大公約数の数を求めろ?違うか。最大公約数を求めろ?
でも3だもんだ。3、12の2つが3で割り切れるので3のGCDの2以上の整数。
せーの整数、KのGCD度。 Kで割り切れるもの、2以上の整数、はいはいはい、とりあえず
Nイコールイントインプット、で、Aイコール
リストのマップのイントインプット
スプリット、で
アンスイコール0にして4Yインレンジ
どうしよっかな。 2スタートのMAXA
プラス10とかにしとこうかな。 で、IF Aの
あ、そうか。 20ループか。
A品大文字A
IF A%i
イコールイコール0なら
アンサーの他にTMPも入れないといけないね。 1個目の方分の後にTMPを入れてTMPイコール0で
IF A%i イコールイコール0だったら TMPプラスイコール1
で、アンサーイコールMAXの
アンサーかTMPか。 で、プリントアンサーで
いいんじゃない?ダメ?
入力例1は3が出たらオッケー。 2。
2か。そっか。 3?
3と12の2つが3で割り切れるので、3のGCD度は2です。 ややこしいなぁ。
そうか。
割る数が大きい方がじゃないんだ。 GCD度を求めないといけないから
GCDイコール0
と、IF GCDが
TMPより小さかったら、TMPが大きかったらアンサーはイコールiだ。 これでいけるか?
12が出た。 12が出たかぁ。
アンサーiじゃダメだなぁ。 そうか。GDPも入れ替えないといけないか。
GDPじゃない。 GCD。
GCDイコールTMPにして、 アンサーイコールi。
うん。3が出ましたね。ようやっと。 入力例2は9が出たらオッケー。
2。 2。
なんで?
ん? この場合9のGCD度は4です。2や3のGCD度も同じく4なので、2や3が出力しても構いません。
あ、じゃあオッケーだな。 あーびっくりした。
入力例3は2が出たけど、出力例は1000。 これも2で大丈夫なのかな?
1回出してみましょうか。 これでちょっとダメだったら解説みよう。
あ、エーシーしました。よかった。C問題いきます。 C問題2・3。
AtCoder Beginner Contest 182回目のC問題
問題文。各桁に0が出現しないような正の整数Nが与えられます。
Nの桁数をKとします。 Nの桁を0個以上K個未満消して、
残った桁をそのままの順序で結合することで3の倍数を作りたいです。
3の倍数を作ることができるか判定し、作ることができるなら、
作るのに必要な最小の消す桁数を求めてください。 Nは10の18乗。
各桁に0が出現しない整数。 3の倍数を作ることができないならマイナス1を作ることができるなら、
作るのに必要な最小の消す桁数を出力せよ。 入力例1、35。
出力例1、5。あ、違う、1。 5を消した3という数は3の倍数です。この時消した桁数は1。
で、最小です。 入力例2、369は出力例0。1つも桁を消さなくてもいいことに注意してください。
入力例3、6227384。 出力例3、1。例えば8を消した622734は3の倍数です。
入力例4、11。 出力例はマイナス1。消す桁数はNの桁数をKとして0個以上K込みでなければならないため、
全部の桁を消すことはできないことに注意してください。 この場合問題文に従って3の倍数を作ることは不可能なため、マイナス1を出力します。
うん、うーんっと。 これなんか解き方あったよなぁ。
10、20。 なんか全部の桁数を足して
3の倍数だったら3ですみたいな やつがあった気がするんですが、ちょっと覚えてないので解説を見てみましょうか。
なんか、 正の整数が3の倍数であることとその数のすべての桁の和が3の倍数であることは同時です。
すべての桁の和を3の倍数にするために消す桁を考えるにあたって以下の情報だけあれば十分です。
3で割った余りが0の桁。 3で割った余りが1の桁の数。 3で割った余りが2の桁の数。
これを踏まえた上で場合分けをします。 すべての桁の和を3で割った余りが0の場合、この場合すでにNは3の倍数なので答えは0です。
すべての桁の和を3で割った余りが1の場合、この場合少なくとも1つ桁を消さないといけません。
3で割った余りが1の桁が存在する場合、その桁を消せば良いので答えは1です。
ただしNがもともと1桁だった場合、すべての桁を消すことになってしまうので答えは-1です。
そうでない場合、3で割った余りが0または2の桁だけから構成されるので、3で割った余りが2の桁が2個以上あるはずです。
そのような桁を2つ消せば良いので答えは2です。
ただしNがもともと2桁だった場合、すべての桁を消すことになってしまうので答えは-1です。
すべての桁の和を3で割った余りが2の場合、余りが1の場合と同様です。
3で割った余りが2の桁が存在する場合、その桁を消せば良いので答えは1です。
ただしもともと1桁だったら-1です。
Nの桁数や3で割った余りが0の桁の数などはNを十進数転換すれば求められます。
Nが0になるまでNを10で割った余りを記録し、Nを10で割るということを繰り返すと十進数転換できます。
CやC++で10の18乗といったような大きな数を扱うためには、64ビット以上の幅を持つ整数型を使う必要があります。
他にもNが18桁しかないので、消す桁を二進数を使って全探索するという方法もあります。
全探索できるんだ。ちょっとPythonの回答例を見ておこうと思います。
ではまた次回お疲れ様です。