けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

逆順列を考える

Codeforces 552 DIV3 E. Two Teams (R1800)

超苦手タイプ 問題へのリンク 問題概要 要素からなる順列があたえられる。先手と後手が交互に 残っている中から最大要素を選び、その左右 要素を合わせて 要素を、自分のところに抜き取ってくる (左右に 要素残っていない場合はある分だけ抜き取ってくる) と…

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…

AtCoder AGC 005 B - Minimum Sum (400 点)

教育的な典型問題! 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…

AOJ 2931 括弧を語る数 (RUPC 2019 day3-B)

こういうのを頭混乱させずにきっちり素早く解ける人が、強い人なんだと思う。強くなりたい!!!!!! ということで教育的な楽しい問題!!! 問題へのリンク 問題概要 整合するカッコ列 があって、 から以下のように定義される長さ の順列 が与えれる: i …