【プログラミングコンテスト】AtCoder Beginner Contest 118③
明日のAtCoder Beginner Contest120に向けて練習中のねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc118)にて開催されました、AtCoder Beginner Contestの第2回目です(C問題の解説ですが、B問題を解いてないので2回目です)。
今回は、第3問「C - Monsters Battle Royale」の問題と僕との戦闘記です。
0.はじめに
1.問題文
N 体のモンスターが居て、それぞれ 1 , 2 , . . . , N と番号付けられています。
はじめ、モンスター i の体力は A i です。
以降、体力が 1 以上のモンスターを生きているモンスターと呼びます。
生きているモンスターが 1 体になるまで以下を繰り返します。
ランダムに 1 体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。 その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。 最後に生き残ったモンスターの最終的な体力の最小値を求めてください。
2.入力例
入力
4 2 10 8 40
出力
2
1 番目のモンスターだけが攻撃し続けた場合、最後に生き残ったモンスターの体力は 2 となり、このときが最小です。
3.初見の感想
- 攻撃するモンスターの選び方は、最も小さいHPのモンスター
- ただ、最も小さいモンスターの攻撃は回数がかさむのでTLEになりそう…
- 効率的な攻撃方法とは…?(ここで思考停止)
4.学びポイント
- 問題をより深く分析すると…求める答えは最大公約数!
- ユークリッドの互除法を実装しましょう
- 互除法は同じ操作を複数行うので再帰的に書くのがよさそうですね
5.コードの簡単な解説
- 入力のパースはこちら
var n = int.Parse(Console.ReadLine()); var A = new int[n]; var temp = Console.ReadLine().Split(' '); for (int i = 0; i < n; i++) { A[i] = int.Parse(temp[i]); }
- 2数での互除法はこのような再帰関数で書ける
static int gcd(int x, int y) { if (x == 0) return y; if (y == 0) return x; if (x < y) return gcd(x, y % x); else return gcd(x % y, y); }
- あとはこの関数をそれぞれの数字に適応させます
static int gcd(int[] A) { var ans = A[0]; for (int i = 1; i < A.Length; i++) { ans = gcd(ans, A[i]); } return ans; }
6.全コード
using System; class Program { static void Main(string[] args) { var n = int.Parse(Console.ReadLine()); var A = new int[n]; var temp = Console.ReadLine().Split(' '); for (int i = 0; i < n; i++) { A[i] = int.Parse(temp[i]); } var ans = gcd(A); Console.WriteLine(ans); } static int gcd(int[] A) { var ans = A[0]; for (int i = 1; i < A.Length; i++) { ans = gcd(ans, A[i]); } return ans; } static int gcd(int x, int y) { if (x == 0) return y; if (y == 0) return x; if (x < y) return gcd(x, y % x); else return gcd(x % y, y); } }
7.最後に
例を使って、問題の解き方をノートの上でいいので思いつきたいものです…