ARC
コンテストページ: AtCoder Regular Contest 158 - AtCoder コンテスト中AC: A A - +3 +5 +7 3つの値を同じにする問題は割と良く見る気がします。そして、この系統の問題は、差をどのように詰めるのか、という視点で見ると解ける場合が多いです。 今回、及び…
コンテスト中AC:A A - Larger Score 入れ替えに必要な操作回数 複数個入れ替える場合に必要な操作回数 問題の条件を満たすのに必要な操作回数 A - Larger Score 一応、考察した内容ですが、あまり自信はないです。 番目までのから順番を保ったまま抜き出した…
コンテスト中AC:なし A,B解説AC A - Coprime Pair B - Count 1's A - Coprime Pair 公式解説 素数の間隔(prime gap)が重要とのことです。 素数の間隔 - Wikipedia 公式解説及び上記のwikiによれば、問題の制約における素数間の極大の間隔(maximum gap)は1500…
コンテスト中AC:A,C Bはコンテスト後自力AC。もう少しで解けそうでした。 A - Floor, Ceil - Decomposition 実際に10まで、xとfloor(x/2)×ceil(x/2)のどちらが大きいか手計算しました。 すると、 x≦4なら、x≧floor(x/2)×ceil(x/2) x≧5なら、x
コンテスト中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,B A - Permutation Grid B - Shift and Reverse A - Permutation Grid nの制約上、実際に構築することはできません。 このことから、の組みによって一意に定まるような法則性がありそうだと予測します。 白黒がどのように決定するか試して…
解説AC ABCのこの問題のように類題は出題されています。しかし、このように逆に構成できることは思いつきませんでした。 右からi桁目までを10進数の整数としたとき、なる区間(j,i]を10進数としたものが7の倍数となる条件は、 を満たすことです。なお、10と7…
解説を見てAC 公式解説に詳しく書かれていますが、自分用にメモしておきます。 勝敗の決定 ・Nが奇数なら先手必勝 ・Nが偶数なら、1個取って0にできれば先手必勝、そうでなければ後手必勝 1個取って0になることの判定法 公式解説と少し違いますが、この方が…
コンテスト中AC:A,B A - Two Lucky Numbers B - Grid Repainting 4 A - Two Lucky Numbers 整数xの文字列表現をstr(x)とします。また、str(x)+str(y)は文字列の連結を表すこととします。 基本的にはstr(B/2)とstr(A)を連結させる方針となります。 しかし、B…
コンテスト中AC:A,B A - Remove One Charcter B - Colorful Lines A - Remove One Charcter 同一文字が連続する領域から、i文字目とj文字目取り除いてを作る ことと、 が等しい ことは必要十分条件です。 必要性は明らかです。 十分性を示します。 の取り除…
コンテスト中AC:A,B A - Smaller XOR B - Range Point Distance A - Smaller XOR 以下、整数は2進数で表現するものとします。 N = 10101としてシミュレートしてみます。 (1) xの4ビット以降に1がある場合 例えば、x = 100000とすると、 100000 XOR 010101 = …
コンテスト中AC:A,B A - Gold and Silver を折線グラフで考えたとき、下に凸な頂点で金に交換、上に凸な頂点で銀に交換し、それ以外では何もしないのが最適です。 始点と終点は例外なので、のとき、以下のようにします。 1.金を持っているとき なら、まだ上…
コンテスト中AC:A A - Dial Up に1しかないのにに1がある場合、-1です。0の場合も同様です。以下、そうでない時を考えます。 を円環とみなしたとき、と異なる数のうち最も近い位置と、との距離をとします。 への追加操作は明らかに回必要であるため、以下で…
