Retribution全体感想45分4完(1ペナルティ)で114位でした。問題Fが解けそうだったので、考えていました。方針が立って、あとは細部の計算を確認しながら実装するだけ!となったのが終了15分前。細かい計算ミスなどをチェックする余裕がほとんどないまま残り1分くらいで実装できましたが、サンプルが合わずダメでしたw終了後の検証でちゃんとACできたので、制限時間の問題ではあったようです。いう得意寄りの問題を正解に結び付けていかないと上位には行きづらいですね。Inversion300点の配点ですが、例えばABCコンテストの300点と比べるとだいぶ難易度が高いように思います。転倒数は条件を満たす2つ組の数え上げですが、何らかの形でまとめて数えたいです。2つ組の片方を固定して数えるのが通常の考え方です。今回はさらに、同じパターンの並びを繰り返すことを使わないと計算量が爆発しそうです(1つの数を1回読むだけでTLEする)。3という並びの、3グループ目の「1」から見た転倒数です。1,2グループ目からは同じ位置の5つが数え上げられ、3グループ目だけ例外的となっています。自身より小さい数値が1周期にいくつ含まれているか。・同グループ内の転倒数に分けて計算するという発想になります。自身より小さい数値が1周期にいくつ含まれているか。周期内の自身より左に小さい数値がいくつ含まれているか。N)$で計算する方法もあります。今回の問題では不要ですが、過去問のARC-Cクラスでは必須となっているようです。転倒数」などでぐぐりましょう。Inversion奇サイクルがないという条件は、二部グラフと同値であることは知っていました。完全グラフを二部グラフに分割する問題です。程度なので、レベル2つくらいで出来るのかな?というのが第一印象でした。これを実験していると、5頂点の場合に失敗します。完全二部グラフよりも小さい辺集合をとると、さらに状況が悪くなります。完全グラフが含まれる」ことに気づきました。以上必要ということが分かります。実例構成もこの考え方の隣に落ちていました。元集合をぴったり2分割することが必要そうだと気づきます。通りでばらけていなければいけません。進法表示を各レベルの二部グラフの分割に対応させていけばよいと分かります。Retributionコンテスト中には、解ききれず。場合分けによる分析を長く進めていました。いくつあるかという余計なパラメータが入ってなかなか簡単にならず。そのうち、余事象側の方が簡単であることに気づきます。対して余事象の方が簡単だと気づきますが、すると最初から余事象を考えればよいと気づきます。ここに気づいてからは、形式的べき級数を書いて5分くらいで方針が立ちました。方針が立ったのが終了15分前で解ききれず。なんで余事象を考えるまでに30分以上かかっているのか...という反省点がありますが、まぁ仕方ないかな。公式解説とも方針が異なりそうだったので、別記事で解説を書きました。良ければこちらをご覧ください。44分4完1ペナで、249位でした。75分4完(ABCE)4ペナ、163位でした。56分5完で、11位でした。ABCDとEFで、かなり難易度差の大きな問題セットでした。107分4完10ペナで、50位でした。形式的べき級数解説pythonその他タイトルとURLをコピーしました。