The 47th World Championship ICPC I問題:Waterworld

問題. Waterworld

下図のように表面が分割された球が与えられる。水平方向には高さが等しくなるように  n 分割されており、垂直方向には  m 等分されている。 j ステップ目のときの領域  A_i の表面積に占める水の量の割合をパーセント表記したものを  a_{i, j} とする。
球全体の表面積に占める水の量の割合をパーセント表記で答えよ。

本家問題文から参照

制約 2 \le n, m \le 1,000 0 \le a_{i, j} \le 100

続きを読む

The 46th World Championship ICPC P問題:Turning Red

問題. Turning Red

 n 個のライトと  m 個のボタンがある。ライトは赤、緑、青の三色のいずれかで点灯する。ライトの色を変えることができるボタンを1回押すと、赤は緑に、緑は青に、青は赤に色を変える。
各ボタンに対して、そのボタンを押すと同時に色が変わるライトのリストが与えられる。ただし、各ライトに対して、そのライトの色を変えることができるボタンの数は高々 2 個である。また、あるライトの色を変えるボタンが与えられない場合もある。

初めに各ライトの色が与えられる。すべてのライトの色が赤色になるようなボタンの押し方で、押したボタンの回数の総和の最小値を答えよ。ただし、そのような押し方が無い場合は "impossible" と答えよ。

制約 0 \le n \le 2 \cdot 10^5 0 \le m \le 2 \cdot n

続きを読む

The 46th World Championship ICPC W問題:Riddle of the Sphinx

問題. Riddle of the Sphinx

3種類の生物がいる。それぞれの種類の足の数を答えよ。

問題を解くためにスフィンクスに「 a, b, c」という形式の質問を 5 回行う。これは 3 種類の生物がそれぞれ  a, b, c 匹いるときの足の本数の合計を訊ねる質問である。この質問に対してスフィンクス r と答えるが、5回の質問のうち多くても 1 回は嘘をつく場合がある。

制約 0 \le a, b, c \le 10 0 \le r \le 10^5

続きを読む

The 46th World Championship ICPC Y問題:Compression

問題. Compression

0 と 1 からなる非空な文字列  s が与えられる。 s の連続する 2 つの同じ連続部分列に対して 1 つの連続部分列を取り除く操作を再帰的に繰り返していく。最終的に得られる文字列の中で長さ最小のものを答えよ。

制約 1 \le |s| \le 10^5

続きを読む

The 46th World Championship ICPC T問題:Carl’s Vacation

問題. Carl’s Vacation

2 つのピラミッドがある。そのピラミッドの頂上間の最短距離を求めよ。

ピラミッドの形状は  (x_1, y_1, x_2, y_2, h) で表される。ピラミッドの形状は真上から見ると正方形で、正方形のある一辺をピラミッドを左にしながら点  (x_1, y_1) から点  (x_2, y_2) へ向かう線分で表す。ピラミッドの頂点は正方形の中心で高さ  h である。
2 つのピラミッドは交差しない。

制約 -10^5 \le x_1, x_2, y_1, y_2 \le 10^5  \left( (x_1, y_1) \neq (x_2, y_2) \right),  1 \le h \le 10^5

続きを読む

【有吉クイズ】割り箸くじびき

2023年2月21日放送の 有吉クイズ 内で割り箸くじびきという心理戦のあるゲームが行われました(テレ朝POST)。ここでは確率論に基づきどのような戦略がよいのかについて考察します。
間違っているかもしれませんのでそのときはコメントで教えてくださると嬉しいです。

続きを読む

png++

png++C++ 言語から PNG 画像の作成・編集等が行える libpngラッパーライブラリ です。libpngPNGエンコード・デコードを行うリファレンスライブラリとして C 言語で書かれています。
ここでは、png++ のインストール方法とその使い方の一部を紹介します。

続きを読む