こんばんは、しほみんです。
久々に競技プログラミングの話をします。先週土曜日に企業が主催のコンテストが行われた挑戦してきました。日付が超えてしまったのでちょっと反省です。
https://atcoder.jp/contests/nikkei2019-2-qual/tasks
そもそも注目してなかったので時間の参加自体も遅れて、うまく解けずに終わったパターンでした。A問題しか解けずに、レートも大幅に下がりました。
プログラムやっぱ最近書いてないから力落ちちゃってますね…何処かで取り戻さねば…
今回もB問題はアルゴリズムができててもプログラム的な制約でミスったパターンでした。よくよく反省してやっていきたいと思います。
今回もどう考えたかなど考察していきたいと思います。今回はC問題まで理解できているのでそこまで書いていこうと思います。
ここから以下ネタバレです。
A問題
Nが与えられた場合、Nを1以上の異なる整数の2つの和で表します。
この時の和の表し方は何通りありますかって問題です。
例えば、N = 7 のときは（1,6),(2,5),(3,4)の3通りです。
これはいくつか考察すればすぐに解けます。
N = 2のときは0です。
N = 3 のときは(1,2)の1通りです。
N = 4のときは(1,3)の1通りです。
N = 5のときは(1,4),(2,3)の2通りです。
N = 6のときは(1,5),(2,4)の2通りです。
と考えていくと、小さいほうの数は1から偶数のときは(N-2)/2、奇数のときは(N-1)/2までの数が考えられるので答えは
偶数のとき (N-2)/2
奇数のとき (N-1)/2
です。
ただし、偶数のときでも(N-1)/2でもint型の切り捨てが起こるので
答えはint型で固定して(N-1)/2です。
B問題
頂点木の問題です。要するに、1を頂点としたとき、それ以外の数との距離が指定されるのでそれを満たすものが存在するか考えればよいです。
例えば4つの頂点がって、1からの距離がそれぞれ0,1,1,2だったら、
4が2につくか、3につくかで変わります。よって、2通りです。
基本的に1の距離は0です。これを満たさない場合はありえないので0です。
あとは距離がiのものを考えていきます。
iのときがm個、i+1のときがn個あるとします。
m個からn個への結び方を考えます。必要なことはn個は必ずm個のどっからかつながる必要があって、m個のほうは全部使う必要がないです。
これを踏まえると、i+1からiにつなぐところはi+1のそれぞれ任意でm個のどこかにつながればいいです。これで木の条件を満たします。
よって、nのm乗がiとi+1のありうる組み合わせです。
あとはiは0から最大の距離までそれぞれ求めてかければいいです。
ただし、問題は指数関数なので値がとても大きくなります。なので随時、指定された数で割らないとなりません。自分がそこで大きく躓いてACできませんでした。
C#ではどうやらBigIntegerというライブラリの中に、PowMod関数というのがあるので、それで、数とmodで割る数を指定して、かけていけばあふれません。
最近こういう制限で失敗していることもあるのでまだまだ知識は足りないなと思います。
C問題（時間内で回答はできませんでしたが、ちょっとの考察と回答を見て理解しました）
とあるAとBの列があって、Aをn-2回まで変えることができた場合、AとB列のすべてのAi<=Biであればよいということです。
Aを変えることなんですがN-1回あれば基本的に任意の数列にできる（はず）です。
ということは基本的にA,Bを小さい順に並び変えたばあい、そのA<=Bが満たせればいいことは何となく考えられます。ただ、N-2回までなので1回なんとかして減らす方法を考えるって感じです。
よってまずはA, Bは小さい順にソートします。Ai <= Biがまず満たせるか考えます。満たさなければその時点でNoです。
あとはYesの場合ですが、問題はそのソートができるかどうかです。
N-1回ならどんなものでもソートできます。なので1回操作を減らすことができる場合は、Yesとします。
1回操作を減らす方法は2通りです。
①サイクル分割が2つ以上になる。
②サイクル分割が1つでも、Aのどこかの隣り合う数を並び替えてもAi<Biの条件を満たす場合（つまり、Ai+1<=Biを満たすiが存在する場合）
サイクル分割とは...
線形代数学の置換のことを示す。（詳しくは教科書とかで見てください）
数列1と2がある場合、どのように数が循環しているかを見ます。
例えば数列1{2, 7, 5, 3, 1, 4, 6}と数列2{1, 2, 3, 4, 5, 6, 7}の場合、
数列1の2をスタートした場合、2→1→5→3→4→6→7→2と循環します。
この場合すべての数を通るので(1 2 3 4 5 6 7)となって1サイクルになります。
1サイクルの場合、すべてを整理するにはN-1回の交換が必要です。
よって、サイクルが増えるとそれぞれNi個あるとするとNi - 1回のサイクルあるのでサイクルがn個あれば、n回減ります。ここから、①のサイクル分割が2つ以上あれば、成立します。
②の場合ですが、Aを整えるより、Bを意図的に変えて、サイクルをずらす手法です。この場合、サイクルが1つでも、交換回数を一回減らせるので成立します。
例えばA={1, 2, 3, 4, 5, 6, 7}とB={1, 2, 3, 4, 6, 6, 7}の場合、
A={1, 2, 3, 4, 6, 5, 7}とAの5番目と6番目は入れ替えてもA<=Bを満たし、条件を満たします。
{1, 2, 3, 4, 5, 6, 7}がN-1回なら、{1, 2, 3, 4, 6, 5, 7}はN-2回の交換で済むんだろうなって感じです。これははっきり言って結構考えるの難しい気がします....
C問題のアルゴリズムは以下のようになります。
①AとBを読み込む
②AとAをソートしたものとBをソートしたものを用意
③AとBとソートしたものをAi <= Biかで確認する。満たさないならNo
④Aのサイクルの確認、AとAのソートしたものを素直に置換のルートをしてみて1サイクルか確認。2サイクル以上ならYes
⑤1サイクルの場合、Ai+1 <=Biを満たすiがあるか探す。あったらYes。なければNo
（注）2019.11.17変更
ちょっと実装してみたのですが、なにかうまく行かないのでちょっとアップは見送ります…すいません。考え方はあってると思うのだけど…
やっぱり、ここまでくると難しいなって感じです。普通にただコンテスト挑んでもうまくいかない感じがするので、どこかで時間を作って勉強したいなと思います。
ではでは。
