RECRUIT 日本橋ハーフマラソン 2021

A - 魔法使いXの戦い

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

魔法使いXはいまモンスターの大群と対峙しています。モンスターは N 匹いて、横一列に並んでいます。
モンスターにはそれぞれ強さがあり、左から i 番目のモンスターの強さを A_i と表します。

魔法使いXが使える魔法は唯一つ、「パワーアップ」です。
「パワーアップ」はモンスター1匹の強さを、もう1匹のモンスターの強さ分だけ上げるという魔法です。
具体的には以下のような手順を経ます。

強さを変化させたいモンスターを1匹選ぶ。このモンスターの左からの位置を p とする。
モンスターをさらに1匹選ぶ。このモンスターの左からの位置を q とする。このとき p = q でもよい。
p 番目のモンスターの強さが、\(A_{p} = (A_{p} + A_{q}) \% K\) へと変化する。ここで、\% K は K で割った余りを表す。
（K はこの世界における強さの制限値で、強さが K 以上になった場合はオーバーフローしてしまいます）

また、魔法使いXは「パワーアップ」を最大 M 回まで唱えることができます。

「パワーアップ」をかけるモンスターをうまく選び、魔法を唱え終わった後のそれぞれのモンスターの強さをできるだけ小さい値にして、戦いを有利にしてください。

各テストケースの得点およびこの問題の得点は、次のように計算されます。

1つのテストケースでは、以下の式でスコアが計算されます。 \[score = \text{ceil}\left(\sum_{i}(\log_{2}K - \log_{2}(A_{i} + 1))\right)\] なお、\text{ceil}(x) は x 以上の最小の整数を表します。
また、魔法を唱え終わった後の A で 0 でない値が1個以下の場合、M - (魔法を唱えた回数) をスコアに加えます。
テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力

入力は以下の形式で標準入力から与えられます。
1行目には整数 N, M, K がスペース区切りで与えられます。2行目には N 個の整数がスペース区切りで与えられます。

\(\begin{array}{lll}
    N & M & K\\
    A_{ 0 } & \ldots & A_{ N-1 }
  \end{array}\)

N はモンスターの数で、N = 300 を満たします。
M はXが唱えられる魔法の回数で、M = 1000 を満たします。
K は強さの制限値で、K = 10^8 を満たします。
A_{i} は左から i 番目のモンスターの強さを表す整数で、0 < A_{i} < K を満たします。

出力

出力は M 行以下で、各行にはスペース区切りで 2 個の整数を標準出力へ出力してください。

\(\begin{array}{lll}
    p_{0} &  q_{0} \\
    \vdots &  \vdots \\
  \end{array}\)

p_{i} は i 回目の「パワーアップ」の手順1で選んだモンスターの位置で、0 ≤ p_i ≤ N - 1 を満たす必要があります。
q_{i} は i 回目の「パワーアップ」の手順2で選んだモンスターの位置で、0 ≤ q_i ≤ N - 1 を満たす必要があります。
p_{i} = q_i でもよいです。
出力が上記の制約を満たさない場合、となります。

テストケースの生成について

各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
各 A_{i} の値は、1 以上 K 未満の整数から一様ランダムに独立に選ばれます。

入力例1

5 10 100
75 99 51 48 1

このケースは説明用のもので、入力の制約（ N = 300, M = 1000, K = 10^8）を満たしていません。

出力例1

各「パワーアップ」後の A は以下のようになります。

50 99 51 48 1
0 99 51 48 1
0 99 51 49 1
0 99 51 0 1
0 99 50 0 1
0 99 0 0 1
0 0 0 0 1

このケースでは、スコアの計算式は \( \text{ceil}(4(\log_2(100) - \log_2(0+1)) + (\log_2(100) - \log_2(1+1))) \fallingdotseq \text{ceil}(32.21\cdots) = 33\)となります。
また、魔法を唱え終わった後の A で 0 でない値が1個以下なので、10 - 7 = 3 がスコアに加算され、
最終的には、33 + 3 = 36 がスコアとなります。

配布物について

テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザを次のリンクから提供しています。

テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザ (zip)

ビジュアライザの説明

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME.htmlに書いてあります。

input file

output file

fps

command

A_p difference

score

logスケールで表示

save as image

B - マッサージチェア2021

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

Xさんが働くオフィスのフリースペースには、N 行 N 列にマッサージチェアが並べられています。
上から i 行目、左から j 列目にあるマッサージチェアの座標を (i, j) と表します。

マッサージチェアには、色々な性能のものがあります。
(i, j) にあるマッサージチェアの性能を 1 以上 30 以下の整数で表したものを E_{i, j} とし、高いほど良いことを意味します。
また、 (i, j) にあるマッサージチェアを動かすパワーとして、 0 以上 N 以下の整数を自由に設定することができ、これを P_{i, j} とします。

パワーが 0 に設定されたマッサージチェアは使われず、人は座りません。
パワーが 0 以外に設定されたマッサージチェアには、必ず人が座ります。
(i, j) にあるマッサージチェアを 0 以外のパワー P_{ i, j } で動かす場合、パワーに応じた動作音が周囲に聞こえてしまうため、 (i, j) からマンハッタン距離が P_{i, j} 以下の他のマッサージチェアには、人が座らないようにする必要があります。

次の画像は、いくつかのマッサージチェアに 0 以外のパワーを設定した例です。マスに書かれた整数は、その位置にあるマッサージチェアに割り当てられたパワーを表し、ピンク色のマスの位置にあるマッサージチェアには人が座らないようにする必要があります。

Xさんが各マッサージチェアに設定するパワーを決定した後、パワーが 0 でない全てのマッサージチェアに人が座ります。
(i, j) にあるマッサージチェアに座った人は、E_{ i,j } \times P_{ i,j } の満足度を得ます。
マッサージチェアに座った人たちが得る満足度の和を、できるだけ大きくしてください。

各テストケースの得点およびこの問題の得点は、次のように計算されます。

1つのテストケースでは、マッサージチェアに座った人たちが得る満足度の総和がそのまま得点になります。
テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力

入力は以下の形式で標準入力から与えられます。
1行目には整数 N を一つ含みます。続く N 行のそれぞれには、スペース区切りで整数を N 個含みます。

\(\begin{array}{lll}
    N & & \\
    E_{ 0,0 } & \ldots & E_{ 0,N-1 } \\
    \vdots & \ddots & \vdots \\
    E_{ N-1,0 } & \ldots & E_{ N-1,N-1 }
  \end{array}\)

N はマッサージチェアが並ぶ行・列の数を表す整数で、N = 40 を満たします。
E_{ i,j } は (i, j) にあるマッサージチェアの性能を表す整数で、1 ≤ E_{i,j} ≤ 30 を満たします。

出力

出力は N 行で、各行にはスペース区切りで N 個の整数を標準出力へ出力してください。

\(\begin{array}{lll}
    P_{ 0,0 } & \ldots & P_{ 0,N-1 } \\
    \vdots & \ddots & \vdots \\
    P_{ N-1,0 } & \ldots & P_{ N-1,N-1 }
  \end{array}\)

P_{ i,j } は (i, j) にあるマッサージチェアを動かすパワーを表す整数で、0 ≤ P_{i,j} ≤ N を満たす必要があります。
動作音の影響を受けるマッサージチェアは、パワーを必ず 0 に設定してください。
出力が上記の制約を満たさない場合、となります。

テストケースの生成について

各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
テストケースジェネレータは以下の手順でケースを生成します。厳密には実装を見てください。説明・実装ともに、必ずしも目を通す必要はありません。

E_{ i,j } が x になる確率は、 1/x^2 に比例するように生成されます。すなわち、E_{ i,j } が大きな値になるほど、出現する頻度が低くなります。

入力例1

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

このケースは説明用のもので、入力の制約（ N = 40 ）を満たしていません。