投稿者 NOSS | 2019-03-14
2019/3/14に行われた部内コンテストに出題された問題の概要と解説です
コンテストのリンクはこちら
A問題
ワードあたりbitで表す。ワード数がのとき何bitか求めよ。
が答え。
B問題
概要
個のマスがあるポイントカードがあり、マス以上が当たり印のとき景品と交換できる。マスの印はマスにつき円で書き換えられる。
枚のポイントカードがあり、番目のカードの当たりとはずれ印の個数が与えられる。個以上の景品を得るための最小費用を求めよ。
解説
番目のポイントカードを景品と交換できるようにするためには の費用が必要です。これをそれぞれ計算し少ないものから貪欲に枚用いれば最小値になります。
C問題
概要
行列のマスにそれぞれ~匹の蝉がいる。一番左上のマスから一番右下のマスまで最短で移動するとき経路にいる蝉の数の最小値を求めよ。
解説
経路がループしたり戻ることがないのでDPで求めることができます。上から、左から移動したときのマスを、にいる蝉の数をと表すとします。「 = まで行くときの蝉の数の最小値」と置けば
で解くことができます。
また、グラフの最短経路問題として解くことも可能です。
D問題
概要
頂点の木があり、番目の頂点には匹の蝉がいる。番の頂点は根で蝉はいない。辺を切ると根と非連結になった頂点にいる蝉をすべて駆除できる。番目の辺を切るときのコストはである。すべての蝉を駆除するために必要な最小コストを求めよ。
解説
まず根から考えてみます。根からのびる各辺に対して、辺を切る or 残してそれ以降をうまく切る、の2つが考えられます。これらをうまく選択したときのコストの総和が答えです。辺を切ったときのコストはです。辺を残したときのコストはその先の頂点を根とした部分木を考えれば最初の根と同じ形の問題となるので同様の手順で求めることができます。
よって再帰的にこの問題は解くことができます。辺の先の頂点に蝉がいる場合、必ずその辺を切る必要があることに注意します。
E問題
概要
の桁和についてとなる以下の正整数の個数を求めよ。
解説
条件を満たすを考えると、少なくともはある数を乗した数である必要があることがわかります。このような以下のは高々個しかないのですべて調べられます。
F問題
概要
AIとしりとりをします。使用できる文字はアルファベットの子文字のみ。AIの使う単語は文字以下。このとき回以内の手番で勝利してください。
解説
しりとりの有名な戦術である「同じ文字攻め」が有効です。AIが使える単語は2文字以下なので頭文字を固定すれば使える単語の種類は高々27個です。よって50回以内に勝利することができます。
コメント
Cは典型的なDPです。
Dは木DPにつながる問題です。
Eは解の状態から逆算して考えると見通しがつきます。
Fはインタラクティブの練習によいと思います。
by NOSS