自己紹介
AtCoderで日々奮闘している、中学生のwhile-true-ifです。今日はQiitaに初めて、記事を投稿します。
ちなみに自分は茶コーダー(2024/3/11時点)です。
この記事の対象者
- AtCoderでヘンなことしてみたい人
- AtCoderでレートを上げるための手段を選ばない人
逆にきれいなコードを書くことを自分のモットーとしている人にはおすすめしません。
ABC333 C問題
問題
十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると 1,11,111,… です。
ちょうど 3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。
経緯
競技時間中に、同じ茶Coderの友達がその問題をACしたのを順位表で見て、「自分も解かなきゃ」と焦ってしまったことが原因です。そこで、制約を見て、Nの最大値が333なら、すべて手作業で列挙すればいけるんじゃないかと思い、やってしまいました。解くのにかかった時間は、約50分です。
提出したコード
a=[3, 13, 23, 33, 113, 123, 133, 223, 233, 333, 1113, 1123, 1133, 1223, 1233, 1333, 2223, 2233, 2333, 3333, 11113,
11123, 11133, 11223, 11233, 11333, 12223, 12233, 12333, 13333, 22223, 22233, 22333, 23333, 33333, 111113, 111123,
111133, 111223, 111233, 111333, 112223, 112233, 112333, 113333, 122223, 122233, 122333, 123333,133333,
1+111111+111111,11+111111+111111,111+111111+111111,1111+111111+111111,11111+111111+111111,111111+111111+111111,
1111113, 1111123, 1111133, 1111223, 1111233, 1111333, 1112223, 1112233, 1112333, 1113333, 1122223, 1122233,
1122333, 1123333, 1133333, 1222223, 1222233, 1222333,1223333,1233333,1333333,2222223,2222233,2222333,2223333,2233333,2333333,3333333,
11111113, 11111123, 11111133, 11111223, 11111233, 11111333, 11112223, 11112233, 11112333, 11113333, 11122223, 11122233, 11122333,
11123333, 11133333, 11222223, 11222233, 11222333, 11223333, 11233333, 11333333, 12222223, 12222233, 12222333, 12223333,
12233333, 12333333, 13333333,22222223,22222233,22222333,22223333,22233333,22333333,23333333,33333333,
111111113, 111111123, 111111133, 111111223, 111111233, 111111333, 111112223, 111112233, 111112333,
111113333, 111122223, 111122233, 111122333, 111123333, 111133333, 111222223, 111222233, 111222333, 111223333,
111233333, 111333333, 112222223, 112222233, 112222333, 112223333, 112233333, 112333333, 113333333, 122222223,
122222233, 122222333, 122223333, 122233333, 122333333, 123333333, 133333333,222222223,222222233,222222333,222223333,222233333,
222333333, 223333333, 233333333, 333333333,
1111111113, 1111111123, 1111111133, 1111111223, 1111111233, 1111111333, 1111112223, 1111112233, 1111112333,
1111113333, 1111122223, 1111122233, 1111122333, 1111123333, 1111133333, 1111222223, 1111222233, 1111222333,
1111223333, 1111233333, 1111333333, 1112222223, 1112222233, 1112222333, 1112223333, 1112233333, 1112333333,
1113333333, 1122222223, 1122222233, 1122222333, 1122223333, 1122233333, 1122333333, 1123333333, 1133333333,
1222222223, 1222222233, 1222222333, 1222223333, 1222233333, 1222333333, 1223333333, 1233333333, 1333333333,
2222222223, 2222222233, 2222222333, 2222223333, 2222233333, 2222333333, 2223333333, 2233333333, 2333333333,
3333333333,
11111111113, 11111111123, 11111111133, 11111111223, 11111111233, 11111111333, 11111112223, 11111112233,
11111112333, 11111113333, 11111122223, 11111122233, 11111122333, 11111123333, 11111133333, 11111222223,
11111222233, 11111222333, 11111223333, 11111233333, 11111333333, 11112222223, 11112222233, 11112222333,
11112223333, 11112233333, 11112333333, 11113333333, 11122222223, 11122222233, 11122222333, 11122223333,
11122233333, 11122333333, 11123333333, 11133333333, 11222222223, 11222222233, 11222222333, 11222223333,
11222233333, 11222333333, 11223333333, 11233333333, 11333333333, 12222222223, 12222222233, 12222222333,
12222223333, 12222233333, 12222333333, 12223333333, 12233333333, 12333333333, 13333333333,
22222222223, 22222222233, 22222222333, 22222223333, 22222233333, 22222333333, 22223333333, 22233333333,
22333333333, 23333333333, 33333333333,
111111111113, 111111111123, 111111111133, 111111111223, 111111111233, 111111111333, 111111112223,
111111112233, 111111112333, 111111113333, 111111122223, 111111122233, 111111122333, 111111123333,
111111133333, 111111222223, 111111222233, 111111222333, 111111223333, 111111233333, 111111333333,
111112222223, 111112222233, 111112222333, 111112223333, 111112233333, 111112333333, 111113333333,
111122222223, 111122222233, 111122222333, 111122223333, 111122233333, 111122333333, 111123333333,
111133333333, 111222222223, 111222222233, 111222222333, 111222223333, 111222233333, 111222333333,
111223333333, 111233333333, 111333333333, 112222222223, 112222222233, 112222222333, 112222223333,
112222233333, 112222333333, 112223333333, 112233333333, 112333333333, 113333333333, 122222222223,
122222222233, 122222222333, 122222223333, 122222233333, 122222333333, 122223333333, 122233333333,
122333333333, 123333333333, 133333333333, 222222222223, 222222222233, 222222222333, 222222223333,
222222233333, 222222333333, 222223333333, 222233333333, 222333333333, 223333333333, 233333333333,
333333333333]
n=int(input())
print(a[n-1])
自分で書きましたが何度見てもひどいですね(^^)
結果
なんと、11msという驚異的な時間でACすることに成功しました!!!
🎉🎉🎉🎉🎉🎉🎉🎉
(ちなみに、正攻法で解いた愚かな人たちは、実行時間が約60~70msでした(Pythonで解いた場合))
自分の暗算力に感謝します。
ABC058 C問題
問題
すぬけ君は、文字列の書かれた紙から文字をいくつか切り抜いて、並び替えて別の文字列を作るのが好きです。
明日になると、すぬけ君は文字列 S1 ,...,Sn のうちどれか 1 つが書かれた紙がもらえます。すぬけ君は文字列を作る事をとても楽しみにしているので、どんな文字列を作るか計画を立てることにしました。ただし、すぬけ君はまだどの文字列が書かれた紙がもらえるかを知らないため、どの文字列が書かれていた場合にも作れる文字列を考えることにしました。
S1 ,...,Sn のどの文字列が書かれていても作れる文字列のうち、最長のものを求めてください。最長のものが複数ある場合は、辞書順で最小のものを求めてください。
(読みにくいので、実際のコンテストページを見てください)
経緯
お察しのとおり、過去問です。
過去問解いてるときに、茶色diffの問題をとけないのは屈辱なので、意地でも解いてやろうと思いました。
提出したコード
nn=int(input())
a,b,c,d,e,f,g,h,ii,jj,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z=[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn,[0]*nn
for i in range(nn):
ss=list(input())
for j in range(len(ss)):
if ss[j]=='a':
a[i]+=1
elif ss[j]=='b':
b[i]+=1
elif ss[j]=='c':
c[i]+=1
elif ss[j]=='d':
d[i]+=1
elif ss[j]=='e':
e[i]+=1
elif ss[j]=='f':
f[i]+=1
elif ss[j]=='g':
g[i]+=1
elif ss[j]=='h':
h[i]+=1
elif ss[j]=='i':
ii[i]+=1
elif ss[j]=='j':
jj[i]+=1
elif ss[j]=='k':
k[i]+=1
elif ss[j]=='l':
l[i]+=1
elif ss[j]=='m':
m[i]+=1
elif ss[j]=='n':
n[i]+=1
elif ss[j]=='o':
o[i]+=1
elif ss[j]=='p':
p[i]+=1
elif ss[j]=='q':
q[i]+=1
elif ss[j]=='r':
r[i]+=1
elif ss[j]=='s':
s[i]+=1
elif ss[j]=='t':
t[i]+=1
elif ss[j]=='u':
u[i]+=1
elif ss[j]=='v':
v[i]+=1
elif ss[j]=='w':
w[i]+=1
elif ss[j]=='x':
x[i]+=1
elif ss[j]=='y':
y[i]+=1
else:
z[i]+=1
a=min(a)
b=min(b)
c=min(c)
d=min(d)
e=min(e)
f=min(f)
g=min(g)
h=min(h)
i=min(ii)
j=min(jj)
k=min(k)
l=min(l)
m=min(m)
n=min(n)
o=min(o)
p=min(p)
q=min(q)
r=min(r)
s=min(s)
t=min(t)
u=min(u)
v=min(v)
w=min(w)
x=min(x)
y=min(y)
z=min(z)
print('a'*a+'b'*(b)+'c'*(c)+'d'*(d)+'e'*(e)+'f'*(f)+'g'*(g)+'h'*(h)+'i'*(i)+'j'*(j)+'k'*(k)+'l'*(l)+'m'*(m)+'n'*(n)+'o'*(o)+'p'*(p)+'q'*(q)+'r'*(r)+'s'*(s)+'t'*(t)+'u'*(u)+'v'*(v)+'w'*(w)+'x'*(x)+'y'*(y)+'z'*(z))
結果
なんと、12msという驚異的な時間でACすることに成功しました!!!
🎉🎉🎉🎉🎉🎉🎉🎉
(ちなみに、正攻法で解いた優秀な人たちは、実行時間が約10~15msでした(CPythonで解いた場合))
↑↑↑実行時間変わんなかった...(´;ω;｀)
まとめ
AtCoderでは制約が小さければ、このようなコードでもACすることができます。みなさんも解法が思いつかないピンチな時にやってみてはいかがでしょうか？