AtCoder Grand Contest 046

AGC

※解説的なものを期待している場合、以下は全く読む価値ないです。
　ほとんどどのようなことを考えてハマっていたかだけが書かれています。

コンテスト前のレート：1801
レート通りのパフォーマンスが得られる順位：571位

A - Takahashikun, The Strider

問題
勘で投げて賭けに勝った。

思考過程
  1. 例を見た雰囲気で、X \times Kが360の倍数になれば原点に戻ってこれそうだと思う。
  2. 例２はほぼ円（正360角形）の軌道になりそうな気がするし、多分大丈夫？ 証明は知らん。
  3. 余計なオーバーフローの確率を減らすため、平気なはずだが念のためlongにしておく。

後から、軌道を繋げていくのではなく、全部原点を始点としたベクトルにしてみるとスター型のグラフのようになり、K本のベクトルの和がゼロベクトルとなる状態を思い浮かべると、なんとなく合ってそうと思えた。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextInt();
        sc.close();

        for (int i = 1; ; i++) {
            if (x * i % 360 == 0) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで2分22秒＋0ペナ。248位。
　

B - Extension

問題
50分ほどかけて解けず。

思考過程
  1. 例２を元に考えてみる。
  2. 黒く塗れる可能性のあるマスは、3 \times 4 - 2 \times 1=10マス。行追加と列追加は合計4回なので黒マスは4個。
  3. _{10}C_4から余事象を引くとかできるか？　→重複排除するのが非常に難しそう。
  4. 下から3行目を追加したときの黒の位置が何列目かで場合分けすると以下のようになり、全部足すと65通りで合ってる。
    • 1列目：3^3=27通り
    • 2列目：2^1 \times 3^2=18通り
    • 3列目：2^2 \times 3^1=12通り
    • 4列目：2^3=8通り
  5. 例２に1行追加し、「2 1 4 4」だったらどうなるか？
  6. DPをしたときの3行目から4行目への遷移を考えるが、3行目と4行目の黒マスの位置関係D^2パターンを全部個別に求めて加算する必要がありそうで、上記の式の3^Kを4^Kに変えたりする必要もありそうな？

といったところでだいぶ時間も過ぎたのでC問題へ。
　

C - Shift

問題
初手でB問題よりいい感じに考察進んだ気がしたし、こちらの方が点数が高いので、残り時間を全部つぎ込んだが解けず。

思考過程
  1. 無限回操作できるとすると、最終的には「111...000...」のような並びになる。
  2. '1' を '0' の前に移動させる操作は、上記の最終形をソート済み状態と見たときの転倒数を減らす操作のように見える。
  3. 各 '1' について、前方に '0' がいくつあるかの数列を作ると、その数列と文字列の並びは1対1で対応する。例１～３を数列に変換すると以下のようになる。
    • 0101 → [1, 2]
    • 01100110 → [1, 1, 3, 3]
    • 1101010010101101110\ldots → [0, 0, 1, 2, 4, 5, 6, 6, 7, 7, 7, \ldots]
  4. このような数列に対し、i番目の要素を1以上減らす操作をK回以下行って作れる数列は何通りか？（※操作後にソートして同一になるものは1通りとみなす）　という問題に言い換えられた。
  5. 「dp[x][y][z]：x番目まで見て、操作をy回行って、ソート後数列の末尾の値がz」というものを考えてみたが、結局遷移を上手く書き切れずに終了。

解説PDFを見るとDPの定義が完全に違いそう。
やっぱりDPは苦手分野っぽい。
　


最終結果：Aの1完、980位、パフォーマンス1381
レート変動：1801→1765

水色時代はAGCに稼がせてもらっていたのに、最近のAGCの成績はいまいち。
むしろ5月6月は完全に失敗しているのはAGCだけなのだが・・。