PGBattleって何?
こちらのサイトが公式サイトです。
最近巷で話題のAtCoderさんなどが主催の企業/学校対抗の競技プログラミングの大会です。
難易度をチームで3つ分担して解くのですが、自分は企業の部のせんべい部門(真ん中の難易度)で出場しました。
問題について
全部で4問ありました。ちょっとうろ覚えですが紹介していきます。
1問目は、N個の食器を全てKよりきれいにするには何分かかるかという問題でした。
1分洗うと1きれいになって、それぞれ食器の汚さが入力で渡されます。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int result = 0;
// 整数の入力
int n = sc.nextInt();
int k = sc.nextInt();
for (int i = 0; i < n; i++) {
int a = sc.nextInt();
if (a > k) {
result = result + a - k;
}
}
System.out.println(result);
}
2問目は鶴亀算で、N匹とM本の足という情報が渡されて、
aとbとcがそれぞれ何本の足という情報を入力し、それぞれが何匹が答えるものでした。
個人的に一番難しかったです。。
時間もなくて焦っていたのでちょっとぐちゃっとなっています・・・
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int result = 0;
// 整数の入力
int n = sc.nextInt();
int m = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if (a == 0 && b == 0 && c == 0 && m == 0) {
System.out.println(n + " 0 0");
return;
}
for (int aNum = 0; aNum < n + 1; aNum++) {
int x = (m - b * n - (a - b) * aNum);
int y = c - b;
int cNum = x / y;
int bNum = n - aNum - cNum;
if (a * aNum + b * bNum + c * cNum == m && aNum >= 0 && bNum >= 0 && cNum >= 0) {
System.out.println(aNum + " " + bNum + " " + cNum);
return;
}
}
System.out.println("-1 -1 -1");
}
3問目はバレーボールの問題でした。
N人の選手がいて、行動パターンがMこあり、どの選手がどの選手にボールを渡せるというのが決まっていて、3回以内にボールをかえせるかどうかを判定するものでした。
これは案外すぐ解けました。
public class Main {
public static void main(String[] args) {
HashMap<Integer, P> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
int result = 0;
// 整数の入力
int n = sc.nextInt();
int m = sc.nextInt();
IntStream.rangeClosed(0, n).forEach(i -> map.put(i, new P(i)));
for (int i = 1; i <= m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
map.get(a).putNext(b);
}
// 高橋君
map.get(0).putNext(0);
// 入力完了
for (int i = 1; i <= n; i++) {
boolean isOK = false;
for (int first : map.get(i).getNext()) {
for (int second : map.get(first).getNext()) {
for (int third : map.get(second).getNext()) {
if (third == 0) {
isOK = true;
}
}
}
}
System.out.println(isOK ? "Yes" : "No");
}
}
}
class P {
private int myNum;
private HashSet<Integer> set = new HashSet<>();
P(int a) {
myNum = a;
}
public void putNext(int next) {
set.add(next);
}
public HashSet<Integer> getNext() {
return set;
}
}
4問目は座標の問題。
N個の点があり、他の点の中に自分よりx, y, z座標全てが小さい点があるかどうかを判定するものでした。難易度が ★★★★★★となっていたのでビビっていたのですが、すぐ解けました。
public class Main {
public static void main(String[] args) {
HashMap<Integer, P> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
int result = 0;
// 整数の入力
int n = sc.nextInt();
IntStream.rangeClosed(1, n).forEach(i -> map.put(i, new P(i)));
for (int i = 1; i <= n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
map.get(i).putZahyo(a, b, c);
}
// 入力完了
for (int i = 1; i <= n; i++) {
boolean isInside = false;
P point = map.get(i);
for (int j = 1; j <= n; j++) {
if (map.get(j).isInside(point)) {
isInside = true;
}
}
System.out.println(isInside ? "Yes" : "No");
}
}
}
class P {
private int myNum;
private ArrayList<Integer> zahyo = new ArrayList<>();
P(int a) {
myNum = a;
}
public void putZahyo(int x, int y, int z) {
zahyo.add(x);
zahyo.add(y);
zahyo.add(z);
}
public ArrayList<Integer> getZahyo() {
return zahyo;
}
public boolean isInside(P point) {
return point.getZahyo().get(0) > zahyo.get(0) && point.getZahyo().get(1) > zahyo.get(1)
&& point.getZahyo().get(2) > zahyo.get(2);
}
感想
すごく楽しかった・・・!!
はじめての競プロだったので、自分の回答はセオリーとは離れているのかもしれませんが、とにかく楽しかったし、おそらく満点もとれたので満足です。
これを機にAtCoderも登録してみようかと思います!
(追記)
公開しておいて全問不正解で笑ってますww