AtCoder Beginner Contest 234のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

またまた日が空きました。AtCoder Beginner Contest 234に参加です。

A - Weird Function (100点)

問題文にあるような関数を実装して、f(f(f(t)+t)+f(f(t)))を出力させればいいです。
また、f(f(f(t)+t)+f(f(t)))=4t^8+40t^7+216t^6+740t^5+1789t^4+3060t^3+3746t^2+2960t+1371 であるため、こちらを実装するのもありでしょう。
多項式の計算にはHorner法を用いることで累乗による計算回数を減らすことができます。

B - Longest Segment (200点)

点の個数が N \leq 100 と小さいため、全ての組 (i,\,j) (1 \leq i \lt j \leq N) についての線分の長さ \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} を計算して最大値を求めればいいです。
C++などの言語ではstd::fixed, std::setprecisionや"%.8d"などを用います。

C - Happy New Year! (300点)

0,\,2 を 0,\,1 に変換してもその大小関係は変わらないため、条件を満たす中で K 番目に小さい数は二進数表記での K に対応します。そのため十進数を二進数に変換し、1 を 2 に変換することで答えが求まります。

D - Prefix K-th Max (400点)

毎回、既出の数のリストから K 番目に大きな数を求めたり、ソートしたりすると計算量が O(N^2) や O(N^2 \log N) となってしまい、TLEします。
ある時点で大きい方から K+1 番目以降の数がそれ以降で答えになることはないため、各時点での大きい方から K 番目までの数が分かればいいです。よってこれらを集合std::setや優先度付きキューstd::priority_queueを用いて、毎回、この集合内の最小値と A_i の比較で大きい方を集合内にあるようにして要素数が常に K になるようにすれば、その中の最小値が各回の答えになり、全体として O(N \log N) になります。
コンテスト内では最初は、二重二分探索で O(N (\log N)^2) 解で通しましたが、探索範囲を間違えて2WA出してしまいました。

E - Arithmetic Number (500点)

一番左の数は 1 から 9 の 9 通り、公差は -9 から 8 の 18 通りであるため、これらを全探索することができます。各条件について右に数を増やしていき(増やす数がマイナスになればその条件については打切り)、X 以上になったら、答えの候補にして、その中の最小値が答えとなります。

F - Reordering (500点)

S 内の i 種目の英小文字の出現数を c_i とします。このとき

{\mathrm{dp}}_{i,j} = (\text{\(i\) 種目までの英小文字で作れる \(j\) 文字の文字列の数})
というDPを考えます。公式解説では貰うDPで考えているようでしたが、私は配るDPをもとに考えました。
{\mathrm{dp}}_{i,j} の状態について (i+1) 種目の英小文字を文字の隙間(前後含む) (j+1) 個の隙間に配置していきます。このとき同じ隙間に複数個おいてもよく、1個も置かれない隙間があってもいいです。初期状態
{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} 1 & (i = 0 \land j = 0)\\ 0 & (\mathrm{Otherwise}) \end{array} \right.
として 0 \leq k \leq c_{i+1} について {\mathrm{dp}}_{i+1,j+k} に {\mathrm{dp}}_{i,j} \times {}_{j+1}\mathrm{H}_{k} を足すことで答えが \displaystyle \sum_{j=1}^{N} {\mathrm{dp}}_{26,j} と求まります。ここで {}_{n}\mathrm{H}_{r} は重複組み合わせで {}_{n}\mathrm{H}_{r} = \displaystyle\binom{n+r-1}{r} = \frac{(n+r-1)!}{r!(n-1)!} であり、変形すると公式解説と同じ
{\mathrm{dp}}_{i,j} =\displaystyle \sum_{k=0}^{\min\{j,\,c_i\}} {\mathrm{dp}}_{i-1,j-k} \binom{j}{k}
となります。

G - Divide a Sequence (600点): 未提出

これもDPっぽいですが、未だ解けてません。

Ex - Enumerate Pairs (600点、実行時間制限: 4 sec): 未提出

計算量が落ちない...

結果、感想

f:id:Flkanjin:20220109131832p:plain
ちゃんと6完で来たので良かったという感じですが、Dで2WA出してしまったのが痛いなと、要反省です。

エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）参加!

A - Four Digits (100点)

999 以下なら先頭に0を追加して...という風にもできますが、やることはゼロ埋め4桁出力なので、printfやマニピュレータによるフォーマット出力で対応できます。

  • printf("%04d\n", N);
  • cout << setw(4) << setfill('0') << N << endl;

B - Failing Grade (200点)

for文を用いて各 i について a_i \lt P であるかを調べればいいです。

C - Swiss-System Tournament (300点)

各回毎に前の順位から今回の順位を求まられればいいです。
前回の順位で、上位からどのプレイヤーかが分かれば各試合する組み合わせが分かるので、各プレイヤーがその時点で何勝しているかが分かるので、それを勝数毎のバケツに入れて、各勝数について大きい順に、中のプレイヤーをインデックスの小さい順に取ってやれば、その試合の後の順位が上位から順に求まります。

D - Between Two Arrays (400点)

次のようなDPがまず思いつきます。

{\mathrm{dp}}_{i,j} = (\text{\(c_i = j\) であるような \(C\) の長さ \(i\) の接頭辞(prefix)の個数})
として、
{\mathrm{dp}}_{1,j}=\left\{ \begin{array}{ll} 1 & (a_1 \leq j \leq b_1)\\ 0 & (\mathrm{othrewise}) \end{array} \right.
において 2 \leq i \leq N について
{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} \displaystyle\sum_{k = 0}^{j} {\mathrm{dp}}_{i-1,k} & (a_i \leq j \leq b_i)\\ 0 & (\mathrm{othrewise}) \end{array} \right.
という遷移で答えが \displaystyle \sum_{k=0}^{\infty} {\mathrm{dp}}_{N,k} (範囲は a_N \leq k \leq b_N で十分) と求まりますが、このままでは M = \displaystyle\max_{1 \leq i \leq N} b_i として計算量が O(NM^2) となってしまうので間に合いません。
ここで \displaystyle\sum_{k = 0}^{j} {\mathrm{dp}}_{i-1,k} の部分について累積和を利用することで O(NM) にでき、これでACをとることができます。
また、
{\mathrm{dp}}_{0,j}=\left\{ \begin{array}{ll} 1 & (j = 0)\\ 0 & (\mathrm{othrewise}) \end{array} \right.
として遷移式を i=1 のときにも適応させることで場合分けや初期化を減らすこともできます。

E - Red and Blue Tree (500点)

各辺を通る回数の配列 p = (p_1,\,p_2,\,\dots,\,p_{N-1}) が求まれば、S = \displaystyle \sum_{i=1}^{N-1} p_i として部分和を \displaystyle \frac{K + S}{2} とするような要素の選び方の数としてDPなどで求まります。

このときのDPは

{\mathrm{dp}}_{i,j} = (\text{\(p\) の長さ \(i\) のprefixについて部分和を \(j\) とする場合の数})
として、
{\mathrm{dp}}_{0,j}=\left\{ \begin{array}{ll} 1 & (j = 0)\\ 0 & (\mathrm{othrewise}) \end{array} \right.
において 1 \leq i \leq N について
{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} {\mathrm{dp}}_{i-1,j} + {\mathrm{dp}}_{i-1,j-p_i} & (0 \leq j-p_i)\\ {\mathrm{dp}}_{i-1,j} & (\mathrm{othrewise}) \end{array} \right.
という遷移で答えを O(NS) = O(N^2M) で求めることができます。

p を求めるのは、DFS等で O(NM) で求めることができるので、全体として O(N^2M) で答えが求まりました。

F - Expensive Expense (500点、実行時間制限: 4 sec)

制約より与えられたグラフは木であることが分かります。全方位木DPで答えは求まるそうですが、私は書けないです。ここでコンテスト終了後に直径を利用する解き方でACしました。

もともとの木に頂点 1',\,2',\,\dots,\,N' と 1 \leq i \leq N の各 i について頂点 i と i' を結ぶコスト D_i の辺を追加します。この追加後も木の儘です。頂点 u,\,v 間の距離を \mathrm{dist}(u,\,v) と書きます。また、a=\{1,\,2,\,\dots,\,N\}, a'=\{1',\,2',\,\dots,\,N'\} とします。

ここで頂点の組 (s,\,t) が直径をなす、即ち \mathrm{dist}(s,\,t) = \displaystyle\max_{u,v \in a \cup a'} \mathrm{dist}(u,\,v) であるように取ります。このとき任意の頂点 v について \displaystyle \max_{u \in a \cup a'} \mathrm{dist}(u,\,v) = \max\{\mathrm{dist}(v,\,s),\,\mathrm{dist}(v,\,t)\} が成立します。

先ずはこれを証明します。
\mathrm{dist}(a,\,b) \gt \max\{\mathrm{dist}(a,\,s),\,\mathrm{dist}(a,\,t)\} となるような頂点の組 (a,\,b) が存在すると仮定します。このとき、a も b も s や t でないことは自明です。また、s - t のパス上で a から最も近い点を c とすると \mathrm{dist}(s,\,t) = \mathrm{dist}(a,\,s) + \mathrm{dist}(a,\,t) - 2\mathrm{dist}(a,\,c) となります。

  • a-b と s-t の2つのパスが交わらない場合:

\mathrm{dist}(s,\,b) = \mathrm{dist}(s,\,a) + \mathrm{dist}(a,\,b) \gt \mathrm{dist}(a,\,s) + \mathrm{dist}(a,\,t) \geq \mathrm{dist}(s,\,t) より \mathrm{dist}(s,\,t) が直径であることに反します。

  • a-b と s-t の2つのパスが交わる場合:

s,\,t のうち、b に近い方が t であるように仮定します(そうでない場合は s,\,t を入れ替える)。このとき \mathrm{dist}(s,\,b) = \mathrm{dist}(s,\,a) + \mathrm{dist}(a,\,b) - 2\mathrm{dist}(a,\,c) \gt \mathrm{dist}(a,\,s) + \mathrm{dist}(a,\,t) - 2\mathrm{dist}(a,\,c) = \mathrm{dist}(s,\,t) となりこちらでも \mathrm{dist}(s,\,t) が直径であることに反します。

よってこの二つより、背理法により示したことが示されました。
ここまで来れれば、double-sweep等によって (s,\,t) を求め、1 \leq i \leq N の各 i について \max\{\mathrm{dist}(s,\,i),\,\mathrm{dist}(t,\,i)\} を求めればよいと思ってしまいますが、最初の街では観光しないので、例えば s = i' のときは \max\{\mathrm{dist}(s,\,i),\,\mathrm{dist}(t,\,i)\} ではなく \mathrm{dist}(t,\,i) が答えとなります。

この解き方では4つの始点について最短距離を求めるので O(N \log N) や O(N) で求めることができます。

G - 222 (600点): 未提出

数式こねくり回したら出来そう

H - Beautiful Binary Tree (600点、実行時間制限: 3 sec): 未提出

難しそう

結果、感想

f:id:Flkanjin:20211010110902p:plain
ちゃっと増加してよかったなっていう感じですが、時間内にFも通したかったなと、ちゃんと精進しないといけないねと思わされました。

AtCoder Beginner Contest 221のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

久しぶりの更新です。AtCoder Beginner Contest 221に参加です。

A - Seismic magnitude scales (100点)

答えは 32^{A-B} となります。powなどを用いてもこの問題ではOKですが、場合によっては誤差が発生しうるのでfor文を使うのが無難と思いそちらで組みました。

B - typo (200点)

問題文の通り、何も操作を行わないとき、i 文字目と i+1 文字目を入れ替えたとき、それぞれについて一致するかどうかを調べることで解けます。
実装的には各 i についてi 文字目と i+1 文字目を入れ替えたときと戻した時を判定すれば、何も操作を行わないときについて別個に書く必要がなくなるので、コードは短くなりますね。

C - Select Mul (300点)

N の各桁の数字を任意の順番に並べて、その先頭の数と、後ろの数と見做すことで全ての分離方法を考えることができ、その方法は N の桁数を n とするとき O(n!n) 通りあり、計算量も O(n!n) となります。
ここで、各分離方法について、それぞれの数字を降順にソートした方が答えが大きくなるため、各数字を2つのグループのどちらかに所属するかの 2^n 通りのみの分離方法のみ調べる必要性があることになります。これはbit全探索を用いて計算量 O(2^nn) で実装できます。
本番では後者の方法がすぐ思い浮かんだので、そちらでのみ実装しました。
どうやら O(n) 解 や O(n \log n) 解があるようですが、こんなの本番中に思いつけへんやん...

D - Online games (400点)

全ての日について考えると最大で 2 \times 10^9 日目まで考える必要があるので、間に合いません。人数の変動があるのは各 i について A_i 日目と A_i + B_i 日目なので、その節目で人数が何人になって、その間隔が何日なのかを計算することで答えを求めることができます。
本番では間隔の前後を間違えて1WAしました。

E - LEQ (500点)

A^{'}_1 が A_i, A^{'}_k が A_j であるような部分列の個数は A_{i+1},\,A_{i+2},\,\dots,\,A_{j-1} のそれぞれを選ぶかどうかの 2^{j-i-1} 通りであるため、求める答えは \displaystyle \sum_{\substack{1 \leq i \lt j \leq N \\ A_i \leq A_j}} 2^{j-i-1} です。
2^{j-i-1} = \dfrac{2^j}{2^{i-1}} であるため A^{'}_1 として A_i を選んだ時、i \lt j \leq N, A_i \leq A_j となるような j について 2^j を足していき、2^{i-1} で割ることでこのときの部分列数が求まります。よってこれを全ての i について足していけばいいことができます。
これは A_1,\,A_2,\,\dots,\,A_N について 1,\,2,\,\dots,\,2^{N-1} という重みを付けた個数のセグ木について添え字の降順に走査することで実装することができますが、A_i の値が 10^9 程度になることにもなるため座標圧縮してやる必要があります。
本番ではセグ木の演算でmodをとらせるということをしていなかったため1WA出してしまいました。

F - Diameter set (500点)

木の直径はdouble sweep によって求めることができます。そこから木の中心 c を求めますが、この時、直径の偶奇で場合分けをしますが、各辺上に頂点を追加してやることで、直径を2倍にし、偶数にすることができ、この直径を 2d とします。
この木を c を根とする根附き木として、c の直接の子を k_1,\,k_2,\,\dots,\,k_n として、c 以外の点をそれぞれどの k_i の子孫(または k_i 自身)であるかでグループ分けします。各グループについて c からの距離が d であるような点の個数を m_i とします。条件を満たす点の選び方は各グループについて距離 d の点を高々1つづつ選んでいき、かつ選んだ個数が 2 以上のものであるため、\displaystyle \prod_{i = 1}^{n}(m_i+1) - \sum_{i=1}^{n}m_i -1 通りとなります。

本番ではグループを高々2つまでしか考えてなくて爆死しました。

G - Jumping sequence (600点、実行時間制限: 5 sec): 未提出

何かしら圧縮してDPなんやろうなぁと思ってます。

H - Count Multiset (600点): 未提出

DPなのかな

結果、感想

f:id:Flkanjin:20211003114315p:plain
8問ABCになってから調子悪かったのですが、久しぶりに良いパフォが取れました。このまま1700まで恢復していきたいですね。

Codeforces Round #737 (Div. 2)のきろく

Codeforces 競技プログラミング Codeforces Div. 2 参戦記 インタラクティブ問題

久しぶりのCodeforces＆参戦録です。レート冷えなくてなんとか安心したっていう感じです。問題文和訳はこちら

A. Ezzat and Two Subsequences / Ezzat и две подпоследовательности (500点)

最大値の影響を大きく、最小値の影響を小さくしたいので、最大値を少ない方の部分列に、最小値を多い方の部分列にもっていければいいかなと思いました。公式解説によると、最大値とそれ以外で分ければいいようですが、本番は証明できず、少し怖かったので配列をソートして、b_1,\,b_2,\,\dots,\,b_n として、\displaystyle\max_{i=1}^{n-1}\left\{\frac{1}{i}\sum_{j=1}^i a_j + \frac{1}{n-i}\sum_{j=i+1}^{n} a_j\right\} を出力することにしました。

B. Moamen and k-subarrays / Moamen и k-подотрезки (1000点)

k=l (1 \leq l \lt n) でソートできる場合、k = l+1 では要素数が 2 以上の連続部分列を分割すれば、同様にソートすることができるので、ソートできる最小分割数を求めればいいことが分かります。

a_i,\,a_{i+1} についてソート後においても連続する (b_j,\,b_{j+1} みたいな感じ) ときは同一連続部分列に属すようにしてもいいですが、そうでない場合は違う連続部分列に属すようにしなければなりません。よって連続部分列の最小数は、ソート後においても連続するような部分列の数となります。

C. Moamen and XOR / Moamen и XOR (1750点)

桁DPです。

{\mathrm{dp}}_{i,j} = (\text{上位 \(i\) 桁について(\(j\) ? 両辺が等しい : 左辺が大きい) 場合の数})
とすると、
{\mathrm{dp}}_{0,j}=\left\{ \begin{array}{ll} 0 & (j = \mathrm{false})\\ 1 & (j = \mathrm{true}) \end{array} \right.
です。

各桁について数字の選び方は 2^n 通りです。上位桁で左辺の方が大きいことが決まっている場合、下位については任意の選び方で左辺の方が大きくなります。

n が奇数のときは、bitAND が 1 となる、全てが 1 のときはbitXORも 1 であり、bitANDもbitXORも 0 となるのは偶数個のみが 1 であるときで、{}_n{\mathrm{C}}_0 + {}_n{\mathrm{C}}_2 + \dots + {}_n{\mathrm{C}}_{n-1} = 2^{n-1} 通りであるので

{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} 2^n{\mathrm{dp}}_{i-1,\mathrm{false}} & (j = \mathrm{false})\\ (2^{n-1}+1){\mathrm{dp}}_{i-1,\mathrm{true}} & (j = \mathrm{true}) \end{array} \right.
となります。
n が奇数のときは、bitAND が 1 となる、全てが 1 のときはbitXORは 0 であり、bitANDもbitXORも 0 となるのは偶数個のみが 1 であるときで、{}_n{\mathrm{C}}_0 + {}_n{\mathrm{C}}_2 + \dots + {}_n{\mathrm{C}}_{n-2} = 2^{n-1}-1 通りであるので
{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} 2^n{\mathrm{dp}}_{i-1,\mathrm{false}}+{\mathrm{dp}}_{i-1,\mathrm{true}} & (j = \mathrm{false})\\ (2^{n-1}-1){\mathrm{dp}}_{i-1,\mathrm{true}} & (j = \mathrm{true}) \end{array} \right.
となります。

Ezzat and Grid / Ezzat и таблица (2500点): 未提出

分かりません...

E. Assiut Chess / Шахматы в Assiut (3000点): 未提出

コンテスト中には、問題文すら見ていませんでした...

結果、感想

f:id:Flkanjin:20210812021015p:plain
久しぶりの参戦でレートを温めることができて嬉しいです。このまま紫になりたいなぁ。

Codeforces Round #737 (Div. 2) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 インタラクティブ 和訳 Codeforces Div. 2 和訳

A. Ezzat and Two Subsequences / Ezzat и две подпоследовательности (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Ezzat(عزت)*1は n 個の整数(負の可能性もあり)から成る配列を持っています。彼はこの配列の各要素が正確に1つの部分列に属し、f(a) + f(b) の値が可能な限り最大となるように、空でない2つの部分列に分割したいと思っています。ここで、f(x) は部分列 x の平均を表します。

数列 y からいくつか(0個や全ての場合もあり)を削除することで数列 x が得られるとき、x は y の部分列であるといいます。

部分列の平均とは、この部分列の数値の合計を部分列の大きさで割ったものです。

例えば、[1,\,5,\,6] の平均は \displaystyle \frac{1+5+6}{3} = \frac{12}{3} = 4 であるため、f([1,\,5,\,6]) = 4 となります。

入力

1行目には単一の整数 t (1 \leq t \leq 10^3) が与えられる、これはテストケース数である。各テストケースは2行から成る。

各テストケースの1行目には単一の整数 n (2 \leq n \leq 10^5) が与えられる。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (-10^9 \leq a_i \leq 10^9) が与えられる。

全てのテストケースでの nの和が 3 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、単一の値を出力せよ、その値とはEzzatが達成できる最大値である。

絶対誤差または相対誤差が 10^{-6} を越えなければ正解と見做される。

形式的には、提出解を a、ジャッジ解を b とする。\displaystyle \frac{|a-b|}{\max\{1,\,|b|\}} \leq 10^{-6} であるとき、正答とみなされる。

入出力例

4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3
4.500000000
-12.500000000
4.000000000
18.666666667

注記

1つ目のテストケースでは、配列は [3,\,1,\,2] です。この配列を分割する全ての方法は次のようなものです。

  • a = [3], b=[1,\,2]。このとき値は f(a) + f(b) = 3 + 1.5 = 4.5 となる
  • a = [3,\,1], b=[2]。このとき値は f(a) + f(b) = 2 + 2 = 4 となる
  • a = [3,\,2], b=[1]。このとき値は f(a) + f(b) = 2.5 + 1 = 3.5 となる

従って、可能な最大値は 4.5 となります。
2つ目のテストケースでは、配列は [-7,\,-6,\,-6] です。この配列を分割する全ての方法は次のようなものです。

  • a = [-7], b=[-6,\,-6]。このとき値は f(a) + f(b) = (-7) + (-6) = -13 となる
  • a = [-7,\,-6], b=[-6]。このとき値は f(a) + f(b) = (-6.5) + (-6) = -12.5 となる

従って、可能な最大値は -12.5 となります。

B. Moamen and k-subarrays / Moamen и k-подотрезки (1000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Moamen(مؤمن)*2は異なる n 個の整数から成る配列を持っています。彼は次の操作を順番に正確に1回行うことで、この配列を非減少順に並び替えたいと考えています。

  1. 各要素が正確に1つの連続部分列に属すように、配列をちょうど k 個の空でない連続部分列に分割する
  2. これらの部分配列を任意に並び替える
  3. 新しい順序で部分配列を結合する

数列 b の先頭からいくつか(0個や全ての場合もあり)の要素を削除し、末尾からいくつか(0個や全ての場合もあり)の要素を削除することで数列 a が得られるとき、a は b の連続部分列であるといいます。

上記の操作を正確に一度だけ行って、配列を非減少順に並び替える方法があるかどうか、Moamenに教えてください。

入力

1行目には単一の整数 t (1 \leq t \leq 10^3) が与えられる、これはテストケース数である。テストケースについての記述が続く。

各テストケースの1行目には2つの整数 n,\,k (1 \leq k \leq n \leq 10^5) が与えられる。

2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq |a_i| \leq 10^9) が与えられる。全ての数が相異なることは保証されている。

全てのテストケースでの nの和が 3 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、単一の文字列を出力せよ。

Moamenが配列を非減少順に並び替えることができる場合、"YES"(引用符なし)と出力せよ。そうでなければ、"NO"(引用符なし)と出力せよ。

"YES"と"NO"の各文字はどの活字ケース(大文字/小文字)で出力してもよい。

入出力例

3
5 4
6 3 4 2 1
4 2
1 -4 0 -2
5 1
1 2 3 4 5
Yes
No
Yes

注記

1つ目のテストケースでは、a = [6,\,3,\,4,\,2,\,1], k = 4 であり、次のように操作を行うことができます。

  1. a を \{[6],\,[3,\,4],\,[2],\,[1]\} に分割する
  2. 並び替える: \{[1],\,[2],\,[3,\,4],\,[6]\}
  3. 結合する: [1,\,2,\,3,\,4,\,6]. これで配列はソートされた

2つ目のテストケースでは、配列を 2 つの連続部分列に分割してソートを行う方法はありません。

例えば、配列を \{[1,\,-4],\,[0,\,-2]\} に分割した場合、\{[1,\,-4],\,[0,\,-2]\} または \{[0,\,-2],\,[1,\,-4]\} のようにしか並び替えることができません。しかし、どちらの場合も、結合後の配列はソートされていません。

C. Moamen and XOR / Moamen и XOR (1750点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Moamen(مؤمن)とEzzat(عزت)がゲームをしています。彼らは、各要素が 2^k より小さいような、n 個の非負整数から成る配列 a を作ります。

a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n である場合、Moamenが勝ちます。

ここで \& はbit単位AND*3を、\oplus はbit単位XOR*4を表します。

Moamenが勝つような配列 a の個数を計算してください。

結果は非常に大きくなる可能性があるため、1\,000\,000\,007 (10^9+7) で割った値を出力してください。

入力

1行目には単一の整数 t (1 \leq t \leq 5) が与えられる、これはテストケース数である。

各テストケースは2つの整数 n,\,k (1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 2 \cdot 10^5) を含む1行で構成される。

出力

各テストケースについて、単一の値を出力せよ、その値はMoamenが勝つような配列の個数である。

結果を modulo 1\,000\,000\,007 (10^9+7) で出力せよ。

入出力例

3
3 1
2 1
4 0
5
2
1

注記

1つ目のテストケースでは、n = 3, k = 1 です。結果として、可能な配列は [0,\,0,\,0], [0,\,0,\,1], [0,\,1,\,0], [1,\,0,\,0], [1,\,1,\,0], [0,\,1,\,1], [1,\,0,\,1], [1,\,1,\,1] で全てです。

Moamenはそのうち5つでのみ勝利します: [0,\,0,\,0], [1,\,1,\,0], [0,\,1,\,1], [1,\,0,\,1], [1,\,1,\,1]。

D. Ezzat and Grid / Ezzat и таблица (2500点)

テストごとの時間制限: 2.5秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Moamen(مؤمن)は 0 と 1 の数字だけを含む n 行 10^9 列のグリッドを描いていました。Ezzat(عزت)はMoamenが描いているものに気付き、グリッドを美しくするために削除する必要のある行の最小個数に興味を持ちました。

グリッドの全ての連続する2行について、この2行に 1 を持つような列が少なくとも1つ存在する場合、かつその場合のみグリッドは美しいといいます。

Ezzatは行数 n と、数字 1 を含むグリッドの m 個のセグメントを与えます。 各セグメントは3つの整数 i,\,l,\,r で表され、i は行番号を、l,\,r はその行のセグメントの最初と最後の列を表します。

例えば、n = 3, m = 6 で、セグメントが (1,\,1,\,1), (1,\,7,\,8), (2,\,7,\,7), (2,\,15,\,15), (3,\,1,\,1), (3,\,15,\,15) であるとき、グリッドは次のようになります。

\begin{align*}10000011000000000\dots\dots\dots\dots\\00000010000000100\dots\dots\dots\dots\\10000000000000100\dots\dots\dots\dots\end{align*}

グリッドを美しくするために削除しなければならない最小の行数をEzzatに伝えてください。

入力

1行目には2つの整数 n,\,m (1 \leq n,\,m \leq 3 \cdot 10^5) が与えられる。

続く m 行のそれぞれには3つの整数 i,\,l,\,r (1 \leq i \leq n, 1 \leq l \leq r \leq 10^9) が与えられる。これら m 行のそれぞれは行番号 i は l 列目から r 列目(両端含む)までに数字 1 を含んでいることを表す。

セグメントは重なることもあることに注意せよ。

出力

1行目には単一の整数 k を出力せよ、これは削除しなければならない最小の行数である。

2行目には削除しなければならない行を表す k 個の相異なる整数 r_1,\,r_2,\,\dots,\,r_k (1 \leq r_i \leq n) をいずれかの順序で出力せよ。

解が複数ある場合は、そのいずれかを出力せよ。

入出力例

3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15
0
5 4
1 2 3
2 4 6
3 3 5
5 1 1
3
2 4 5

注記

1つ目のテストケースのグリッドは問題文で説明されているものです。このグリッドは次のような特性を持っています。

  1. 1 行目と 2 行目は列 7 に共通して 1 を持つ
  2. 2 行目と 3 行目は列 15 に共通して 1 を持つ

結果として、このグリッドは美しく、どの行も削除する必要はありません。
2つ目のテストケースでは、グリッドは次のようになります。

\begin{align*}01100000\dots\dots\dots\dots\\00011100\dots\dots\dots\dots\\00111000\dots\dots\dots\dots\\00000000\dots\dots\dots\dots\\10000000\dots\dots\dots\dots\end{align*}

E. Assiut Chess / Шахматы в Assiut (3000点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
これはインタラクティブ問題です。

ICPC Assuit(أسيوط)*5 コミュニティ(以下、ICPC Assiut Community)がユニークなチェスの大会を開催することとなり、貴方はクイーンを操って隠れたキングを追い詰める役に選ばれました。キングはICPC Assiut Communityのメンバーがキングを操ります。

8 \times 8 のチェス盤上で対戦を行い、行は上から下へ、列は左から右へと数字が振られていて、x 行 y 列にあるマスは (x,\,y) と表されます。

1手でクイーンを同一横線上、縦線上、斜線上のいずれかのマスに移動させることができます。例えば、クイーンが (4,\,5) にあった場合、(q_1,\,5), (4,\,q_1)*6, (q_1,\,9 - q_1), (q_2,\,q_2+1) (1 \leq q_1 \leq 8, q_1 \neq 4, 1 \leq q_2 \leq 7, q_2 \neq 4) のいずれかに移動できます。クイーンは現在のマスに留まることはできないことに注意してください。

f:id:Flkanjin:20210810153104p:plain

1手でキングは盤面から出ないように「右」「左」「上」「下」「右下」「左下」「左上」「右上」のいずれかに移動できます。キングはクイーンと同じ行、列、斜線上にあるマス(クイーン自身がいるマスを含む)に移動することはできません。例えば、キングがマス (4,\,5) にいた場合、(4+k_1,\,5+k_2) (-1 \leq k_1,\,k_2 \leq 1, (k_1,\,k_2) \neq (0,\,0)) に移動することができます。
f:id:Flkanjin:20210810153934p:plain

ゲーム開始時に、クイーンを盤上の任意のマスに配置し、これはゲーム注意回のみ行われます。その後、クイーンとは異なる位置にキングが秘かに置かれます。貴方にはキングの位置は分かりません。その後、キングを先手として、キングとクイーンが交互に手を打ちます。キングは可能な方向(「右」「下」「上-左」など)に動き、その方向のみが貴方に伝えられます。そののち、クイーンが移動するマスを宣言し、クインを移動させなければなりません。このようにしてゲームは、貴方が勝つか、手番がなくなるまで続きます。

キングに有効な手がなくなれば貴方の勝ちです。130 回クイーンを動かした後もキングに有効な手があれば、貴方の負けです。

入力

1行目には単一の整数 t (1 \leq t \leq 60) が与えられる、これはテストケース数である。

相互入出力

各テストケースにおいて、クイーンの開始位置を直ちに出力せよ。キングのいるマスにクイーンを置いた場合、直ちに勝利する。

その後、最大で 130 手を打つことができる。各手は x\ y という形式で行われる、ここで x,\,y (1 \leq x,\,y \leq 8) はそれぞれクイーンの亜tらしい行と列を表す2つの整数である。この手はクイーンの有効な手でなければならない。

最初のクイーンの配置の後や自分の手の後、キングの移動方向を表す文字列 s を受け取る。これは次のうちのいずれかである: "Right", "Left", "Up", "Down", "Down-Right", "Down-Left", "Up-Left", "Up-Right"、もしくは勝利時の"Done"。"Done"は各テストケースの終わりとして考えよ。

クエリを出力した後、忘れず改行を出力し、出力をflushせよ。そうでなければIdleness limit exceededを得る。出力のflushのためには、次を利用せよ。

  • C++の場合、fflush(stdout)やcout.flush()
  • Javaの場合、System.out.flush()
  • Pascalの場合、flush(output)
  • Pythonの場合、stdout.flush()
  • 他の言語の場合は、ドキュメントを参照せよ

無効なクエリを出力したり、各テストケースで 130 個を超えるクエリを出力しようとした場合、ゲームは直ちに終了し、Wrong Answer判定となる。

入出力例

1
Left
Right
Done
7 5
7 6
7 7

注記

この入出力例では、開始時に隠れキングは (8,\,8) にいました。ゲームは次のように続きます。f:id:Flkanjin:20210810161649p:plainf:id:Flkanjin:20210810161701p:plain

*1:このラウンドのWriterであるAhmedEzzatGさんに由来すると思われる。単語としてはペルシャ語などで名誉や尊敬などの意味を持つ。ここでは人名

*2:アラビア語などで信者などを表す語。ここでは人名

*3:原文では英語、ロシア語のWikipediaへのリンク

*4:こちらも原文では英語、ロシア語のWikipediaへのリンク

*5:アシュート、エジプトの都市

*6:正確には(4, q_3) (1 ≤ q_3 ≤ 8, q_3 ≠ 5)

AtCoder Beginner Contest 204のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 204で久しぶりにレート上昇しました!

A - Rock-paper-scissors (100点)

3 人のじゃんけんであいこになるのは、全員同じ手を出すか、全員違う手を出した時なので、 x = y のときはその手、そうでないときは 3-x-y の手を出せばいいです。また、サーバルの出した手に対応する文字を z としたとき、x + y + z \equiv 0 \pmod 3 となることを利用すると z = (6 - x - y) \bmod 3 となります。

B - Nuts (200点)

forとifを組み合わせて答えを出すことができますが、各 i について足す数は \max\{A_i - 10,\,0\} であるのでこれを足していく方が多分少し短いです。

C - Tour (300点)

全頂点対について移動が可能かどうかなので、Warshall-Floyd法で...とすると O(N^3) なので間に合いません。
始点を固定した時同じ頂点を2度以上訪れないようにしたDFSやBFSを行うと、どの頂点も辺も高々1回しか通らないので O(N+M) でその始点から訪れることができるかどうか判別できるので、その始点を全て試して足して合わせてやることで O(N(N+M)) で判定することができます。

D - Cooking (400点)

コストをlong longにし忘れと辺を双方向につなぎ忘れによって3WA出してしまいました... これがなければ、青色復帰できたのに...

U = \{1,\,2,\,\dots,\,N\} を二つの集合 A_1,\,A_2 に空集合を許した分割を行ったときの \displaystyle\min \max\left\{\sum_{i \in A_1} T_i,\,\sum_{i\in A_2}T_i\right\} が答えです。分割の方法は 2^N 通り存在するため、全探索では間に合いません。
この問題は部分和問題であるためDPの利用を考えます。

{\mathrm{dp}}_{i,j} = (T_1,\,T_2,\,\dots,\,T_i \text{の部分和を\(j\)にすることができるかのbool値})
とすると {\mathrm{dp}}_{0,0} =\mathrm{true} であり、1 \leq ileq N について
{\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} {\mathrm{dp}}_{i-1,j} & (j < T_i)\\ {\mathrm{dp}}_{i-1,j}\ \mathrm{OR}\ {\mathrm{dp}}_{i-1,j-T_i} & ({j \geq T_i}) \end{array} \right.
が成り立ち、\displaystyle S = \sum_{i=1}^{N}T_i とすると \displaystyle \sum_{i\in A_2}T_i = S - \sum_{i\in A_1}T_i であるため、答えは \displaystyle\min_{{\mathrm{dp}}_{N,j} = \mathrm{true}}\max\{j, \,S-j\} が答えとなります。j の値は S 以下で S \leq N \displaystyle \max_i T_i \leq 10^5 であり、計算量 O(NS) で十分間に合いました。

E - Rush Hour 2 (500点)

任意の整数時間待機することができるので、各都市への最速到達時間を考えればいいです。道路 i を通って都市 A_i から時刻 t に出発して都市 B_i に到達する時刻は t + C_i + \displaystyle \left\lfloor \frac{D_i}{t+1} \right\rfloor となります。f(t) = t + C + \displaystyle \left\lfloor \frac{D}{t+1} \right\rfloor, g(t) = t + C + \displaystyle\frac{D}{t+1} とした時 g'(t) = 1 - \displaystyle\frac{D}{(t+1)^2} であり、g は t \leq \sqrt{D} -1 で単調減少、t \geq \sqrt{D} -1 で単調増加することから、t = \sqrt{D}-1 のときに最小値をとり、f(t) = \lfloor g(t) \rfloor であることから f も \sqrt{D}-1 附近で最小値をとることが分かります。ちゃんとした解説は公式解説を参照して下さい。
上記から各道を通った時の反対側に着く時刻が最小値となるような出発時刻 t_i が求まります。よって、頂点 A_i に到達可能な最速時刻が T であるとき、 T \lt t_i の時は t_i まで待ってから、T \geq t_i の時は即座に道 i を用いることでその道を用いて B_i へ行く経路のうち最速で B_i に行くことができるため、このように改造したDijkstra法で答えを求めることができます。

F - Hanjo 2 (600点): 未提出

制約からbitDP+行列累乗かなと思いましたが、漸化式が書けませんでした...

結果、感想

f:id:Flkanjin:20210607132329p:plain
久しぶりにレートが上昇しました。速く青色復帰したいです。

ZONeエナジー プログラミングコンテスト “HELLO SPACE”のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

ZONeエナジー プログラミングコンテスト “HELLO SPACE”に参加、レートを大幅に冷やしてしまいました...

A - UFO襲来 / UFO Invasion (100点)

長さは 12 文字なので愚直に書くこともできますがfor文を用いてi文字目から4文字の部分文字列がZONeであるかどうかを判別すればいいです。

B - 友好の印 / Sign of Friendship (200点)

距離 d, 高さ h の遮蔽物が邪魔にならないのはUFOと遮蔽物の上端を結ぶ直線とタワーの交点以上上った時であり、その高さを x とすると三角形の相似より h-x:d = H-x:D 依り \displaystyle x = \frac{Dh-Hd}{D-d} であるため答えは \displaystyle \max\left\{0,\,\max_{i} \frac{Dh_i-Hd_i}{D-d_i}\right\} となります。

D - 宇宙人からのメッセージ / Message from Aliens (300点)

実際に文字列を反転させるのは文字列長ほどの計算量を要するので時間がかかります。反転しているかどうかbool型の変数を用意しておき、その状態に合わせて前後から文字を追加できるようにdequeを利用します。
後半の同じ文字を取り除くのは文字を1文字ずつ取り出していくとき、答えの文字列の末尾と追加する文字が同じときに取り除き、そうでないときそのまま追加するとすることによって実現することができます。

C - MAD TEAM (400点)

最小値の最大化なので二分探索であることは思いつきましたがそれに必要な判定方法をコンテスト中に思いつくことができませんでした。
答えが x 以上かどうかを考える時各人の各能力が x 以上かどうかしか考える必要がなく、5 bitの数と考え、状態を圧縮し、3人を選んだ時に全てがtrueになるかどうかを判定すればいいことが分かります。3人を選ぶときは各人の5 bitの数を集合などに入れてやることで高々 32 種類しか考える必要がなくなり、そこから重複を許して3つ選んでやることでOKかどうか分かります。

E - 潜入 / Sneaking (500点)

愚直に辺を張ると辺の本数が O(R^2C) となり、Dijkstra法でも間に合わないなと考えていました。 何かこれでも通る人は通るみたいですね...通しとけばよかった

x 軸の負方向への移動は +1 がなければ隣の頂点へのコスト 1 の辺で表すことができます。そこで頂点を2階層とし、x 軸の負方向への移動だけは2階層目で、その他は1階層で行うことにします。1階層から2階層の対応する頂点へはコスト 1, その逆はコスト 0 とすることで、問題文の移動を O(RC) 本の辺で表現することができ、Dijkstra法で十分間に合う本数になります。

F - 出会いと別れ / Encounter and Farewell (600点): 未提出

線形の基底らしいですね、履修しておきます...

結果、感想

f:id:Flkanjin:20210503231016p:plain
CやEが解けず、レートを冷やしてしまいました... 2週間連続で冷やしているので、何とか挽回していきたきですね。