J 各操作で左崎さんは，右男さんはを必ず1減らす 相手の値を減らせるなら減らすべきなので数列に0が存在しないときは[1,n]を選択するべき よって回[1,n]を選択する操作を繰り返す この操作をした後はお互いa_1とa_nを減らし合って先に0になった方が負けにな…

ABC はい E DP D 2SAT H UFマージテク G 期待値で式変形を頑張る I 係数がパスカルの三角形になってる FFTでやる J 行列を構築するやつ F よくわからん D x_i = (iを集合に入れるならtrue) とする XORについてのclosureを (not x_i) or (not x{i xor X}) と …

ABCDEJ → コンテスト中に解いた F: 凸関数 G: DP H: 2数の積の桁長 I: 誤差がやばい K: 畳み込み K 1次元につぶす https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day1/3873509 G 解説で素直なDPとなっているDPの一例を書く．A[i][j], B…

問題ページ 考えたこと dp[すぬけくんのコマの位置][りんごさんのコマの位置][手番] としたDPはできそう 明らかに状態が多すぎるので減らしたい コマが隣接して置かれていないとき，左のコマは右に隣接するまで一つずつずらすのが最適 dp[左のコマの位置][手…

問題ページ 解法 マージソートの過程をセグ木に保存する方法(蟻本 p171)と同じ要領で，各頂点にその区間に対応する「高い要素」の列を保存しておく．左の子と右の子の2つの列をmergeするときには，左の子の列はそのままで，右の子の列の要素のうち左の子の列…

問題ページ 解法 区間]により大きい要素しかないのであれば を計算すればよい．逆に以下の要素しかなければ0を出力するだけである．区間]の和，以下の要素の個数，以下の要素の和が求まればより大きい要素と以下の要素に場合分けしてそれぞれ計算すればよい…

問題ページ 解法 ペアとなっている2要素を区間として，区間が交差しない部分は独立に考えてよさそう．各区間でどのようなペアのとり方が存在するのか考えると以下のパターンしかない． (1) 1 (2) 2 3 … 3 2 (3) 3 1 (4) 3 3 3 2は(2)以外で使用できないので(…

コンテスト 東京工業大学プログラミングコンテスト2019 - AtCoder チームolphe_konaiphe(oshibori，tsutaj，ferin)で参加しました． B問題 部分文字列okyoのあとに部分文字列echが存在するかを判定すればいいことがわかったので書いてAC A問題 oshiboriさん…