第一回日本最強プログラマー学生選手権-予選-

参加しました～

全探索で十分間に合うのでそうします。

問題：N個の整数列ＡをK個並べた整数列の転倒数を求めよ

転倒数：あるaiより左側にあり、aiよりstrictに小さい。これを満たす整数組の数

考察：

ｉ番目の整数列Ａのｊ番目の要素をaijとします

このaijより左側にある要素は、Aがi-1個分と、Aの中で0~i-1番目までです。

両者のaiより大きい要素数は愚直にO(N)で求まります。

各iについて求めると、等差数列になるので和がO(1)で求まります。

全体でO(N^2)で解くことができました。

問題：黒白に塗られた２ｎ個のマスがある。ある２マスを選んでその区間（両端を含む）を黒白入れ替える。ｎ回の操作後にすべて白にする方法は何通りあるか

考察：

あるマスｉを考えます。

このマスの左側にはi-1マス、右側には2n-iマスあります。

左側で2つマスを選んだり、右側だけで2つマスを選んでもマスｉの色は変わりません。

また各サイドで偶奇も変化しません。ここに着目します。

片側が奇数、もう片方が偶数なことは、全体が２ｎ個なことから明らかです。

もしマスｉと奇数のほうをマッチさせると、両側が偶数になり、偶数回マスｉを含む操作がなされます。

したがって奇数のほうとマッチすると1回の反転、偶数のほうなら0回の反転と、同じ結果になることがわかりました。

初期値と、左右のマスの数の偶奇から、どちら側にマッチさせるかが求まります。

左側から順に決めていけば、簡単に総数が求まります。

右側と左側の数が不一致だったり、途中でマッチさせる相手がない場合は0通りです。

問題：ｎ個の頂点にnC2本の辺を追加し、各辺にレベルを設定する。このレベルごとに、ある頂点からその頂点に戻るようなパスは必ず偶数長になるように、レベルを設定する。レベルの最大値を最小化せよ

考察：

木構造ならn-1レベルまでなりそうです。

これより小さい場合を考えます。

1-2-3-4…という直線状の構造なら木と同じです。

この場合さらに辺を増やすことができます。

1-4など2個飛ばしなら追加しても問題ありません。

全てで2個飛ばしに追加したとき、追加できる辺はありません。

次に辺が張られていない頂点集合が背反になります。

mod2の0,1なので当然です

1,3,5...

2,4,6...にわかれます。

帰納的に同じことができます。

各ステップで最適に辺を張っているので、nC2本になるまで繰り返せば最適です。

1ステップ目で2個ずつ、2ステップ目では2個ずつの2個ずつ＝4個ずつなので、2^kになります。うまいこと調整して求めればO(N^2)で解くことができました。

156位で本戦出場権を得ることができました！たぶん！

Dがエスパーっぽかったんですけど、結果は結果なので喜んでおこうと思います。

Cは結構苦手な流れの考察でしたが、試行錯誤してどうにか通すことができてよかったです。ただケアレスで2ペナだったのは痛かったですが。

知り合いもおらずかなり不安なオンサイトなんですけど、せっかくのチャンスなので出ようと思います。たのしみ～