1660B Vlad and Candies(機械翻訳直訳のみ)

Problem - 1660B - Codeforces

問題

少し前まで、Vladには誕生日があり、そのためにキャンディーのパッケージが贈られました。キャンディーにはn種類あり、 タイプi (1 \leq i \leq n)のa_{i}種のキャンディーがあります。

Vladは、現在最も頻繁に使用されているタイプのキャンディーのいずれかを選択して、毎回1​​つのキャンディーを食べることにしました(そのようなタイプが複数ある場合、彼はそれらのいずれかを選択できます)。食べることを最大限に楽しむために、Vladは同じ種類のキャンディーを2つ続けて食べたくありません。

2つの同じキャンディーを続けて食べることなく、すべてのキャンディーを食べることができるかどうかを彼が理解するのを手伝ってください。

解答

全部で3つのケースがあります、2つのタイプのキャンディーでそれらを考えてみましょう:

 a_{1}= a_{2}の場合

キャンディーをこの順序で食べます a_{1},a_{2},a_{1},a_{2}\cdots a_{1},a_{2}


 a_{1} = a_{2} + 1 の場合

次にタイプ1のキャンディーを食べ、次にこの順序で食べます[2,1,2,1、…、2,1] (ほぼ上記の場合と同様)

 a_{1} = a_{2} + 2の場合

タイプ1のキャンディーを食べますが、タイプ2のキャンディーよりもまだ多く、タイプ1のキャンディーをもう一度食べる必要があります。したがって、答えは「No」です。
ここで、配列aに存在する最大値と次に最大な値でこれらの条件をチェックするだけで十分であることを証明します。 3番目の条件が真の場合、答えは「No」になります。

それ以外の場合は、最大にある2つのタイプのキャンディーを順番に食べて3番目の最大値に等しくなり、その後、これら3つのタイプのキャンディーを順番に食べます。


補足

 

タイプXという表記は面倒なため赤・青の2色の(包装のある)キャンディーに例えてみる

 

YESの場合

(1)赤=青=3

赤→青→赤→青→赤→青

もしくは

青→赤…青→赤

(2)赤=青+1→赤=3 青=2

赤→青→赤→青→赤

先に多い方を食べて次を少ない方にするといい

NOの場合

(3)赤=青+2→赤=4 青=2

赤→青→赤→青

と(2)対応で上手くいきそうだが残っているのは赤が二つなので赤→赤にならざるを得ない。

尚、2以上になっても青を使い切った後残ったのは複数の赤になるためNOになる。

最大の数と、二番目に最大な数で2以上になる場合はNOになる。

赤 = 2 , 青= 6, 黄色 = 5 の場合

一番多い青を赤に合わせるまで青→黄を繰り返す

青 → 黄 → 青→ 黄 → 青 → 黄→青 →黄→青

すると、赤 = 2 , 青=2 ,黄 =1になるのでそこで赤を挟む

赤→青→黄→赤→青とすれば良い

 

1657B XY Sequence

この戦略が合計を最大化することを証明することも難しくありません。

矛盾することにより、最適な答えに a_{i-1} + x \leq Bであるが a_{i}= a_{i-1} -yであるインデックス iがあるとします。

 a_{j} = a_{j}−1 + xである最初の位置 j \geq iを見つけて、iとjの間で操作を交換しましょう。

その結果、 B \geq a_{i},a_{i+1},\cdot \cdot \cdot ,a_{j} [i,j-1] からのすべての a_{i}が増加しましたが、 a_{j}は同じままでした。

 

ルールに違反することはなく、合計が増加します。結果これは矛盾します。

2022/3/3 1638B.Reverse

問題本文

Problem - 1638A - Codeforces

長さnの順列 p_{1},p_{2},...,p_{n-1},p_{n} が与えられます。 2つの整数 l,r(1 \leq l \leq r \leq n)を選択し、順列の部分列 [l,r]を逆にする必要があります。

順列は、 p_{1},p_{2},...,p_{l−1},p_{r},p_{r−1},...,p_{l},p_{r+1},p_{r+2},...,p_{n}になります。

最初の順列に対して正確に1つの逆演算を実行することによって取得できる、辞書式に最小の順列を見つけます。

同じ長さのaとbの2つの異なる順列の場合、最初の位置が異なる場合、aは辞書式順序でbよりも小さく、aの要素が小さいことに注意してください。

順列は、1からnまでの任意の順序のn個の異なる整数で構成される配列です。

たとえば、[2,3,1,5,4] は順列ですが、[1,2,2]は順列ではありません(2が配列に2回表示されます)。 [1,3,4] も順列ではありません(n = 3ですが、配列には4があります)。

入力各テストには、複数のテストケースが含まれています。

最初の行には、テストケースの数である単一の整数 t(1\leq t\leq 500)が含まれています。

テストケースの説明は次のとおりです。

各テストケースの最初の行には、順列の長さである単一の整数 n(1\leq n\leq 500)が含まれています。

各テストケースの2行目には、順列の要素であるn個の整数 p_{1},p_{2},...p_{n}  (1\leq pi \leq n)が含まれています。

出力テストケースごとに、取得できる辞書式順序で最小の順列を印刷します。

 

解答

 p_{i} p_{i}\neq iとなる最初の要素とします。

要素のプレフィックス p_{1} = 1,p_{2} = 2,...p_{i-1} = i-1の場合、すでに変更されているため、何も変更する必要はありません。

最小の辞書式順序ですが、その位置に p_{i}ではなくiを使用したいと思います。

解決策は、セグメント [i,j] を逆にすることです。ここで、 p_{j} = iです。

すべての k \prec iに対して p_{k} = kであるため、 i \prec jであることに注意してください。

したがって、すべての k \prec  iに対して p_{k}   \prec  p_{j} = iになります。

時間計算量:O(n)。

2022/02/26 1633B Minority(少数)

問題本文

Problem - 1633B - Codeforces

 

文字「0」と「1」のみで構成される文字列sが与えられます。

sの連続する部分文字列を選択し、その文字の厳密な少数派である文字のすべての出現箇所を部分文字列から削除する必要があります。

つまり、部分文字列内の「0」の量が「1」の量よりも厳密に小さい場合は、部分文字列から「0」の出現をすべて削除します。

「1」の量が「0」の量よりも厳密に小さい場合は、「1」の出現をすべて削除します。

数が同じ場合は、何もしないでください。

操作は1回だけ適用する必要があります。

削除できる文字の最大数はいくつですか?

入力

最初の行には、テストケースの数である単一の整数 t(1 \leq t \leq 10^{4})が含まれています。

各テストケースの唯一の行には、文字「0」と「1」のみで構成される空でない文字列sが含まれています。

sの長さは 2 \times 10^{5}を超えません。

すべてのテストケースでの文字列の全長sは、 2 \times 10^{5}を超えません。

出力テストケースごとに、1つの整数を出力します。

これは、操作を1回だけ適用した後に削除できる最大文字数です。

テストケースの説明

最初のテストケース「01」では、部分文字列「0」、「1」、または「01」を選択できます。

「0」 \Rightarrow「0」の量は1であり、「1」の量は0です。ここでは「1」は厳密な少数派であるため、出現するすべての部分文字列から削除されます。

ただし、0個あるので何も変わりません。

'1'についても同じです。

そして、「01」では、「0」と「1」のどちらも同じ 厳密な少数派ではありません。

したがって、何も変わりません。

したがって、文字を削除する方法はありません。

 

2番目のテストケース「1010101010111」では、部分文字列「10101010101」を選択できます。

5文字の「0」と6文字の「1」が含まれています。

「0」は厳密な少数派です。したがって、すべての「0」を削除できます。

同じ答えを生成する他の部分文字列が存在します。

3番目のテストケース「00110001000」では、部分文字列「011000100」を選択できます。

6文字の「0」と3文字の「1」が含まれています。

「1」は厳密な少数派です。したがって、すべての「1」を削除できます。

 

回答

https://codeforces.com/blog/entry/99539

 

可能な限り最大の答えを推定してみましょう。

最良の場合、文字列全体からすべて0またはすべて1を削除できます。

発生が最も少ない方が答えになります。

文字列内の0と1の量が異なる場合、この境界に到達するのは実際には簡単です。文字列全体である部分文字列を選択するだけです。

量が同じ場合、限界に達することは不可能です。

文字列全体を選択しても何も起こりません。

より小さな部分文字列を要求すると、答えが少なくなります。

答えを減らすことができる最小値は1です。

最後の文字を含まない文字列である部分文字列を選択すると、量の1つが1つ減ります。

これにより数が異なり、限界に達します。

全体的な複雑さ:テストケースごとに \Theta (| s |)

1633A. Div. 7

問題本文

Problem - 1633A - Codeforces

問題本文和訳

整数nが与えられます。

そのような方法でその中の最小桁数を変更する必要があります。

結果の数値には先行ゼロがなく、7で割り切れるということです。

それを行うための複数の方法、それらのいずれかを印刷します。

指定された数がすでに7で割り切れる場合は、 変更はありません。

入力最初の行には1つの整数t( 1\leq t \leq 990 )が含まれています。

これはテスト数です。

次に、テストケースが続きます。

各テストケースは、1つの整数nを含む1行で構成されます。(  10 \leq n \leq 999)。

出力テストケースごとに、先行ゼロなしで1つの整数を出力します。

また変更の結果(つまり、7で割り切れる数) 適用できる方法が複数ある場合は結果の数値をどれか出力します。

指定された数がすでに7で割り切れる場合は、それを印刷するだけです。

 

回答本文

Educational Codeforces Round 122 — Editorial - Codeforces

回答和訳

この問題には、さまざまな解決策を書くことができます。

ここでは、7番目の整数ごとに7で割り切れるという事実に依存しています。

つまり、結果が7で割り切れるように、nの最後の桁を変更する(または変更しない)方法が常にあるということです。

nがすでに7で割り切れる場合は、それを出力するだけです。

それ以外の場合は、いくつかの式を使用して、最後の桁を0から9に変更します。