2019/3/14に行われた部内コンテストに出題された問題の概要と解説です

コンテストのリンクはこちら

A問題

$1$ワードあたり$32$bitで表す。ワード数が$W$のとき何bitか求めよ。

$32*W$が答え。

B問題

概要

$2N$個のマスがあるポイントカードがあり、$N$マス以上が当たり印のとき景品と交換できる。マスの印は$1$マスにつき$1$円で書き換えられる。
$M$枚のポイントカードがあり、$i$番目のカードの当たりとはずれ印の個数$a_i,b_i$が与えられる。$M-1$個以上の景品を得るための最小費用を求めよ。

解説

$i$番目のポイントカードを景品と交換できるようにするためには $max(0,N - a_i)$ の費用が必要です。これをそれぞれ計算し少ないものから貪欲に$M-1$枚用いれば最小値になります。

C問題

概要

$H$行$W$列のマスにそれぞれ$0$~$9$匹の蝉がいる。一番左上のマスから一番右下のマスまで最短で移動するとき経路にいる蝉の数の最小値を求めよ。

• $2 \le H \le 50$
• $2 \le W \le 50$

解説

経路がループしたり戻ることがないのでDPで求めることができます。上から$i$、左から$j$移動したときのマスを$(i,j)$、$(i,j)$にいる蝉の数を$s[i][j]$と表すとします。「$dp[i][j]$ = $(i,j)$まで行くときの蝉の数の最小値」と置けば

$$ dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + s[i][j] $$

で解くことができます。
また、グラフの最短経路問題として解くことも可能です。

D問題

概要

$N$頂点の木があり、$i$番目の頂点には$C_i$匹の蝉がいる。$0$番の頂点は根で蝉はいない。辺を切ると根と非連結になった頂点にいる蝉をすべて駆除できる。$i$番目の辺を切るときのコストは$p_i$である。すべての蝉を駆除するために必要な最小コストを求めよ。

• $2 \le N \le 1000$
• $0 \le C_i \le 1000$
• $1 \le p_i \le 1000$

解説

まず根から考えてみます。根からのびる各辺に対して、辺を切る or 残してそれ以降をうまく切る、の2つが考えられます。これらをうまく選択したときのコストの総和が答えです。辺を切ったときのコストは$p_i$です。辺を残したときのコストはその先の頂点を根とした部分木を考えれば最初の根と同じ形の問題となるので同様の手順で求めることができます。
よって再帰的にこの問題は解くことができます。辺の先の頂点に蝉がいる場合、必ずその辺を切る必要があることに注意します。

E問題

概要

$x$の桁和$y$について$x=(y+a)^{n}$となる$m$以下の正整数$x$の個数を求めよ。

• $0 \le a \le 50$
• $2 \le n \le 50$
• $10^{3} \le m \le 10^{8}$

解説

条件を満たす$x$を考えると、少なくとも$x$はある数を$n$乗した数である必要があることがわかります。このような$m$以下の$x$は高々$\sqrt[n]{m}$個しかないのですべて調べられます。

F問題

概要

AIとしりとりをします。使用できる文字はアルファベットの子文字のみ。AIの使う単語は$2$文字以下。このとき$50$回以内の手番で勝利してください。

解説

しりとりの有名な戦術である「同じ文字攻め」が有効です。AIが使える単語は2文字以下なので頭文字を固定すれば使える単語の種類は高々27個です。よって50回以内に勝利することができます。

コメント

Cは典型的なDPです。
Dは木DPにつながる問題です。
Eは解の状態から逆算して考えると見通しがつきます。
Fはインタラクティブの練習によいと思います。

by NOSS