2024-04-23

The 46th World Championship ICPC Y問題：Compression

競プロ-ICPC

問題. Compression

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

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

2024-04-23

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

アルゴリズム-計算幾何競プロ-ICPC

問題. 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-02-24

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

数学-数学問題

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

2023-02-01

png++

環境-ツール

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

2021-09-24

ICPC国内予選2020 D問題：icpca 文字

競プロ-ICPC アルゴリズム-ビット操作アルゴリズム-探索

$n$ 種類の相異なる英大文字からなる文字列 $a_1 a_2 \ldots a_n$ と、式 $S, T$ が与えられる。
式 $S, T$ は次の文法規則からなる。
　・E $::=$ F | '(' E '<' E ')' | '(' E '>' E ')'
　・F $::= a_1$ | $a_2$ | $\ldots$ | $a_n$
ただし、不等式の評価は $a_i < a_j$ ならば $\min\{a_i, a_j\}$ 、 $a_i > a_j$ ならば $\max\{a_i, a_j\}$ とする。
$a_1 a_2 \ldots a_n$ 上の全順序のうち式 $S$ と $T$ の値が等しくなるものの数を求めよ。

制約： $1 \le n \le 16$ 、 $0 \le |S|, |T| \le 100$

2021-09-17

ICPC国内予選2020 B問題：接触追跡

競プロ-ICPC

問題. 接触追跡

あるアプリを利用している人が $m$ 人いる。その中で $p$ 番目の利用者は感染者である。時刻順に濃厚接触の記録が $n$ 件与えられる。 $i$ 番目の記録 $a_i \neq b_i$ は $a_i$ 番目と $b_i$ 番目の利用者が濃厚接触したことを表している。感染者と直接的または間接的に感染した疑いのある利用者の総数を求めよ。