ポケモンでさぼっていたんですが、まともに復帰しました
6完 65:45で239位でした、まあまあ
A Generalized ABC
Aはfor文が定着したんですかね、逆に普通のifがきたらびっくりしそう
(AC 1:18)
B Let's Get a Perfect Score
よくあるBですが、or演算を使うことでループをちょっとだけ楽にできます
こういうのかっこいいんだけど、あんまり実用性は...
(AC 3:51)
C String Delimiter
エスケープシーケンスの練習？
"っていう文字はちょっとめんどうなので、エスケープシーケンスを使おうと思ったんですが、よくわかんなかったのでint型に文字を変更して解きました
やること自体はBにあってもおかしくなさそう
(AC 9:34)
D Make Bipartite 2
むずくないですか？D適正の人が二部グラフにどのくらい触れているのか...
まずそもそものグラフが二部グラフでないときはお話になりません、0で終わりです
そもそも二部グラフだった時について考えます
白・黒の2色で塗ることを考えると、つないだあとも二部グラフであるためには、白と黒の頂点を結ばなければいけません
逆にそうであれば、どのように結んでも問題ありません
よって、白の頂点の数をw, 黒の頂点の数をbとして、b*wが答えになります
...とすめばいいんですが、グラフが連結でない場合があります
連結でないものを結ぶ場合は、どのように結んでも問題がないので、各連結成分にある頂点の個数をKとして、K*(N-K)だけ増やすことができます
ただし重複ができるので省かないといけないことに注意しましょう
(AC 18:23)
E Choose Two and Eat One
これもむずいよ～
まず、N≦500なので各ペアにおける(x^y + y^x) mod Mは、繰り返し二乗法でO(N^2 log(N^2))で計算できます
そうすると、N*Nマスのグリッドから
・1つをのぞいた各行1つ選ぶ(そのときに消す)
・(i,j)を選ぶと、(j,i)は選べない
という条件で、スコアを最大化する問題に帰着されます
これは、「1つをのぞく」行を決め打ちして、フローを流せば燃やす埋めるで解ける気がします
...が、冷静になって考えるとEでフロー、しかもそれなりに考察しないといけないものがでるわけがないので、もう少し考えます
操作回数がN-1回になることと、ペアをつくることは頂点をつなぐことであるということを考えると、なんとなくグラフ構造が使えそうだなと思って、そこまでいくと最大全域木を構成するのがよさそうに思います
木構造になれば、操作列自体の構築も簡単(先に捨てるものから葉にすればよい)ので、これは適用できそうだと思います
ここまでくればあとは普通のMSTを書けばよいです
(AC 43:43)
F Union of Two Sets
構築+インタラクティブでおもしろそうだけど、むずかしそうだなと思いながら見ます
まずN=4000のときに何が飛んでくるかわからなくて、逆にここに全対応できればNがどんな値でもなんとかなることがわかります
どこから手を付けるかなんですが、絶対に必要なものから考えます
たとえば(5,5)と飛んできたときに長さ1のものがないと確実に死ぬので、長さ1の(1,1),(2,2)...(N,N)は必須になります
これがあると、長さ2には問題なく対応できます
となると、長さ3のものが必要です
長さ3があると、たとえば長さ5は1つだけ要素をかぶせることで3+3-1=5と構築できます
同様に考えると、長さnが全パターン網羅できればn*2までは網羅できます
そうすると、1,3,7,15...の長さのものを構築すればよく、これを実際に構築すると40000にいかないくらいになって制約的にも問題ありません
あとはクエリに答えていくんですが、クエリで与えられた長さをDとすると、1,3,7,15...を1つずつ調べて、D/2以上であればその長さのものを2つくっつけて構築できます
pairと番号の対応をmapで管理したので、クエリあたりの計算量O(logM^2)で解きました
(AC 65:45)
G Similar Permutation
挿入DPっぽいなーと思ったんですが、わからず...
復習します
(AC --:--)
総括
Eでハマっているようでは...
