コンテスト中AC:A,B Cはコンテスト後自力AC A - Bridge and Sheets B - Reserve or Reverse C - The Majority A - Bridge and Sheets 便宜上、を追加しておきます。 最初からかけられているシートのうち、最も右端をとします。最初としておきます。 にかけら…

コンテスト中AC:A,B A - Erase by Value B - Dividing Subsequence A - Erase by Value 同じ数は消えるので、一旦連続して重複した数について、重複を削除して考えます。 から始めて、単調増加している間は、消すと辞書順では大きくなってしまうので、消さな…

コンテスト中AC:A〜C D - Dance 状態遷移を伴うDFS 考慮すべき事項 状態の管理に必要な情報 情報の受け渡し方法 値渡し グローバル変数等で共有 終了条件 D - Dance 解けなかったので、反省点含めて記録します。 まず、Nが小さいことから全探索が可能と予想…

自力AC(一度TLEになったので、解法を見て、合っているか確認した) 条件を満たす桁に関する問題 以下の整数全てに関する問題 という条件から、桁DPが有力候補となります。 桁DPに関する情報はネット上に多くあるため、ここでは割愛しますが、大雑把に説明しま…

コンテスト中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に無向辺がある」と言い換えます。 昇順に並び替えるとは、 すべての頂点について、とが…