競技プログラミング

AtCoderでABC066を解きました

A – ringring

問題文

snuke 君は自転車を買いに来ました。
snuke 君はすでに買う自転車を決めたのですが、その自転車にはベルが付いていないため、
自転車とは別にベルも買う必要があります。

snuke 君は安全意識が高いので、ベルをどちらの手でも鳴らせるよう、両方のハンドルに 1 つずつ
付けることにしました。

お店にあるベルは 3 種類で、それぞれ a円、 b円、 c円です。
この 3 つのうち、異なる 2 つのベルを選んで買うときの、値段の合計の最小値を求めて下さい。

制約

  • 1 <= a,b,c <= 10000
  • a,b,c は整数

考えたこと

3つのうち安い2つを買えば良いので全部足してから一番高いものを引けば良いです。

B – ss

問題文

同じ文字列を 2 つ並べてできる文字列のことを偶文字列と呼ぶことにします。
例えば、 xyzxyzaaaaaa は偶文字列ですが、abababxyzxy は偶文字列ではありません。

アルファベットの小文字からなる偶文字列 S が与えられます。
S の末尾の文字を 1 文字以上消して作れる偶文字列のうち、最も長い偶文字列の長さを求めて下さい。
与えられる入力では、条件を満たす 1 文字以上の文字列が存在することが保証されています。

制約

  • 2 <= |S| <= 200
  • S は小文字のアルファベットのみからなる偶文字列である。
  • S に対して、条件を満たす 1 文字以上の文字列が存在する。

 考えたこと

偶文字列のサイズは必ず偶数なので長さ2ずつ小さくしていって偶文字列になっているかチェックしてやれば良いです。O(n^2)になりますが200以下なので問題ないです。

C – pushpush

問題文

長さ n の数列 a_1, … , a_n が与えられます。
空の数列 b に対して、以下の操作を n 回行うことを考えます。

i 回目には

  1. 数列の i 番目の要素 a_ib の末尾に追加する。
  2. b を逆向きに並び替える。

この操作をしてできる数列 b を求めて下さい。

制約

  • 1 <= n <= 2 * 10^5
  • 0 <= a_i <= 10^9
  • n,a_i は整数である。

考えたこと

この操作をまじめにしていたら終わらなさそうなので別の方法を考えます。

例をみてみると明らかに規則性があり、数列が真ん中の方から詰まっていっていることに気づきました。この作戦で配列を用意してその真ん中のほうから数列を詰めていくこともできそうでしたがインデックスをミスしてしまいそうだったので、両端キューを使って前後から繋げていけば楽そうだなと思いそちらで実装しました。

D – 11

問題文

1,…,nn 個の整数からなる長さ n+1 の数列 a_1,a_2,…,a_{n+1} が与えられます。
この数列には 1,…,n のどの整数もかならず 1 回以上出現することが分かっています。

k=1,…,n+1 のそれぞれについて、与えられた数列の長さ k の(連続とは限らない)部分列の個数を求め、
10^9+7 で割ったあまりを出力して下さい。

注意

  • 2 つの部分列が数列として同じであれば、元の数列での位置が異なっていたとしても、1 通りと数えます。
  • 数列 a の長さ k の部分列とは、a の要素のうち k 個を選んで、
    それらを順番を変えずに取り出して並べた数列のことを指します。
    例えば、数列 1,2,3,4,5 の長さ 3 の部分列には、 1,3,51,2,3 などがあります。
    一方で、3,1,21,10,100 はこの数列の部分列ではありません。

制約

  • 1 <= n <= 10^5
  • 1 <= a_i <= n
  • 1,…,n のどの整数も必ず数列に出現する。
  • n,a_i は整数である。

考えたこと

鳩ノ巣原理的にどれかひとつだけが2つあるんだなというところからその同じ数字Aのインデックスを使ってこちゃこちゃして答えを出すんだろうなと考えました。

そしてこれは全体から被ってる個数を引くと楽そうだなとも思いました。

部分列の長さがiのとき、全体はCombination(n+1, i)です。被っているやつというのは数字Aを1回だけ使っていてかつその数字Aがどちらかわからない、つまり数字Aの外側しか使っていないということです。

従って答えはCombination(n+1, i) – Combination(数字Aの外側の個数, i-1)です。

これでいけそうだと思い実装しようとしたのですが、今回はここでかなり手間取りました。

まずコンビネーションはパスカルの三角形で計算するとO(n^2)かかってTLEしてしまうのでフェルマーの小定理を使うやつか〜と思い引っ張ってきました。

その後1000000007でMOD取るのを忘れたり、MOD取る前にMOD足すのを忘れていたりしてなんでWAなん??というのを数回してACできました。