ABC167 WriteUp

#要約
ABは速攻で解けるのにCが一生解けない.後回しにしていた「DPが解けない」という弱点が如実に出てしまった...

今後緑~青目指していくなら今回のC問題は必ず解けるようにしておきたい.

そのためにも，AOJの組合せ最適化(https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1) をゴリゴリ解くぞ！！

A

高橋君はとあるWebサービスに会員登録しようとしています。まずIDを$S$として登録しようとしました。しかし、このIDは既に他のユーザーによって使用されていました。そこで、高橋君は$S$の末尾に1文字追加した文字列をIDとして登録することを考えました。高橋君は新しくIDを$T$として登録しようとしています。これが前述の条件を満たすか判定してください。

Tの末尾文字を削除したT[:-1]がSと一致するかをチェックすればよいです.
一応S="" T=""みたいなヤバ入力¹を通さないために文字数のチェックもします．

s = input()
t = input()
if len(s) + 1 == len(t) and s == t[:-1]:
  print("Yes")
else:
  print("No")

B

1が書かれたカードが$A$枚、0が書かれたカードが$B$枚、−1が書かれたカードが$C$枚あります。これらのカードから、ちょうど$K$枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最大値はいくつですか。

Kの値によって最大値には3つの場合があります．
1 . K<=Aの場合．

• 「1」のカードをK枚とってもおつりがくる,もったいない状態ですね.
• 最大値を取るのは，「1」カードをK枚取る場合で,最大値はKです.

2 . A<K<=A+Bの場合

• この場合，A枚の「1」カードをとっても，K-A枚取る義務があるため，その分は「0」カードか「-1」カードを取らなければいけません．幸い前提条件よりK-A<Bなので，残ったドローの義務についても「0」カードを引くことで最大値を減らすことなく点数繰りができます．
• 最大値を取るのは,「1」カードをA枚，「0」カードをK-A枚取る場合で,最大値はAです．

3 . A+B<Kの場合

• 「1」カードと「0」カードを取り尽くしてしまったので，とうとう「-1」カードに手を出さなければならなくなりました(秘境生活でギシギシを食べざるを得なくなったエド・スタフォードの気持ちですね)．²この場合，取らなければならない「-1」カードの枚数はK-(A+B)枚です.
  • 最大値を取るのは,「1」カードをA枚，「0」カードをB枚，「-1」カードをK-(A+B)枚取る場合で， 最大値はA-(K-(A+B))です.

高々3パターンの場合分けなので，愚直に実装していきましょう.

a,b,c,k=[int(i)for i in input().split()]
if k <= a:
  print(k)
elif k<=a + b:
  print(a)
else:
  print(a-(k-a-b))

##D

高橋王国には$N$個の町があります。町は$1$から$N$まで番号が振られています。それぞれの町にはテレポーターが1台ずつ設置されています。町$i(1≤i≤N)$のテレポーターの転送先は町$A_i$です。高橋王は正の整数$K$が好きです。わがままな高橋王は、町$1$から出発してテレポーターをちょうど$K$回使うと、どの町に到着するかが知りたいです。高橋王のために、これを求めるプログラムを作成してください。

(WA回答)

街をノード，テレポートを有向エッジと見ると,有向グラフが何となく見えてきますね．
そして，少し考えると，「ある程度テレポートを繰り返すと，最終的にはグラフ内の無限ループをぐ〜るぐるすることになるのでは？」「その部分はシミュレーションしなくていいな」という結論に至ります.
ということは，

• とりあえず愚直にテレポートを繰り返す. 探索済ノードはリストにappendして記録する.
• もしテレポート中に探索済ノードにブチ当たった場合，以降のテレポートは無限ループになるので，繰り返し部分はシミュレーションせずとも計算で求めることが出来る.
• 無限ループする前にK回達成したらそれはそれでよし.終了.
  という実装が考えられる...と思ったのですが，以下の回答だとTLEになるだけでなく，WAになってしまいます．

N,K=[int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#インデックスを1オリジンに
A.insert(0,-1)

accessed_node = set([1])
accessed_node_list=[1]
loop_root = []
loop_madeno_size = 0
loop_size=0
t=1
#ループ検出
for _ in range(1,K+1):
  if not A[t] in accessed_node:
    accessed_node.add(A[t])
    accessed_node_list.append(A[t])
    #次の場所を決める
    t=A[t]
  else:
    #ループ路を確定する
    loop_start_index=accessed_node_list.index(A[t])
    loop_root = accessed_node_list[loop_start_index:]
    loop_madeno_size = loop_start_index
    loop_size=len(loop_root)
    break
#print(accessed_node)
#print(loop_madeno_size)
if loop_madeno_size <= K:
  print(t)
  exit()
K -= loop_madeno_size
print(loop_root[K%loop_size])

ウーン...修行してから解き直したい．
あとこれ，PyPyだと若干早いパターンですね.

まとめ

フル回答はこちら : https://github.com/Nekomo/AtCoder/tree/master/ABC/167
来週までに組合せ最適化,DPいっぱい解くぞ〜！！

1. ヤバい入力． ↩

2. ルーマニア | ザ・秘境生活 https://youtu.be/NSwOF_A0LfM ↩