Codeforces Round #516(Div.2)

解いた問題を振り返ります。

A.Make a triangle!

問題概要

Problem - A - Codeforces

3 辺 a, b, c が与えられる。a, b, c の各辺にいくつか数を足して三角形になるようにするとき、足す数の最小値はいくつか?

制約

1 <= a, b, c <= 100

考え方

三角形の成立条件は a + b > c かつ b + c > a かつ c + a > b です。各辺に0 <= i, j, k <= 100 を足して三角形が成立するときのi + j + k の最小値を出力すれば良いです。

Submission #44293160 - Codeforces

B.Equations of Mathematical Magic

問題概要

Problem - B - Codeforces

t 個の a_i が与えられる。 a_i - x_i = a_i xor x_i となるような x_i の個数を各 x_i について求めよ。

制約

  • 1 <= t <= 1000
  • 0 <= a <= 230-1

考え方

まず条件より x は x <= a であることはすぐに分かります。各ビットごとに考えていくことにします。この時 a の i ビット目が 0 の場合は x の i ビット目は 0 よりありません。a の i ビット目が 1 の場合は x の i ビット目は 0 または 1 を取ることができます。 1 - 0 = 1 ∧ 1 xor 0 = 1 と 1 - 1 = 0 ∧ 1 xor 1 = 0 からわかります。よって a のpopcount を k とすると 2k が解となります。これを各 a_i について求めれば良いです。

Submission #44297466 - Codeforces

C.Oh Those Palindromes

問題概要

Problem - C - Codeforces

n 文字の文字列 s が与えられる。文字列に含まれる回文の数を最大にするように s をいくつか並び替えて t とする時、t を求めよ。複数存在するときはどれを出力しても良い。

制約

  • 1 <= n <= 105

考え方

ababa という文字列が与えられた時、最大の回文数は 9 となります。なるべく文字が対称になるように文字を構成すれば良さそうという気持ちになると、同じ文字を連続して並べても最大の回文数は満たされることがわかります。よって実は s をソートするだけで条件を満たす t を構成することができます。

Submission #44302408 - Codeforces

D.Labyrinth

問題概要

Problem - D - Codeforces

n 行 m 列のマスが与えられる。初期位置として r, c が与えられる。左方向への移動は最大 x 回、右方向への移動は最大 y 回の範囲で初期位置から移動するとき、到達できるマスの最大値はいくつか?

制約

  • 1 <= n, m <= 2000
  • 1 <= r <= n, 1 <= c <= m
  • 0 <= x, y <= 109
  • マス.は移動可能、*は移動不可

考え方

初期値からx, y の制限を満たすように BFS をする。ただし移動する際に、なるべく上下の移動を優先的に行い、次に左右の移動を行うようにしたい。なぜなら以下のような場合があるためです。

※黄色のマスが初期位置。答えはすべてのマスに移動可能なので 47 です。 f:id:d_tutuz:20181015231516p:plain

このような場合、上下への移動をコスト 0 、左右への移動をコスト 1 すると 01BFS(01BFS自体の説明は別途) ができます。各マスにそれまで左右に移動した回数を保持しておいて、x, y の制約を超えないように 01BFS で移動したとき、移動可能なマスの数が解になります。

Submission #44336872 - Codeforces

E.Dwarves, Hats and Extrasensory Abilities

問題概要

Problem - E - Codeforces

インタラクティブ問題。n つの点を出力する必要がある。まずある 1 点 (x_i, y_j) を出力する。その 1 点に対して黒 or 白 と色付けされる(この部分はインタラクティブで実行時によって変わる)。すべての n つの点に黒 or 白の色付けがされたとき、最後に黒の点群と白の点群を分割するような直線になるように (a, b), (c, d) を出力せよ。

制約

  • 1 <= n <= 30
  • 0 <= x, y <= 109
  • 0 <= (x_1, y_1), (x_2, y_2) <= 109

考え方

構築問題です。なるべくシンプルに構築したい気持ちになります。なので 1 直線上で各点を構成するようにするとします。まず 2 点は任意に決めることができます。3 点目以降は直前の点の色の結果を踏まえてどこに点を打つか決めます。このようにして黒と白の点が直線上で連続した集合になるように点を決めることができそうです。そのようにして構成した点は 1 直線上にあるので、最後 2 点の位置を (l, y), (r, y) とすると、(l, y-1), (r, y+1) によって同色で分割することが可能になります。

さて、1 点目は l = 0 として (0, y) に、2 点目は r = 10^9/2 として (10^9/2, y) に点を打つことにします。3 点目以降の打ち方は二分探索の要領で l, r の座標の中点 m に打てばよいです。3 点目の点の色によって l = m とするのか、r = m のか決まります。3 点目が 2 点目と同色だった場合はより x 軸の大きい値に点を打つことになるので l = m となり、同色でなかった場合は、 x 軸のより小さい値に点を打つことになるので r = m となります。これを n まで繰り返すことで条件を満たす点を打つことができます。

なお、以下の図は、最初の 2 点が同色だった場合とそうでない場合の 3 点目の打ち方を示した図になります。同色だった場合は l = 10^9/2, r = 10^9 となり、そうでない場合は l = 0, r = 10^9/2 となります。

f:id:d_tutuz:20181016000840p:plain

Submission #44337705 - Codeforces

雑記

pretest では D も通ってまさかの自己最高の 4 完になるかと思いましたが、system test で落ちてしまいました。普通のBFSをしてしまったため、上の D のケースで 46 となってしまい・・・。