2022-01-01から1年間の記事一覧
コンテスト中AC:A〜E C - The Kth Time Query D - Multiply and Rotate E - MST + 1 C - The Kth Time Query 二次元配列を用意し、には、が出現したインデックスを順に記録します。 クエリが与えられた時、まず、のサイズがより小さい場合(出現数が)は、-1を…
問題へのリンク 解説AC 牛ゲーとのことで、解法は公式解説を見るのが良いかと思います。 ここでは、自分なりの理解をつけ足したいと思います。 牛ゲーについては、別記事にまとめました。 geam1113.hatenablog.com また、ネットで調べると色々出てきます。 …
2022/01/15 修正 ・有向グラフの図追加 初めに 牛ゲーとは 最大値と最短経路 具体例 初めに AtCoderの問題で牛ゲーが出たので、まとめておきます。数学的に厳密でない部分や、誤りを含む場合もありますのでご了承ください。 牛ゲーとは 以下の2つの問題があ…
C - Happy New Year! D - Prefix K-th Max E - Arithmetic Number C - Happy New Year! 非負整数の2進数表記の1を2に変換する操作を考えます。操作後の値をとします。すると、以下が言えます。 とは一対一対応する。 非負整数の変換によって、0,2のみからな…
解説AC。大体の解法は自分が想定したものと合っていました。 ここでは、を、頂点iに書かれた整数と表現します。 「i番目とj番目が交換可能」という条件を「頂点iと頂点jに無向辺がある」と言い換えます。 昇順に並び替えるとは、 すべての頂点について、とが…
