この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/d4aba1192a81cf736eae
次：https://qiita.com/sano192/items/677ec26921f08586dd18
【目標】
・余りは足し算、引き算、掛け算ができることを覚える
【概要】
一見倍数に関係する問題だが、実際は余りの計算に関する知識が必要な問題。余りを計算して解く問題は頻出であるため、この問題でまず基礎知識を身に着けよう。
この問題はDifficultyが300近くある。このあたりから灰色コーダーの人にとってはじっくり考えないと解けない、難しい問題が出てくるが、じっくり時間を掛けて【方針】【実装】を読み、自力で解けるまで頑張ろう。
【方針】
この問題は2つ知っておかなければならない知識がある。
(1)全桁の足し算が3の倍数ならばもとの数も3の倍数
例：123は1+2+3=6で全桁の足し算が3の倍数→123も3の倍数。
証明は少し難しいが時間をかければ理解できると思う。興味がある人は下記リンク先を確認してほしい。ただし証明まで知らなくても問題は解ける。
https://mathwords.net/3nobaisu
これを踏まえてこの問題の条件を言い換える。
「3の倍数を作るために必要な最少の消す桁数」
=「全桁の足し算が3の倍数になるように必要な最少の消す桁数」
(2)余りの計算は足し算と引き算ができる
例として1+5+9を3で割った余り、つまり(1+5+9)%3がいくらかを考える。
1+5+9=15で、15%3=0。
つまり1+5+9=15を3で割った余りは0。
これを余りの足し算として考えてみると
1%3=1
5%3=2
9%3=0
なので
1+5+9→1+2+0=3
さらに
3%3=0
これは足し算をしてから計算した結果(15%3=0)と一致している。
もう一つ例を出そう。
1+14+25+34を3で割った余り、つまり(1+14+25+34)%3がいくらかを考える。
1+14+25+34=74で、74%3=2。
つまり1+14+25+34=74を3で割った余りは2。
これを余りの足し算として考えてみると
1%3=1
14%3=2
25%3=1
34%3=1
なので
1+14+25+34→1+2+1+1=5
さらに
5%3=2
足し算をしてから計算した結果(74%3=2)と一致している。
同様に余りは引き算、掛け算もできる
ただし、割り算はできない。(詳しくは「45 余りの除算」参照)
なぜこのように計算できるのか、理由については以下リンクの動画がわかりやすいので興味があれば見てほしい。ただし理由を理解していなくても問題は解ける。
https://www.youtube.com/watch?v=6COGmURbrAw
(1)全桁の足し算が3の倍数ならばもとの数も3の倍数
(2)余りの計算は足し算と引き算ができる
ということがわかった。
次に「どの桁をいくつ消せばよいか？」を考える。
結論から言うと桁を最大2つ消せば必ず3の倍数を作ることができる。
ここからの説明は読むだけだとわけがわからなくなる。必ず紙とペンを用意し、自分で書いて整理しながら読んでほしい。
まずNについて、
「Nを3で割った余り」
で分類する。
「Nを3で割った余り」が「0の場合」
例：N=369→3+6+9→0+0+0→0
これはなにも消さなくて良い。答えは0。
「Nを3で割った余り」が「1の場合」
例：N=8521→8+5+2+1→2+2+2+1→7→1
この場合「余りが1の桁」が存在するか、しないかで更に分類する。
・「余り１となる桁」が存在する場合
「余り1となる桁」を1つ消せば、残りの桁を足した数は余り0になる。
例：N=8521
N=8521→8+5+2+1→2+2+2+1→7→1
1を消した場合=852
852→2+2+2→6→0
ただしNが１桁しかなければ消せない。この場合は不可能。(例：N=4)
・「余り1となる桁」が存在しない場合
例：N=3625→3+6+2+5→0+0+2+2→4→1
この場合「余り2となる桁」が少なくとも2つ存在する。
理由を背理法で説明する。
(1)「「余り2となる桁」が存在しない」場合
これは「余り0の桁のみ存在する」ということ。その場合もとの数も余りが0となるので「Nを3で割った余り」が「1の場合」という条件と矛盾する。
(2)「「余り2となる桁」が1つしか存在しない」場合
これは「余り2の桁が1つ」そしてそれ以外全て「余り0の桁」ということ。その場合もとの数の余りも2となるため「Nを3で割った余り」が「1の場合」という条件と矛盾する。
故に「余り2となる桁」は少なくとも2つ存在する。
「余り2となる桁」を2つ消せば、残りの桁を足した数は余り0になる。
例：N=3625
3625→3+6+2+5→0+0+2+2→4→1
2と5を消した場合
36→3+6→0+0→0
ただしNが2桁以下ならば消せない。この場合は不可能。(例：N=25)
「Nを3で割った余り」が「2の場合」
例：N=335→3+3+5→0+0+2→2
この場合「余りが2の桁」が存在するか、しないかで更に分類する。
・「余り2となる桁」が存在する場合
「余り2となる桁」を1つ消せば、残りの桁を足した数は余り0になる。
例えば335の場合、最後の5は3で割った余りが2なので、それを消せば良い。
例：N=335
335→3+3+5→0+0+2→2
5を消した場合=33
33→3+3→0+0→0
ただし１桁しかなければ消せない。この場合は不可能。(例：N=5)
・「余り2となる桁」が存在しない場合
この場合「余り1となる桁」が少なくとも2つ存在する。
理由を背理法で説明する。
(1)「「余り1となる桁」が存在しない」場合
これは「余り0の桁のみ存在する」ということ。その場合もとの数も余りが0となるので「Nを3で割った余り」が「2の場合」という条件と矛盾する。
(2)「「余り1となる桁」が1つしか存在しない」場合
これは「余り1の桁が1つ」そしてそれ以外全て「余り0の桁」ということ。その場合もとの数の余りも1となるため「Nを3で割った余り」が「2の場合」という条件と矛盾する。
故に「余り1となる桁」は少なくとも2つ存在する。
「余り1となる桁」を2つ消せば、残りの桁を足した数は余り0になる。
例えば3794の場合、7と4の桁を消せば3の倍数となる。
例：N=3794
3794→3+7+9+4→0+1+0+1→2
7と4を消した場合=39
39→3+9→0+0→0
ただし2桁以下ならば消せない。この場合は不可能。(例：N=74)
以上、長々と書いているがこれを一つ一つif文になおして判定する。
「Nを3で割った余り」が
余りが0
答え：0
余りが1
余りが1の桁がある
Nは1桁以下
答え：-1(不可能)
Nは2桁以上
答え：1
余りが1の桁がない
Nは2桁以下
答え：-1(不可能)
Nは3桁以上
答え：2
余りが2
余りが2の桁がある
Nは1桁以下
答え：-1(不可能)
Nは2桁以上
答え：1
余りが2の桁がない
Nは2桁以下
答え：-1(不可能)
Nは3桁以上
答え：2
【実装】
入力を受け取る。
N=int(input())
amari1=「余り1となる桁」が存在するかを管理する変数
amari2=「余り2となる桁」が存在するかを管理する変数
amari_all=「Nを3で割った余り」を格納する変数
を用意する。
amari1=False
amari2=False
amari_all=N%3
amari1というのが「余り1となる桁」が存在するかを表す変数。あればTrue、なければFalse。
amari2というのが「余り2となる桁」が存在するかを表す変数。あればTrue、なければFalse。
次に
「余り1となる桁」が存在するか
「余り2となる桁」が存在するか
を以下の手順で確認する。
(1)Nを文字列に変換
(2)Nを1桁ずつ(1文字ずつ)取り出す
(3)取り出した桁を3で割った余りを確認
N=str(N)
for i in range(len(N)):
keta_num=N[i]
keta_num=int(keta_num)
if keta_num%3==1:
amari1=True
elif keta_num%3==2:
amari2=True
keta_numというのは桁numberの意味。取り出した桁は文字列なのでint(keta_num)で整数に変換し、3で割った余りを確認している。
あとは長々と書いた条件分岐を実装するだけ。もう一度条件を確認し、それを見ながらコードに起こそう。Nの桁数はlen(N)で確認できる。
if amari_all==0:
print(0)
elif amari_all==1:
if amari1==True:
if len(N)<=1:
print(-1)
else:
print(1)
else:
if len(N)<=2:
print(-1)
else:
print(2)
elif amari_all==2:
if amari2==True:
if len(N)<=1:
print(-1)
else:
print(1)
else:
if len(N)<=2:
print(-1)
else:
print(2)
【コード全文】
N=int(input())
amari1=False
amari2=False
amari_all=N%3
N=str(N)
for i in range(len(N)):
keta_num=N[i]
keta_num=int(keta_num)
if keta_num%3==1:
amari1=True
elif keta_num%3==2:
amari2=True
if amari_all==0:
print(0)
elif amari_all==1:
if amari1==True:
if len(N)<=1:
print(-1)
else:
print(1)
else:
if len(N)<=2:
print(-1)
else:
print(2)
elif amari_all==2:
if amari2==True:
if len(N)<=1:
print(-1)
else:
print(1)
else:
if len(N)<=2:
print(-1)
else:
print(2)
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/d4aba1192a81cf736eae
次：https://qiita.com/sano192/items/677ec26921f08586dd18