AtCoder Beginner Contest 134
遅ればせながら、Fの解説読んだので書いとく
A - Dodecagon
問題：半径rに内接する正十二角形の面積を求めよ
ただし3r^2になることが知られている。
感想：
・やるだけなんですけど、下の文なかったら恐ろしいですよねｗ
・中心から頂点に補助線引けば求まりそうだけど、ただの数学の問題になっちゃうし
B - Golden Apple
問題：N本のリンゴの木を、監視したい。ある木に監視員を置くと、i-D<=j<=i+Dを満たすjの範囲を監視できる。最低何人必要か。
解答：
・iの小さい方から考えて、D+1番目に配置すれば1から2*D+1本目まで見れます
・なんで切り上げでNを割ればよいです
C Exception Handling
問題：N個の整数列Aが与えられます。i=1~Nに対してAiを除くAの最大値を求めよ
解答：
・まず元のAの最大値をｘとします
・ｘが2つあるとき：どれか1つを除いてもｘがあります
・ｘが1つしかないとき：ｘを除くと元のＡの中で2番目に大きい値が答えになります
D - Preparing Boxes
今回の悪魔。こいつのせいで！こいつのせいで！
問題：N個の空の箱があり、ボールを1つ入れるかどうか決める。1からNの整数iに対して、iの倍数の箱に入っているボールの個数の合計を2で割った余りをaiとする。
a1～aNからボールが入っている箱の組を構築せよ
考察：
xi：箱iに入っているボールの個数とします
まずi>N/2の範囲では、N以下に倍数が1つしかないので、xi=aiです
この影響は、各iについて、iの約数であるjで受けます
いまiを考えます。もし、i+1以上の箱がすべて確定しているなら、aiに影響する箱はiのみです。
したがってaiによって一意にxiが決定します。
Nから降順に決定していけば求まります
約数を求めるにはO(√N)なのでO(N√N)に見えますが実はO(NlogN)で十分高速です
√Nを1からNで積分したとき、logNで抑えられるからみたいな感じだったと思います。
そもそもC++ならN<=2*10^5のO(NlogN)が9*10^7で間に合いそうです。
しかもiが小さいとき明らかに計算量が少なくなるのでまあ大丈夫だろうみたいな予測を立てることができます。
感想：
i番目の数はi+1なことに気づかず4WA・・・
プログラミングはじめたての頃よくやりますよね。0から始めまることに慣れない頃
ドーモ、プログラミング=ショシンシャです
まあ、触り始めて半年なんで初心者で間違ってはないです。にしても勿体ない。これで+20分&デバック時間って厳しいですね
E - Sequence Decomposing
問題：N個の整数列が与えられます。任意のi、j（i<j）について同じ色ならAi＜Ajが成り立つ。このとき最小何色で塗れるか
考察：
最長増加部分列いくつにわければ全てをカバーできるかっぽいです
前から見て、色ごとにいくつかの増加列を持って
・どれかに追加する
・新しく列を増やす
のどっちかの操作をします
このときどの列に追加すれば最適になるか考えましょう
1．追加できる列がない
これは明らかに新しく列を増やすしかないです
2-1．追加できる列がある
新しく列を作るか、追加するか、どちらも考えられます
末尾Tと、今見ているAi、そのうち来るAjを考えましょう。i＜j かつ T＜Aiです
もしT>=Ajなら、Ai＞AjですのでAiをどうするか関係なくAjの列を作らなければいけません。そうすると、AiはTの後ろに入れたほうが色が1つ少なく済みます
次に、T＜Aj<=Aiを考えます。
AiをTの後ろに入れると、（T,Ai）（Aj）という2つの列ができて、色が1つ増えます。
Aiを新しい列にすると（T,Aj）（Ai）という列になり、これも色が1つ増えます。
つまりどちらも変わりません。
最後にT＜Ai＜Ajです
Tの後ろに入れると(T、Ai、Aj)とできるので、新しく列を作るより色が少なく済みます。
以上から後ろに入る列が存在するなら、入れたほうが良いことがわかります。
T、Aiとは別にAjを入れられる列がある場合も同様です
2-2．追加できる列が2つ以上ある。
末尾がT1<=T2＜AiであるT1,T2の列があるとしましょう
まずそのうちT1＜Aj<=Aiを満たすAjが来るとします
そのとき(T1,Ai)としていると、Ajは新しい色にしなければなりません。
(T2,Ai)としていれば、(T1,Aj)が実現可能なため色が少なくて済みます
上記以外のAjについては、Aiをどちらにいれても変わりません。
2-1と同様に、Ajを他の列にいれるときも同様に変わりません
2-1、2-2から、Aiを入れることのできる列の中で最も末尾が大きいものに入れることが最適であるとわかりました。
実装：
末尾の値だけ持ったリストを作ります
このリストは二分探索で使いたいのでソートしておきたいです
末尾のリストにAi>TなるTがなかった場合、先頭に入れることになります。
ここで先頭に挿入するときO(N)なので、初期値-1かなんかで埋めておいて-1の一番後ろを置き換えます
これ書いてて思ったんですけど降順にしといて、二分探索手動で実装して.push_backすれば解決しそう
また、末尾に加えるTkがあったとします
Tk＜Ai<=T(k+1)であることは上の2-2から明らかです
よって、末尾に加える操作でソートが崩れることはありません。
最後に-1じゃない要素を数えればOKです。
感想：
問題読んでから、先頭挿入O(N)じゃんってなるまでに4分。
-1で埋めればいいじゃんってなるまでに7分。
合計16分で解けたのまあまあ早くない？
41分5完+ペナ30分でパフォ1356でした。うーん冷えてくなー
ペナ減らせば青は出てたと思うから精度上げるって感じなのかなあ。
F - Permutation Oddness
問題：長さNの順列を考える。奇妙さをΣ(i=1~N)(|Ai-i|)とする。Aiはi番目の整数。奇妙さがkとなる順列の個数を求めよ
全然わからなかったので解説読みました。以下解説の読解
解説：
まず2つの順列のマッチングと解釈できます。順列AとBとしておきましょう
このマッチングを前から決めていきます。
あるiを見ているとき、
・既に出たi以下の数とマッチングさせる
・i+1番目以降とマッチングさせるために保留する
この2つの選択肢があります
またマッチングさせる場合は、下の条件から片方はiである必要があります
このとき保留しているAjの数、Bjの数は一致します。同じ個数の数字をみてマッチングは1対1なので明らかです。
保留している数字がそれぞれj個あるとしましょう。
見ている数字をiからi+1にしたとき、保留している数字1つの奇妙さは1以上増加します。なぜならマッチングする相手の最小値がiからi+1になったからです。
したがって遷移では奇妙さが2*j増加することがわかります
次にマッチングをする組み合わせは以下の3通りです
1．保留している数は変わらない。
2．保留している数を1つ減らす。
3．保留している数を1つ増やす。
1つずつ見ていきます
1：AiとBiのどちらかを使いマッチングを1つ作ることを指します。
Aiに対してj個、 Biに対してj個、Ai-Biのマッチングが1個の2*j+1通りあります
2：AiとBiを別々に使いマッチングを2つ作ります。
Aiに対してj個、Biに対してj個、この組み合わせなのでj*j通りあります
3：Ai,Biをどちらも保留させることです
当然1通りです
DP[i][j][k]：i番目まで見て、保留している数がそれぞれj個、暫定奇妙さがkの場合の数
このDPをすれば、DP[n][0][K]が答えになります。i、jはN通り、kはN^2通り(実現可能なものはもっと少ないが)なので、O(N^4)で解けました。
感想：
なんだか暫定奇妙さだけで答えが求まるのがすごい不思議でした。
冷静に書けば確かにそうなんですけど感覚的じゃないなあと。
iとどれをマッチングさせても変わらないって状況にするのは難しいですね。
DPが苦手なのもあるんですけど、「ここに着目すると探索範囲がぐっと縮まる」みたいなのってできるようになりたいです
