geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ARC

ARC138 参加記録

コンテスト中AC:A A - Larger Score 入れ替えに必要な操作回数 複数個入れ替える場合に必要な操作回数 問題の条件を満たすのに必要な操作回数 A - Larger Score 一応、考察した内容ですが、あまり自信はないです。 番目までのから順番を保ったまま抜き出した…

ARC137 参加記録

コンテスト中AC:なし A,B解説AC A - Coprime Pair B - Count 1's A - Coprime Pair 公式解説 素数の間隔(prime gap)が重要とのことです。 素数の間隔 - Wikipedia 公式解説及び上記のwikiによれば、問題の制約における素数間の極大の間隔(maximum gap)は1500…

ARC135 参加記録

コンテスト中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

ARC134 参加記録

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

ARC133 参加記録

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

ARC132 参加記録

ARC

コンテスト中AC:A,B A - Permutation Grid B - Shift and Reverse A - Permutation Grid nの制約上、実際に構築することはできません。 このことから、の組みによって一意に定まるような法則性がありそうだと予測します。 白黒がどのように決定するか試して…

ARC129C Multiple of 7

解説AC ABCのこの問題のように類題は出題されています。しかし、このように逆に構成できることは思いつきませんでした。 右からi桁目までを10進数の整数としたとき、なる区間(j,i]を10進数としたものが7の倍数となる条件は、 を満たすことです。なお、10と7…

ARC131C Zero XOR

解説を見てAC 公式解説に詳しく書かれていますが、自分用にメモしておきます。 勝敗の決定 ・Nが奇数なら先手必勝 ・Nが偶数なら、1個取って0にできれば先手必勝、そうでなければ後手必勝 1個取って0になることの判定法 公式解説と少し違いますが、この方が…

ARC131 参加記録

ARC

コンテスト中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…

ARC130 参加記録

コンテスト中AC:A,B A - Remove One Charcter B - Colorful Lines A - Remove One Charcter 同一文字が連続する領域から、i文字目とj文字目取り除いてを作る ことと、 が等しい ことは必要十分条件です。 必要性は明らかです。 十分性を示します。 の取り除…

ARC129 参加記録

コンテスト中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 = …

ARC128 参加記録

コンテスト中AC:A,B A - Gold and Silver を折線グラフで考えたとき、下に凸な頂点で金に交換、上に凸な頂点で銀に交換し、それ以外では何もしないのが最適です。 始点と終点は例外なので、のとき、以下のようにします。 1.金を持っているとき なら、まだ上…

ARC125 参加記録

コンテスト中AC:A A - Dial Up に1しかないのにに1がある場合、-1です。0の場合も同様です。以下、そうでない時を考えます。 を円環とみなしたとき、と異なる数のうち最も近い位置と、との距離をとします。 への追加操作は明らかに回必要であるため、以下で…