algoNote

プログラミング関連

SRM 717 Div2

おそらく全完したのは今回が初めてなので嬉しいです。嬉しいのでブログを書きました。

体感難易度としてmedの方がeasyより簡単な気がしました。(逆でしょ)

[easy] NiceTable

問題概要

0,1からなるテーブルが与えられる。このとき0,1からなる配列x,yを考える。
すべてのi,jについてt[i][j] == x[i] XOR y[i] となるようにx,yを決められるとき"Nice",そうでないときは"Not nice"を出力する。

  •  {1 \leq 縦 \leq 5}
  •  {1 \leq 横 \leq 5}

解法

全探索

縦横の長さはともに高々5なので、x,yを全探索出来ます。実装としてはビットで管理すると簡単です。

別解

テーブルの1列目と1行目を見ることで、適当にx,yを仮定することができるので、それが条件を満たすか調べます。

XORには {A \oplus B = C} であるとき {B = A \oplus C} , {A = B \oplus C} となるという性質があります。
これを利用してx,yを仮定していきます。

コンテスト中にはこちらの解法を書きました。

ソースコード

NiceTable

[medium] LexmaxReplace

問題概要

アルファベット小文字からなる文字列s,tが与えられる。sの文字をtの文字を使って書き換えていくことで作ることのできる文字列のうち辞書順最大のものを求める。ただしtの文字をすべて使う必要はない。

  • {1 \leq |s| \leq 50}
  • {1 \leq |t| \leq 50}

解法

辞書順最大にしたいのだから、なるべく左にある文字をできるだけ大きくすればよいことが分かります。 したがってtの文字を降順ソートして、左から順番に使っていけばよいです。

ソースコード

LexmaxReplace

ちなみに、idxがt.size()と等しくなった時にbreakする処理を抜かしていたことに提出してから気づいてresubmitしたのですが、 この処理を書かなくても通った人もいるそうです。

同じミスをやっている人が部屋にいるのを見つけたのですが、時間切れでチャレンジしそこねました(結果的にチャレンジしなくて正解でしたね)

[hard] DerangementsDiv2

問題概要

整数n,mが与えられる。このとき、1,2,3,…,n+mのn+m要素からなる配列を並べ替えてできる順列のうち、初めのm要素についてp(i)!=iとなるような順列の個数を109+7で割った余りを求める。ここでp(i)は順列のi番目の値を指す。

  • {0 \leq n \leq 50}
  • {1 \leq m \leq 50}

解法

方針として、すべての順列の個数からp(i)==iとなるiがあるような順列の個数を引くことで求めます。

p(i)==iとなるiがあるような順列の個数をnegとすると、negは包除原理を用いて求めることが出来ます。


例としてn=1,m=3を考えてみます。

1が被っている順列は
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
これは (4-1)! = 3! = 6 通りあります。
同様に2が被る順列の個数、3が被る順列の個数もそれぞれ 3! = 6 通りあります。
どの数字が被るかが {_3C_1} = 3 通りあるので、1つ以上の数字が被る順列の個数は 6 * 3 = 18通りあります。

次に 1と2が被っている順列は
[1, 2, 3, 4]
[1, 2, 4, 3]

1と3が被っている順列は
[1, 2, 3, 4]
[1, 4, 3, 2]

2と3が被っている順列は
[1, 2, 3, 4]
[4, 2, 3, 1]

よって2つ以上の数字が被る順列はそれぞれ (4-2)! = 2! = 2 通りあります。
どの2つの数字が被るかが {_3C_2} = 3通りあるので、2つ以上の数字が被る順列の個数は 2 * 3 = 6通りあります。

最後に1,2,3が被るような順列は
[1, 2, 3, 4]
(4-3)! = 1! = 1通りです。 被る数字の選び方は {_3C_3} で1通りなので3つ以上の数字が被る順列の個数1通りです。

よってこの場合のnegは包除原理を用いて、

neg = (1つ以上の数字が被る順列の個数) - (2つ以上の数字が被る順列の個数) + (3つ以上の数字が被る順列の個数) = 18 - 6 + 1 = 13

と求まります。

したがって、この例での答えは (3+1)! - neg = 4! - 13 = 11 となります。


これを一般化すると、1〜mのうちk個以上が被っているような順列の個数は {_mC_k \times (n+m-k)!} で表すことができるので、 答えは

{ \displaystyle
ans = \lbrace (n+m)! - \sum_{k=1}^{m}{_mC_k \times (n+m-k)! \times (-1)^{k-1}} \rbrace \% 10^{9}+7
}

となります。

ソースコード

DerangementsDiv2