こんばんは。寝ても寝ても眠いとーです。
ARC092C
N個の座標が与えられて、xy座標の大きいものと小さいものをペアにしていきましょうという問題
想定解が頭良すぎた 自分で最初考えていてのは、xの小さい順にソートしてそれをxの小さい方から覆っていくようにとっていけばよいって方針だったけど、xの小さい順にソート→それで覆えるものでy座標が大きいものをとっていった方が省エネになる
なんか別の解き方もあるみたいなので、それはまたの機会に
EDPC F
最長共通部分列（LCS:Longest Common Subsequence）の問題
例えば、
abcd と becd の最長の共通部分列は bcd となる
長さが欲しいならば、dpを使って、（s,tは文字列）
s = input() t = input() dp = [] for i in range(len(s)+1): #s+1行、t+1列のリストを作る L = [0]*(len(t)+1) dp.append(L) for i in range(len(s)): for j in range(len(t)): if s[i] == t[j]: #sのi文字目とtのj文字目が一致していたら dp[i+1][j+1] = dp[i][j]+1 #リストのi+1行j+1列を、i行j列＋1に変更 else: dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]) #dp[i+1][j+1]はdp[i+1][j],dp[i][j+1]の長い方に変更
とすればよい
今回は部分列の長さではなく部分列自体を出力してほしいと言っているが、これをdpで愚直に文字列を形成していくやり方でやるとしんどい
ので、文字列を逆順に追っていき、作った文字列の前に文字を追加することを考える
文字を追加するタイミングは、dp[i+1][j+1]の数字が1減ったときである
これは、現在見ているs,tの文字をn,m番目として、
dp[n][m] == dp[n-1][m]であれば、sを一文字前にずらしても文字列（の長さ）は変わらない→LCS自体に変化はない
dp[n][m] == dp[n][m-1]であれば、tを（略
それ以外→dp[n][m] == dp[n-1][m-1]+1で、ここでLCSは増える（このタイミングで文字列を増やせばよい）
ということからわかる
↑こちらの記事を参考にさせていただきました ありがとうございました
SoundHound Inc. Programming Contest 2018 C
1~nまでの数字を重複を許してm個並べたとき、隣接する数字の絶対値がdになる部分の数の期待値を出す問題
シミュレーションで期待値が出せない以上何かしらの計算で出せるようになっているはず
隣り合う数字の差が0になるペアは(1,1)~(n,n)のn通りで、確率は1/n
差がdになるペアは(1,d+1)~(n-d,n)の(n-d)通りと、これをひっくり返した奴の計2*(n-d)通りなので、確率は2*(n-d)/(n**2)
よって、隣り合う数字の差がdになる確率が分かったため、期待値の線形性（この場合で言えば、期待値は(隣り合う数の差がdになる確率)*(m-1箇所）で求められる）からすぐに答えが分かる
同じような問題で、
[例]
確率1/2で0か1を表示する電光掲示板を8つ並べる。'111'と表示される箇所の数の期待値は？（1111は2つとしてカウントされる）
という問題は、'111'と連続する確率が1/8で、3つ並ぶところは6箇所あるので、6*1/8=3/4と求められる 簡単だね
