abc55-c
どうもyudegakiです。
atcoder beginner contest 055-cの解説をしていきます。
問題は→C - Scc Puzzle
n個のS字のブロックとm個のc字のブロックを使って"Scc"を作れという問題ですね。
ただし、c字のブロックを2つ組み合わせることでS字ブロックを1つ作れるという点に注意。
まずは2＊n>mのときを考えていく。
2＊n>mのときはS字ブロックの過剰供給となるので、作れる"Scc"の数はm/2個となる*1
次に2＊n==mのとき
ちょうど"Scc"が作れるので、答えはm/2となる*2
そして問題の上記以外の場合…
この分岐に入ってもまだ2通り存在する。
1つめはm-(n＊2)が4未満。つまりc字のみで"Scc"が作れないとき。このときの答えはnとなる。
2つめはm-(n＊2)が4以上のとき。つまりc字のみで"Scc"が作れるときだ
ここでc字のみで"Scc"が作れるときのことについて考えていこう。c字のみで作れるSccの個数は上記の条件式m-(n＊2)を4で割ったときの答えである。これは、"Scc"を作るにはcが4個必要だからである。よってこのときの答えは、m-(n＊2)/4に先述のc字のみで"Scc"が作れない時の答えを足したものだとわかる。よってm-(n＊2)/4+nとなる。
この言葉のままコーディングすればACをとれると思います。
最後に私のコードを貼ってこの解説を終わりとします。もし私のコードに非効率的な部分がありましたらコメントにて指摘していただけると助かります。
ありがとうございました。
#include<stdio.h>
int main() {
long long n, m, ans;
scanf("%llu%llu", &n, &m);
if (n >= m / 2) {
ans = m / 2;
}
else {
if (m - n * 2< 4) {
ans = n;
} else {
ans = n + (m - n * 2) / 4;
}
}
printf("%llu\n", ans);
}
