所属サークルで競プロ講座(笑)をしたお話
榊です。AtCoderとCodeforcesが水色です。
弊サークルのとある部員が灰色で停滞しているのを見て、茶色へ引き上げたいと思い、講座を開くことにしました。その第1回についてダメだった点について思うところを書いていきます。
書いている途中で、ダメなところばっかり思いついてしまって、ただの反省公開オナニーブログになってしまうことに気付きました。なので、反省はほどほどにして、講座内容の演習問題を作って載せておきました。
反省点:
1.体系としてまとめ上げることが出来ていなかった
つまりは、2時間程度の講座であるにも関わらず、別々なテーマで3種類のお話をしたことが反省点です。極端な例ですが、文字列操作をやった直後にグラフアルゴリスムをやるような、滅茶苦茶な構成になっていました。次回以降はテーマを1つに定めてやります。
2.受講者のレベルに合わせた話が出来なかった
今回は、珍しく(?)1年生の方も来てくれました。しかし、想定が甘かったため、講座内容の全体を通してよくわからないまま終わってしまったのではないかと思います。
反省はこれくらいにして
反省短すぎない?という気はしますが、講座内容の類題を適当に作成しました。
どこかで見たことがある問題だと思います。
見たことがなく、かつ解けないならば、精進をしましょう!
問題1
榊くんは種類の敵iに回だけ攻撃されます。
各敵iの攻撃力はです。
弱体化券を使うことで、1種類の敵の攻撃力をだけ下げることが出来ます。
また、1種類の敵に対して複数枚使用することも出来ます。
ただし、0より下げることはできません。
即ち、敵に対して弱体化券を●回使うとすると、の攻撃力を - ●×X)]にすることが出来ます。
さて、弱体化券は個あります。敵から受けるダメージはmax(0,(榊くんの防御力)-(敵の攻撃力)×(敵の攻撃回数))です。
榊くんが全ての敵からのダメージを0にするのに必要な、最小の防御力を求めなさい。
制約:
実行時間制限:2sec
入力:
N K X
A_1 A_2 ... A_N
B_1 B_2 ... B_N
入力例1:
3 0 5
1 2 3
5 4 3
出力例1:
9
K=0なので敵の攻撃力は減らせません。
敵1は5,敵2は8,敵3は9ダメージを与えてこようとしています。
よって、防御力は9あればすべての敵からのダメージを0に出来ます。
入力例2:
4 2 3
4 4 3 1
1 4 2 4
出力例2:
K=2なので、2回だけ弱体化が行えます。
敵1,2,3,4のうち、2と3に対して1回ずつ弱体化を行うと、
敵1は4,敵2は4,敵3は0,敵4は4ダメージを与えてこようとしています。
よって、防御力は4だけ必要で、これが最小です。
入力例3:
4 100 1
1 1 1 1
1 1 1 1
出力例3:
0
全ての敵の攻撃力を0に出来ます。
よって、0が答えです。
問題2
榊くんは年越しを祝って、N個の整数を用意しました。
この整数を、和がXとなるように取り出す方法は何通りあるでしょうか。
制約:
入力:
N X
A_1 A_2 ... A_N
入力例1:
4 5
4 2 1 3
出力例1:
2
が条件を満たします。よって、答えは2です。
入力例2:
4 5
-1 1 1 4
出力例2:
3
が条件を満たします。よって、答えは3です。