Codeforces #401 A, B, C, D

A問題

問題概要

　3個の箱の中にボールを隠しました。規則にもとづいて箱の位置を交換します。移動させた回数が奇数のときは左と真ん中の箱、偶数のときは右と真ん中の箱を入れ替えます。移動させた回数と最後にボールがあった場所から最初にボールがあった位置を求めてください。箱の位置を左から0, 1, 2と表します。

解法

　ボールがどのように移動するのか実験してみます。

  0 1 2  0 1 2  0 1 2
0 o        o        o
1   o    o          o
2     o  o        o
3     o    o    o
4   o        o  o
5 o          o    o
6 o        o        o
7   o    o          o
8     o  o        o
9     o    o    o

　周期6で位置が変化しているため、移動させた回数nを6で割った余りからボールの初期位置を一意に求められます。

B問題

問題概要

　AくんとBくんはN桁の数字を持っています。二人はこの数字を使ってある勝負をします。左の桁から1桁ずつ数の大小を比べ、相手より小さければ負けになります。しかしBくんは勝ちたいので不正をし、決まった順序と違う順番で数を提示します。Bくんが負ける数を最も少なくしたときの負ける数、Aくんが負ける数を最も多くしたときのAくんが負ける数を示してください。

解法

　Aくんが出す数に対してBくんが出す数の適切な組み合わせさえ分かればいいため、AくんとBくんの持っている数の順番は関係ありません。
　まず、負ける数を最も少なくするときのことを考えます。Aくんが提示する数以上の数を出せば勝負に負けません。そこで、勝負に負けないギリギリの数を出し続けることを考えます。AくんとBくんが持っている数をそれぞれソートし、最も小さい勝負に負けない数を順番に決めていきます。n-(負けない数)とすることで最小の敗北数を求めることができます。
　次に、Aくんが負ける数を最も多くすることを考えます。同じ数では勝てないためAくんが出す数よりも大きい、最小の数を順に当てはめていくことで最大の勝利数を求められます。
　これらの貪欲法でO(N)で求められます。

C問題

問題概要

　n行m列（1<=n*m<=10^5）の表があります。この表の各マスには1つの整数(<=10^9)が書かれています。l行目からr行目(1<=l<=r<=n)が降順でない列が存在するかのクエリにk回(k<=10^5)答えてください。

解法

　dp[i] =（i行目から最も長く降順でない数列が続いている行）を求めておくことで各クエリに対しO(1)で答えることができます。各列について上から順に降順でない部分列が何行から何行にかけてあるのかを求めます。全てのマスについて1回ずつ探索するため計算量はO(n*m)です。

D問題

問題概要

　n個の文字列が与えられる。接尾字を消去することで文字列が降順に並ぶようにしたい。消去する文字数を最も少なくしたときの消去後の文字列を求めてください。

解法

　後ろから順番に降順になるような最も消去する文字数が少ない消し方をすることで求めることができます。n番目の文字列はn+1番目の文字列に対し降順となるように文字を消去する。そして、n-1番目の文字列は消去した後のn番目の文字列に対し降順となるように文字を消去する必要がある。したがって後ろから順番に処理していくことで求められる。