torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

辞書順最小

Good Bye 2014, B : New Year Permutation

問題文 http://codeforces.com/contest/500/problem/B 問題概要 サイズ の順列 及び, 行列 が与えられる.また, 及び が成り立つ. 二つの整数 について, であるときに限り, と を交換することができる.任意回の操作で作ることができる列の内,辞書式順…

Google Code Jam 2014, Round 1B, C : The Bored Traveling Salesman

問題文 http://code.google.com/codejam/contest/2994486/dashboard#s=p2 問題概要 N 個の街があって、それぞれの街は固有の郵便番号をもっている。また、いくつかの街の間は空路で結ばれていてる。 全ての街を訪れることができるように飛行機を予約したいが…

TopCoder Open, Algorithm、Round 1A, Level 2 : EllysScrabble

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12974&rd=15942 問題概要 文字列 letters と整数 maxDistance が与えられる。letters の各文字について、元の位置との距離が maxDistance を超えない範囲で、letters を並べ替えることが…

Codeforces #177, Division 2, C : Polo the Penguin and Strings

問題文 http://codeforces.com/contest/289/problem/C 概要 次の条件を満たす文字列のうち、辞書順最小のものを出力せよ。 文字列は、n 文字の英小文字からなる ちょうど k 種類の文字を含む 隣り合う文字同士は全て相異なる そのような文字列が存在しない場…

AOJ 2423 : Code Art Online

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2423

TopCoder SRM 563, Division 1, Level 1 : FoxAndHandle

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12331&rd=15185 概要 二つの文字列 X, Y を先頭からマージしたものを Z とする。 既にマージされた文字列 S が与えられる。 X は S の部分列、Y は X を並び替えたものであるとする。 X …

TopCoder SRM 545, Div1-L1/Div2-L2 : StrIIRec

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12025&rd=14737 概要 文字列 S の"転倒数"を次のように定める。 i S[j] を満たす i, j の組の数 アルファベットの先頭 n 文字を組み合わせた文字列を考える。 次の二つの条件を満たす辞書…