#要約
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=""みたいなヤバ入力1を通さないために文字数のチェックもします．
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」カードに手を出さなければならなくなりました(秘境生活でギシギシを食べざるを得なくなったエド・スタフォードの気持ちですね)．2この場合，取らなければならない「-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いっぱい解くぞ〜！！
-
ヤバい入力． ↩
-
ルーマニア | ザ・秘境生活 https://youtu.be/NSwOF_A0LfM ↩