ABC306

今回も参加できたので反省会します。
サーバー大変なことになってましたね。。。
今回はABC306( https://atcoder.jp/contests/abc306 )

A

一文字ずつ、繰り返していく処理。
一行で記述するため、print文のendを忘れずに。

N = int(input())
S = input()
for s in S:
  print(s+s,end="")

B

64桁の2進数を10進数表記に変換。
それぞれのbitを条件文で処理。
pythonだとオーバーフローをあまり気にしない部分はいい点(たまにC++などを触るとオーバーフローに対する処理を忘れているのが悪い点)。

A = list(map(int, input().split()))
a = 1
ans = 0
for i in A:
  if i == 1:
    ans += a
  a = a*2
print(ans)

C

1,2,…,Nの数字が3つずつ含まれる配列から、2番目に出てくる位置が早い順に表記する。それぞれの数字が何回目かをカウントする配列と、答え用の配列を用意し、与えられた配列をすべて検索する。出現した数字に応じてカウントを変化させ、2回目に出た場合、答えの配列に追加していく。数字ごとに順番を抽出することも考えたが、計算量がO(3N^2)くらいになりそうだったので、O(3N)の上記の方法で実行。

N = int(input())
l = list(map(int, input().split()))
c_l = [0]
ans = []
for i in range(N):
  c_l.append(0)
for i in l:
  if c_l[i] == 1:
    ans.append(i)
  c_l[i] += 1
for i in ans:
  print(i, end=" ")

5,6行目は省略して、普通にC_l = [0]*(N+1)とかでよかったなと反省。

D

毒で死なないように、おいしさを最高の値で出す問題。ABC303のD問題と同様の形式のDPで解けた。それぞれの料理に対して、食べる前の時点の高橋君の状態とおいしさの値をもとに次状態の値を変更していく。

N = int(input())
s_1 = 0
s_0 = 0
for i in range(N):
  x, y = map(int, input().split())
  if x == 1:    #毒入り
    if s_1 < s_0 + y:
      s_1 = s_0 + y
  else:         #解毒剤入り
    if s_0 < s_0 + y:
      s_0 = s_0 + y
    if s_0 < s_1 + y:
      s_0 = s_1 + y
  
print(max(s_1, s_0))

s_1が腹痛状態のおいしさ最高スコア、s_0が健康状態の最高スコア。料理が毒入りかを判定し、毒入りならばs_0からの遷移のみを考える。毒入りのためs_1への遷移となるが、ここでそれまでのs_1と、今回の遷移によるスコアを比較、更新する。解毒剤入りでは、s_0への遷移として同様に考える。ただ、s_0、s_1のどちらかの遷移も考えられるため、それぞれ比較する必要がある。スコアは0以下の場合も考えられるため、s_0、s_1それぞれに対し条件文を用意し更新した。
スコアを配列Sなどにすることで、S[0]やS[1]のように用いて簡略化もできそう。でも、結果毒入りか解毒剤入りかで分岐するのであんまり変わらなさそう。
else文は以下のように書けば一つで行けそう。

else:
    if s_0 < max(s_0, s_1) + y:
        s_0 = max(s_0, s_1) + y

反省・感想

今回は久々に時間内にDまで回答できました。とくにDは、ABC303の形式と似た形のDPで解くことができ、さっそく反省会をしている効果を感じられました。
Eにも取り組みましたが、TLEになってしまいました。解説見てもあまりピンと来ていませんが、時間があるときに考えてみたいと思います。
終盤コードテストが全くできませんでしたので、とりあえずunrateにならないことを祈ります。我々は何もできず申し訳ないですが、対応頑張っていただきたいですね。

現在レート:728 →　????