ABC171の参加記録です。反省記です。
結果を先に書くと、AB2完のパフォーマンス213。。。
C問題が曲者でした。
本記事では、前回同様に、初心者が初心者の誰かの役に立つかもしれないし、役に立たないかもしれない感じのチラ裏記事です。
Python3でのACコードとC問題を自分が理解するために書いたメモを書いています。
A – αlphabet
入力された文字が大文字か小文字かを判定する問題。
私は、大文字に変換した文字が入力と一緒なら大文字と判定しました。
alpha=input()
if alpha==alpha.upper():
print('A')
else:
print('a')
文字列の大文字、小文字の変換については、Udemyの講座でも受講していたのが頭に残っていたけど、自信がなかったので、[Python 大文字へ変換」でググって調べて回答しました。
B – Mix Juice
配列をソートして、ちょっと加工して配列の合計を求める問題。
N,K=map(int,input().split())
p=list(map(int,input().split()))
l=sorted(p)[:K]
print(sum(l))
C – One Quadrillion and One Dalmatians
今回のコンテストで泥沼にはまった問題。
一見アルファベットを使用した26進法のように見えて、簡単そうに見えるのですが、なかなか曲者で、コンテスト中に解けずに、月曜日の夕方頃にようやく理解できました。
原因は、aが対応するのは、1であり、0ではない。というところですね。
私が理解したのは以下のような手順です。
10進数で使用する文字のリストを
Decimal=[‘0′,’1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’]
とした時は、最初のindexの文字は0になっています。これは、普通の10進数です。
10進数で使用する文字のリストを以下とした場合はおかしなことが起こります。(以下、おかしな10進数という)
curious_decimal=[‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’t’]
最初のindexの文字を1にして、10をt(tenの1文字目)としています。
10は、10で割った時に商が1、余りは0です。余りのindex:0は、’1’です。
先ほど求めた商の1を10で割った時の商は0で余りは1なので、余りのindex:1は’2’です。
商が0になったため、ここで計算は終了です。
上記より、答えは21と出てきます。本来出てきてほしい文字は「t」であるにもかかわらず、おかしな数字になってしまいました。
これは、取り扱う数字と使用するリストの数字の周期とのずれが原因です。
使用する数字をずれた分だけ補正すれば正しく動きます。ずれが補正できるのは入力される数字が1以上の場合のみです。これで、0が入力されると、0に対応する文字がないためエラーになります。
今回の26進数で使用する文字列のリストを
Dalmatian=[‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’]
とした時も、初めのindexの文字はaであり、これが1匹目です。
これも、おかしな10進数と同じように、各桁の文字を求めるときに周期を判定する数字を補正すればうまくいきます。
リストの最後にappendしている場合は、リストを逆にする必要があります。
私は各桁の文字をinsertで一番左に持ってきたので、そのままリストの文字を結合して終了です。
N=int(input())
a=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
name=[]
for i in range (20):
N=N-1
name.insert(0,a[N%26])
N=N//26
if N==0:
break
print(''.join(name))
Appendix ~おまけ~
私が理解するのに使用したおかしな10進数を含んだコードです。
- 今回の問題のケース
- 普通の10進数
- おかしな10進数
上記の並びでそれぞれ計算しています。
1行目の変数をいろいろ変更するとどうなるかが見えると思います。(見えないかもしれません。)
Number = 702
Dalmatian=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
Decimal=['0','1','2','3','4','5','6','7','8','9']
curious_decimal=['1','2','3','4','5','6','7','8','9','t']
n1=Number
n2=Number
n3=Number
name1=[]
name2=[]
name3=[]
for i in range(20):
x=n1-1
name1.insert(0,Dalmatian[x%len(Dalmatian)])
n1=x//len(Dalmatian)
if n1==0:
break
for i in range(20):
y=n2+1-1
name2.insert(0,Decimal[y%len(Decimal)])
n2=y//len(Decimal)
if n2==0:
break
for i in range(20):
z=n3-1
name3.insert(0,curious_decimal[z%len(curious_decimal)])
n3=z//len(curious_decimal)
if n3==0:
break
print(''.join(name1))
print(''.join(name2))
print(''.join(name3))
コメント