活動日誌'18 No.001

投稿者 NOSS | 2019-03-14

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

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


A問題

11ワードあたり3232bitで表す。ワード数がWWのとき何bitか求めよ。

32W32*Wが答え。


B問題

概要

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

解説

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


C問題

概要

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

  • 2H502 \le H \le 50
  • 2W502 \le W \le 50

解説

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

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

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


D問題

概要

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

  • 2N10002 \le N \le 1000
  • 0Ci10000 \le C_i \le 1000
  • 1pi10001 \le p_i \le 1000

解説

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


E問題

概要

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

  • 0a500 \le a \le 50
  • 2n502 \le n \le 50
  • 103m10810^{3} \le m \le 10^{8}

解説

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


F問題

概要

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

解説

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


コメント

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

by NOSS