イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

101. 今日解いた問題（2022.04.13）

AtCoder プログラミング

問題一覧

 

自分の解法など

D - Remainder Reminder

入力例 1 で考えてみます。観察すると、 K+1 \le b \le N であることが分かります。よって、この範囲でそれぞれ a が何通りあるか考えるのがよさそうです。

b で剰余がループすることを考慮して、 q = \lfloor \frac{N}{b} \rfloor 回は全体を取れてそれぞれ b - K 個適切な a が存在します。つまり、 q(b-K) 個足せます。余った分（ N - q(b-K)）が K 以上ある場合、ここから条件を満たすものだけ足します。

計算量は O(N) です。

 

F - Programming Contest

DP っぽいですが、 T \le 10^9 と制約が大きいので無理です。 N が小さいことに注目すると、全探索っぽいです。 A_i をそれぞれ解く・解かないの全探索が思い浮かびますが、 N \le 40 なので 2^N 個の状態が出てくることを考えると、これも不可能です。

ここで、探索範囲を限定できないか考えます。2 つの部分集合に分割してそれぞれの総和パターンを算出し、組み合わせから最終的な総和パターンを出してもよいと気付きます。つまり、半分全列挙の問題です。

実際、 2^{20} \simeq 10^6 で、部分集合の総和算出はこれを 2 回行うだけなので間に合います。部分集合内の要素に限定した総和集合の算出が O(2^{N/2}) です。こうしてできた 2 つの部分集合から元を 1 つずつ選んで足せば、最終的な総和パターンを列挙できます。今回は足して T 以下の最大値を探したいので、どちらかの部分集合をソートしておき、足して T 以下となる最大要素を二分探索で求めればよいです。

以上より、計算量は O(2^{N/2} \log 2^{N/2})、つまり O(N \cdot 2^{N/2}) です。

 

D - Base n

考察すると、条件を満たす最大の n を N とすると、 d + 1 \le n \le N なる n は全て条件を満たすことが分かります。また、 X \ge 1、 M \le 10^{18} なので、 n \le 10^{18} です。よって、 d + 1 \le n \le 10^{18} で二分探索して N を求めれば、 N - d が答えになります。計算量は O(|X| \log M) です。

…ただ、これだけだとこんなに高diffにはならないわけで、この問題は厄介な落とし穴が 2 点あります。

オーバーフローを考慮する

X を n 進法表記とみなしたときの値を愚直に算出しようとすると、オーバーフローが容易に発生します。頑張ってオーバーフローを検出するのも手ですが、 M を n 進法に変換して X と比較すると、除算しか発生しないのでオーバーフローを防げます。

問題をよく読む

これサンプルに無いの結構意地悪だと思うのですが、よく読むと「 n の種類数を求める」のではなくて「 X を n 進法表記とみなして得られる値の種類数を求める」問題となっています。

何進法でも 1 桁目は n^0 = 1 に対応するので、 |X| = 1 のとき得られる値の種類数は X \le M なら 1、そうでないなら 0 です。これだけ例外を書いておきます。

ちなみに、私は最後まで問題の誤読に気付けず、8回くらい WA を出したところで諦めてテストケースを見に行きました。そして、 (X, M) = (1, 10^{18}) のテストケースで考えていた解と異なる値が想定されているのに気付き、唖然としました。

100. AtCoder参加記録（AtCoder Beginner Contest 247）

プログラミング AtCoder

14回参加でレート 1014 です。ようやくレート補正期間が終わりました。

 

f:id:ibako_piyo:20220411000301p:plain

f:id:ibako_piyo:20220411000331p:plain

 

 

今回はパフォーマンス 1173 です。

ABCDを通して、EFGExは未解答です。初めて？のノーペナ。

f:id:ibako_piyo:20220410232448p:plain

 

 

各問題の感想など。

A

S_{i + 1} \leftarrow S_{i} としたあと S_1 \leftarrow 0。

 

B

問題をパッと見てとりあえず Dictionary 使うっぽいな～、と思いながら手癖で姓名を突っ込みました。ただ、ここで「あれ、適切なあだ名の探索って難しくないか？取ったあだ名の分は Dictionary から引く必要があるのでは？全探索も無理じゃん」となって、だいぶ悩みました。

問題文をよく読むと、「あだ名同士が被らないようにする」のではなくて「あだ名が他人の姓名と被らないようにする」だったので、自分の姓名それぞれについて他人の姓名どちらかに存在するかチェックして、両方とも存在すれば No なだけでした。

周りも誤読勢が多かったみたいですが、なんだか妙に読みにくい問題文でしたね。

 

C

最近この手の問題解いたな…と思いつつ。

ただ、制約が小さいので前回解いたものより簡単です。

配列やリストで処理するのは面倒なので、文字列で S_1 から順に構成していきました。

 

D

パッと見で、Queue か…と。

ただ、愚直にやると c の制約が大きいので間に合いません。なので、ボールの種類 x とその数 c を 1 クエリごとに 1 つ突っ込むことにしました。後は取り出すときに Peek の c を見て、適切に処理するだけです。

 

E

しゃくとり法で良くない？と第一印象。

それは合っていたのですが、どのように遷移させるのかを上手く整理できなくて、サンプルが合わず無念の未提出。70分もあったのに…。

 

F

割となんとかなりそうな匂いがしましたが、Eの方が見込みがありそうだったので捨てました。

 

G,Ex

見てないです。

 

 

正直、今回のEは通したい問題でした。昨日のARCもそうですが、自分の弱点ってこれだと思うので、ちょっと意識していきたいですね…

 

99. AtCoder参加記録（AtCoder Regular Contest 138）

プログラミング AtCoder

現状です。13回参加でレート 992 です（14回参加するまでレート補正期間中）。

ARCデビュー戦は惨敗でした。

 

f:id:ibako_piyo:20220409233827p:plain

f:id:ibako_piyo:20220409234055p:plain

 

今回はパフォーマンス 845 で、なかなかやらかしています（ワースト2）。

Aを通して、BはWAで、CDEFは未解答です。Aで3ペナです（ひどい）。

f:id:ibako_piyo:20220409234309p:plain

 

各問題の感想です。

A

とりあえず K+1 項め以降に K 項めまでの最小値（ m とします）より大きい値がないとダメだな、と問題を整理。ここから、最も K 項めに近い、 m より大きい値を持って来ればよさそう？と考えました。

色々パターンを考えて、結局、 A_i (i \le K), A_j (j \gt K) で A_i \lt A_j を満たすペアを全て見て、 j - i の最小値が答えになると分かりました。愚直にやるのは無理なので、各 A_i (i \le K) について A_i 以下の値があるインデックスの最大値を Dictionary に保存し、MultiSet で A_i 集合を記録して、 A_j(j \gt K) について UpperBound から A_j 未満のキーを取得し、上記 j - i の値を求めて最小値を出せば O(N \log N) で答えを出せます。

…ということに開始15分くらいで気付いていたのですが、太文字にした「以下の」最大値を保存するという処理が抜けていて、WAの原因が分からず完全に焦ってしまいました。

結局、40分くらいで諦めてB問題に移りました。

そして、B問題を諦めてから戻ってきたときにバグに気付き、かなり焦りながら修正してなんとか105分で通しました（ひどい）。

 

B

Aでやらかした焦りから完全に見当外れな解き方を試みていました。Aをなんとか通してから戻ってみると、素直に（？） A を1手ずつ戻していけば解けそうでは…？と気付きましたが、時すでに遅しでした。

 

C, D, E, F

見てないです。

 

 

今回はかなり反省点の多いコンテストでした。普通に0完も見えていたので…。

  • 複雑なアルゴリズムになった場合、一度文章で整理してから実装に落とし込む方が無難
  • 変なバグらせ方してるなら早めに次の問題を見に行くべき
  • ちょっと焦りすぎ…

98. 今日解いた問題（2022.04.08）

プログラミング AtCoder

今日も仕事が忙しかったので軽いものを2つ。

ARC だからか、Diff にしてはやや難しい印象。どちらも発想問題でした。

 

問題一覧

 

自分の解法など

A - Permutation Grid

問題文を読むと、どうも作れる盤面は 1 通りに定まるようです。どのようにして決定できるのか考えてみます。

例 1 を見て、自分でマス目を書いてどのように塗っていくか考えます。まず、 R_i = 5, C_j = 5 に対応する行・列は全て黒です。次に、 R_i = 1, C_j = 1 に対応する行・列は先ほどの操作で黒が 1 つ存在するので、残りのマス目は白で確定します。すると、 R_i = 4, C_j = 4 に対応する行・列は白が 1 つ存在するので、残りのマス目を黒く塗ればよいことがわかります。

…と、 (n, 1, n-1, 2, n-2, 3, \dots) のような順で塗っていけば確定できることがわかりました。

ただし、これを愚直に書くと O(n^2) なので間に合いません。そこで、マス目に何らかの法則性がないか考えます。操作がシステマチックなので、何らか見いだせそうです。よく見ると、 R_i + C_j \gt n であるようなマス目 (i, j) は黒であることが分かります。よって、わざわざ盤面を再現せずともこれだけ見ればよいことがわかりました。

計算量は O(q) です。

 

 B - Shift and Reverse 

ゴールから考えてみます。

たとえば、長さ 4 の数列 (1, 2, 3, 4) を考えて、この 1 つ前の状態を考えます。それは (4, 1, 2, 3), (4,3,2,1) の 2 つです。さらにもう 1 つ状態を戻すと、既に出てきたものは除いて (3, 4, 1,2), (3,2,1,4), (1,4,3,2) です。さらに戻すと、 (2,3,4,1), (2,1,4,3) です。これ以上戻しても同じ状態しか出ないので、長さ 4 の数列で入力として与えられるのはこれらに限られます。

数列をじっくり観察しましょう。

  • 0手
    • (1, 2, 3, 4)
  • 1手
    • (4,1,2,3)
    • (4,3,2,1)
  • 2手
    • (3,4,1,2)
    • (3,2,1,4)
    • (1,4,3,2)
  • 3手
    • (2,3,4,1)
    • (2,1,4,3)

観察の結果、以下のようなことに気付きます。

  • 数列を前から順に見ていくと、 1 ずつ増える・減るのが基本で、どこかで 1 から n、あるいは n から 1 へと循環する。
  • 循環を考慮して、数列は昇順または降順になる。

…というわけで、 1 の場所と昇順・降順のパターンを考慮すると、実は状態数は 2n しかないです。そのため、枝刈り BFS で解ける問題です…が、そこまで気付いておきながら何故か違う方法で解きました。

 

目標は 1 が先頭にあり、かつ、昇順になっている状態です。そこで、以下のような戦略が有効そうだと分かります。

  • p_i = 1 なる i を考えて、 i \gt n - i + 1 であれば Reverse する

つまり、 1 を早く先頭に持ってきたいので、真ん中より右にいるならひっくり返した方が早いということです。

ただしこの考察は十分ではなく、元々の数列が昇順だった場合に Reverse 戦略を取ると、 i = 1 まで 1 を Shift させるだけではなく、もう一度 Shift した後さらに Reverse する必要があるため、元々降順だった場合と比べて 2 手多くかかります。よって、条件式も i \gt n - i + 3 と変わります。

 

さらに、実はこれでも不十分で、長さ 5 の数列で考えれば分かるのですが、 i = n - i + 1 かつ降順だった場合、Reverse から始めた方が手数が少なくなります。なぜなら、降順のまま Shift させると 1 を末尾まで持っていく分 1 手余分にかかるからです。

結局、以下のようなコードで答えを出せました。 1 の場所を見つける必要があるため、計算量は O(n) です。

 

// idx は 1 の場所(1-indexed)
// isReverse は元の数列が降順なら true
int ans = 0;
int revIdx = n - idx + 1 + (isReverse ? 0 : 2);
if (idx > revIdx || (idx == revIdx && isReverse))
{
    ans = 1;
    idx = n - idx + 1;
    isReverse = !isReverse;
}

if (isReverse) ans += idx;
else ans += idx - 1;

if (isReverse) ans++;

97. 今日解いた問題（2022.04.07）

プログラミング AtCoder

仕事がかなり大変だったので、比較的解きやすい2問だけ…。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

 

問題一覧

 

自分の解法など

A - Erase by Value

最適な戦略を考察します。

辞書順最小ということは、なるべく前方の文字を小さくできればよいです。よって、前から順に見て、その文字を消したとき次に現れる文字が小さくなるのであれば、その文字を消すのが最適です。

計算量は O(N) です。

 

B - Dividing Subsequence

倍数の Q における位置を高速に求める方法を考える

まず、 Q_j が P_i の倍数となるような j を高速に求める方法を考えます。

各整数が Q のどのインデックスに存在するか前計算を行います。ここでは Q_j \rightarrow j から生成される N 要素の配列 A を用意します。 Q が順列という制約があるので、このような配列は必ず作れます。

ある整数 m の倍数が Q のどのインデックスに存在するかは、 m の倍数を順に見て A から取得すれば O(N/m) で計算できます。操作としてはエラトステネスの篩と同じようなイメージです。 P の全ての要素についてこの計算を行うと、調和級数が出てくることを考慮して O(N \log N) であることが分かります。これは十分高速です。

このようにして作成した、整数 m の倍数が存在する Q のインデックスリストを D_{m, i} とします。

 

最長部分列の求め方を考える

P のインデックスを i、 Q のインデックスを j として (i, j) のペア集合 \{(i, D_{P_i, 1}), (i, D_{P_i, 2}), \dots\} を考えます。これは、問題の条件に合うインデックスのペア集合です。ここから適切な要素を選んで、最長部分列を求めたいです。これは最長増加部分列（LIS）の問題に似ていることに気付きます。

やりたいことは、このインデックスペア集合から以下の条件を満たすできるだけ大きな部分集合を得ることです。

  • 【1】同じ i を含まない
  • 【2】 i の昇順に並べると、 j について狭義単調増加になっている

ここが最大のポイントですが、LIS の問題に帰着させることを考えてみます。【2】の条件から、 j のみを並べて LIS を求めることを考えます。 i の昇順に並べたいので、 (D_{P_1, 1}, D_{P_1, 2}, D_{P_2, 1}, D_{P_3, 1}, D_{P_3, 2}, \dots) のような並べ方がよさそうです。ただし、何も考えず並べると【1】の条件を満たせなくなります。これは、 D_{P_i} を降順に並べることで解決できます。なぜなら、同じ i に対して降順に j が並んでいるので、最長増加部分列を取るアルゴリズムで同じ i から部分列を伸ばす操作が行われないからです。

 

わかりにくいので例 1 で考えます。 P=(3, 1, 4, 2), Q=(4, 2, 1, 3) です。このとき、 A=(3, 2, 4, 1), D_{1} = (1, 2, 3, 4), D_{2} = (1,2), D_{3} = (4), D_{4}=(1) です。これを LIS の問題に帰着させるための数列に置き直すと、 ( (4), (4,3,2,1), (1), (2,1) ) になります。なお、わかりやすくするため D_{i} ごとにカッコで括っていますが、実際は一次元配列です。ここから最長増加部分列を取ると、 i, j ともに狭義単調増加を満たすようなものが得られるとわかります。

要素数 O(N \log N) の数列に対して LIS のアルゴリズムを適用するので、計算量は O( (N \log N) \log (N \log N) ) です。ざっくり O( N (\log N)^2 ) と捉えた方が分かりやすそうです。

96. 今日解いた問題（2022.04.06）

プログラミング AtCoder

今日解いた問題についてまとめます。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

 

問題一覧

 

自分の解法など

A - Bridge and Sheets

最適な戦略を考察します。

たとえば、長さ 3 のシートで [0, 5] の部分を覆うことを考えます。全てを覆うことが要求されているため、いずれは左端にシートを置く必要があります。よって、とりあえず左端にシートを置くと [0, 3] の部分が覆われます。次に、同じように考えていずれは x=3 の場所にシートを置く必要があります。

このように考察すると、長さ l の連続する区間が覆われていないとき、シートは少なくとも \lceil \frac{l}{W} \rceil 枚必要であり、また、これが最適解です。

よって、既に存在する N 枚のシートを座標昇順に並べて、覆われていない区間の長さを算出して各部分に必要な最小シート枚数を算出し、足せば答えになります。ちなみに、この問題では予め a は座標昇順に並んでいるため、ソートする必要はないです（ソートしても間に合います）。

計算量は O(N) です。

 

B - Reserve or Reverse 

最適な戦略を考察します。

例 1 を見ます。a を 1 文字目に持って行きたいので、 x = (1, 3) としたいです。これ以上取れないので、結局これが最適解になります。

例 3 を見ます。a をなるべく前方に持って行きたいです。この例を見ると、後ろから順に見て a を貪欲に選択し、前から順に入れ替える戦略が有効そうです。今回はこの考え方がベースになります。

前方に持ってくる文字は a とは限りません（例 4 を見れば分かります）。どのように前方へ持っていく文字を決定するか考えます。

入れ替え操作をイメージすると、「現在入れ替え対象となってる前方の文字」と「現在確認している後方の文字」の間に「後方の文字」より小さいものが無ければ前方に持って行けばよいことが分かります（もし間に小さいものがあれば、それを前方に持ってくる方が辞書順は小さくなります）。ここでさらに考察すると、「前方の文字」が「後方の文字」より小さい場合は入れ替え操作をしない方がよいと分かります。

以上より、次のような操作で辞書順最小の文字列を作ることができると分かりました。

  1. 前方のインデックスを i、後方のインデックスを j として、 i = 1, j = N で初期化する。 c = 'a'（文字）とする
  2. i \ge j または c \ge 'z'（文字）なら終了
  3. s_k = c となる k (i \lt k \le j) が存在しないなら c \leftarrow c + 1 として 2. へ
  4. s_i \le c なら何もせず i \leftarrow i + 1 として 2. へ
  5. s_j = c なら s_i, s_j を入れ替えて i \leftarrow i + 1、 j \leftarrow j - 1として 2. へ
  6. j \leftarrow j - 1として 2. へ

ここで問題となるのは 3. の「間に文字が存在するか？」の判定です。ここを定数時間に落とすため、文字ごとに登場回数の累積和配列 A（長さ N）を取っておきます。 A_j - A_i = 0 であれば、 s_i から s_j の間にその文字は存在しないです。これによって、事前計算 O(N)、判定 O(1) が達成できます。

以上より、 O(N) で解くことができました。

 

C - The Majority

状況を上手く整理します。

とりあえず全ての箱に 1 のボールを少なくとも 1 つ入れておく必要があるため、そうしておきます。

その後、各箱において 1 のボールが過半数を維持するように他のボールを入れていくことを考えます。これは、 1 以外のボールを入れるとき、一緒に 1 のボールを入れてやることで達成できることが分かります。逆に、このような操作ができないと過半数は達成できません。

この操作で 1 以外の全てのボールを箱に入れて、なお 1 のボールが余っていた場合はどこに入れても良いです。これで全てのボールを箱に入れられました。

 

操作をまとめると、

  • 【0】 a_1 \lt K または \displaystyle a_1 - K \lt \sum_{i=2}^{N}a_i であるなら達成不可能（0 通り）
  • 【1】 1 のボールを、 K 個の箱に各 1 つずつ入れる
  • 【2】 i (2 \le i \le N) のボールを 1 つずつ、 1 のボールとペアにして任意の箱に入れる
  • 【3】 1 のボールが余っているなら、1 つずつ任意の箱に入れる

それぞれの操作が何通りあるかを式で表現すると、

  • 【1】1
  • 【2】 \displaystyle \prod_{i=2}^{N} {}_K H_{a_i}
  • 【3】 \displaystyle {}_K H_{a_1 - K - \sum_{i=2}^{N} a_i}

となります。ここで【2】の式について _{K} H_{a_i} = _{K + a_i - 1}C_{a_i} ですが、制約より K の方が上限が小さいので _{K+a_i-1}C_{K-1} とした方が計算量を落とせます。また、Combination の計算で出てくる除算は mod 逆元を利用します。

まとめると、

\displaystyle ans = ({}_K H_{a_1 - K - \sum_{i=2}^{N} a_i}) \times \prod_{i=2}^{N} {}_K H_{a_i}

が答えで、計算量は O(NK) です。

95. 今日解いた問題（2022.04.05）

プログラミング AtCoder

今日解いた問題についてまとめます。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

 

問題一覧

 

自分の解法など

A - Floor, Ceil - Decomposition

目的を達成するための最適な戦略を考察します。

x を \lfloor x/2 \rfloor, \lceil x/2 \rceil に書き換えると、積はどのように変化するでしょうか。大まかに見積もるため x/2 が 2 つ登場すると考えると、この部分の積は x^2/4 になります。よって、 x \gt 4 であれば書き換える、 x \lt 4 であれば書き換えない戦略が有効そうです。実際、 x = 5 など周辺値で確かめて、この仮説が正しいことが分かります。

よって、 X を書き換える操作を繰り返して得られる数を、全て 4 以下にしたあと積を取ると答えです。ただし、制約が大きいので単純にシミュレーションすると間に合いません。ここで、「値を半分に（近い値に）する操作を繰り返す」ということを考えて、同じような計算が多く登場することに注目すると、メモ化再帰で O(\log X) くらいに落とせることが分かります。

 

B - Sum of Three Terms

各項の関係を数式で表現することで考察します。

  • S_1 = A_1 + A_2 + A_3
  • S_2 = A_2 + A_3 + A_4

と並べてみると、 S_1 - S_2 = A_1 - A_4 であることが分かり、整理すると A_4 = A_1 - S_1 + S_2 です。同様に、以下のような式が導出できます。

  • A_4 = A_1 - S_1 + S_2
  • A_5 = A_2 - S_2 + S_3
  • A_6 = A_3 - S_3 + S_4
  • A_7 = A_4 - S_4 + S_5 = A_1 - S_1 + S_2 - S_4 + S_5

このように、 A の全ての項が最初の 3 項を用いて表現できることが分かりました。 S_i は入力から与えられるので定数として考えてよいです。よって、この問題は A_1, A_2, A_3 を決定する問題と読み替えることができました。もっと言えば、 A_3 = S_1 - A_1 - A_2 であり、 A_1, A_2 の 2 項を決める問題であると言い換えられます。

 

A_i \le 10^9 という暗黙の制約があるので、単純な探索は不可能です。ただし、 A の各項から A_1, A_2, A_3 の「差」を求めることはできています。任意の i について A_i \ge 0 を満たす必要があるため、最初の 3 項に対応する「差」の最小値を求めます。ここで見た項が 0 以上になればよいので、結局、

  • 「差」の最小値が非負であれば 0
  • 「差」の最小値が負であれば、その絶対値

とすれば、「全ての項が非負」という条件を満たす最小の A_1, A_2, A_3 を求められます。また、 A_3 = S_1 - A_1 - A_2 という制約を考えて、 A_1, A_2 はできるだけ小さな値を取ると、 A_3 を正にするという戦略において有利であることが分かります。よって、この条件で A_1, A_2 を決定するのが最善です。

最後に A_3 を計算し、負、または、対応する「差」の絶対値より小さければ適切な A を作れないことになります。それ以外の場合、「差」の情報を組み合わせて A を構築することができます。

 

まとめると、各項の「差」を求めるのに O(N)、初め 3 項の決定は定数時間、各項の構築は O(N) で達成できるので、全体として O(N) で解けます。