先週に引き続き、今週は仕事が忙しかったのと、JavaScript、設計の勉強をしていて、あまり競プロの精進に時間を取れませんでしたが、ABC級のコンテストということでHKKBプログラミングコンテスト2020に参加しました。
ACL Beginner ContestやARC(AtCoder Regular Contest)104も参加して、そこそこ競プロは継続して楽しんでいます。
毎度、ABC級のコンテストでC問題が解けるか解けないか位のレベルの私が書くチラ裏ブログですが、Python3によるA-C問題のACコードを掲載しています。
A – Keyboard
標準入出力とif文の問題。str型のメソッドの一つであるstr.upper()メソッドを使うと楽な問題。
標準入力で文字を二つ受け取り、一つ目の受け取った文字が”Y”であれば、二つ目に受け取った文字を大文字に変換して標準出力(print)すればOKです。
二つ目の文字の種類が3種類しかないので、各文字の大文字の対応表を作ることもできますが、Python3には便利な文字列(str)型で使用できる便利なメソッドがあるので、それを使うのが楽だと思います。
# HHKB プログラミングコンテスト 2020
# A - Keyboard
S=input()
T=input()
if S=="Y":
print(str.upper(T))
else:
print(T)B – Futon
2次元配列の操作を問われる問題。
ABC級のコンテストのB問題で図面の問題が出てきて焦りました。
これ系の問題は苦手意識があるのですよね。
解き方としては、
・同一の行で二つ連続した”.”が存在すること。…①
・同一の列で二つ連続した”.”が存在すること。…②
これらを二次元配列で判定し、判定結果がtrueの場合はansを+1してansを出力すればOKです。
私はこういうタイプの問題でfor文で、よく配列外参照を出してしまいます。
この配列外参照の回避策として、受け取る図面の外枠(または右と下の辺)に”#”を追加したものを用意して、回数に気を付ける。という形で対策しています。
例
↓これを受け取ったら
.#.#
#..#
↓こうやって保持する
######
#.#.##
##..##
######これが悪手かどうかの判定はできていませんが、配列外参照の数は激減しました。
あとは上記①と②の条件を左上から判定していけばOKです。
# HHKB プログラミングコンテスト 2020
# B - Futon
H,W=map(int,input().split())
S=[]
s="#"*(W+2)
S.append(s)
for _ in range (H):
s=input()
s="#"+s+"#"
S.append(s)
s="#"*(W+2)
S.append(s)
ans=0
for i in range (1,H+1):
for j in range (1,W+1):
if S[i][j]=="." and S[i][j+1]==".":
ans+=1
else:
pass
if S[i][j]=="." and S[i+1][j]==".":
ans+=1
else:
pass
print(ans)C – Neq Min
判定する値と最小値の保持、最小値の更新を効率よく探すことを求められる問題。
考えたこと
出現した数値を別のリストで管理して、毎回そのリストからまだ使われていない数字をindex(0)で探して出力すればOKかな。
はいTLE！
index(0)は線形探索で、毎回探すため、計算量はO(N**2)になります。
もう少し考えたこと
①使える最小値は0が初期値。
②使える最小値が配列に出現するまでは、それが答え。
③使える最小値が出現した場合は、今までの出現した数字を除く最小値を探しに行く。
使える最小値は使いまわせることに気づき、使える最小値が使えない場合に、使える最小値を更新すればOKと考えました。使える最小値を更新するためには、やはりindex(0)です。
はい！TLE！
これは、入力のPが
0 1 2 3 4 5 6 7 8 9 10 11 ....といった場合に、使える最小値を毎回更新する必要があり、結局index(0)で探すのは、線形探索のため、計算量はO(N**2)になります。
さらに考えたこと
使える最小値が、今使っているものよりも小さくなることはないために、新しく使える最小値を探しに行くのに配列の0番目から探索することが改善できれば良さそうなことまではわかりました。
そこで、listの操作についてググって、index()メソッドは、追加の引数に開始位置を入れることができる事がわかったので、開始位置に現在の使える最小値を追加して線形探索の計算量を減らして提出したらACしました。
図で考えるとこんな感じです。
# HHKB プログラミングコンテスト 2020
# C - Neq Min
N=int(input())
Pls=list(map(int,input().split()))
mini=0
ansls=[0]*200003
for i in range(N):
if Pls[i] > mini:
ansls[Pls[i]]+=1
print(mini)
else:
ansls[Pls[i]]+=1
mini=ansls.index(0,mini)
print(mini)
コメント