ml_begin’s blog

Python初心者が、機械学習、画像認識、Web解析について取り組んでいきます。

AtCoder(競プロ)〜1日1問【4日目】

f:id:ml_begin:20180604073123j:plain

デバッグに時間がかかりまくると1日1問すら困難ということに気がつきました。
ある程度制限時間設けて、人の解答の理解も含めて1時間で終わらせようと思います(次回から)。

ということで本日は、この問題をやってみました。
abc098.contest.atcoder.jp
問題としては、

「東西方向に東と西どちらかに向いて並んでいるグループがある。
その中でリーダーを決めた場合、リーダー以外はリーダーの方向に向かなければならない。
他の人たちは、できるだけ向いている方向は変えたくない。
向いている方向を変える人数が最も少ないときの数を求めよ」

というものです。

というわけで私の書いたコードはこちら

N,S = int(input()),input()

leaderArrayNum = 0
minDireChangeNum = 3*10**5

#一人ずつリーダーにしていく
while leaderArrayNum < N:
	
 print("leader is {}".format(leaderArrayNum))
 #向きを変更する人数
 direChangeNum = 0

 #リーダーの方へ向くために向きを変更する人数の調査
 compareArrayNum = 0

 while compareArrayNum < N:
  compareMan = S[ compareArrayNum ]
  #リーダーに対して左側にいる
  if compareArrayNum < leaderArrayNum:
   direChangeNum += 1 if compareMan == "W" else 0  
   print("dire_change!{} has to turn east!".format(compareArrayNum)) if compareMan == "W" else False
   #リーダーに対して右側にいる
  elif leaderArrayNum < compareArrayNum:
   direChangeNum += 1 if compareMan == "E" else 0
   print("dire_change!{} has to turn west!".format(compareArrayNum)) if compareMan == "E" else False
   #リーダーである
  elif compareArrayNum == leaderArrayNum:
   compareArrayNum += 1
   continue
  else:
   print("error")
   
  compareArrayNum += 1		
 #向きを変える人数が最小であれば変更
 minDireChangeNum = direChangeNum if direChangeNum < minDireChangeNum else minDireChangeNum 
 leaderArrayNum += 1
print( minDireChangeNum )

冗長感漂うコード。。
案の定、結果はこちら
f:id:ml_begin:20180604051913p:plain
テストケース、5問目以降はタイムアウト(Time Limit Exceeded)。

そこで他の人のコードを確認。

n = int(input())
s = input()
l = []
count = s[1:].count('E')
r = count
for i in range(n-1):
  if s[i] == 'W':
    count += 1
  if s[i + 1] == 'E':
    count -= 1
    if count < r:
      r = count
print(r)

シンプル!

count = s[1:].count('E')]

文字配列の1番目以降の「東」の数をカウント。
countで記憶。

for i in range(n-1)

range()の使い方は、range(最後の値)で、範囲:0〜最後の値-1 です。
n - 1 の範囲なのは、最後の配列の確認の時、
i + 1 をすると存在しない配列番号を参照することになるからです。

  if s[i] == 'W':
    count += 1
  if s[i + 1] == 'E':
    count -= 1
    if count < r:
      r = count

f:id:ml_begin:20180604072911p:plain

次回精進。