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

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

逆順列を考える

AtCoder ABC 142 C - Go To School (300 点)

この問題で要求している処理を「前処理」として要求する問題はたくさんある!!! というわけで教育的な問題かもしれない。 問題へのリンク 問題概要 人の生徒がいて、出席番号 の生徒はそれぞれ、全体で 人目に登校していることがわかっている。 これらの情…

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 …