PG BATTLE 2023に参加しました - Money Forward Developers Blog

この記事は、Money Forward Engineering 2 Advent Calendar 2023、12日目の投稿です。

こんにちは！マネーフォワードでエンジニア採用広報をしているachaです。このブログでは2023年10月21日（土）に行われた、企業・学校対抗のプログラミングバトル PG BATTLE 2023 に参加した際の様子を紹介します。

products.sint.co.jp

PG BATTLE 2023とは

PG BATTLEは、企業・学校対抗プログラミングコンテストです。

1チーム3名でエントリーし、「ましゅまろ(簡単)」「せんべい(普通)」「かつおぶし(難しい)」という難易度ごとに出題された問題を90分間で解き、順位を競います。その際に、チームで一つの問題に取り組むのではなく、ぞれぞれが別の問題に挑戦し、チームの合計点を競います。合計点が同じだった場合は、解答時間の合計が少ないチームが上位となります。
とても人気が高いイベントで、毎年1,000名を超える社会人や学生が参加が参加しています。

詳しい説明やルールなどは公式サイトをご覧ください。

参加メンバーと事前準備

私自身、エンジニアとして働いた経験もなければ、コードもほぼほぼ書けないのですが、エンジニアの方と多く関わる仕事をしています。
「少しでもエンジニアの方の気持ちを知りたい」という思いで3年前から細々と、競技プログラミングに取り組んでいます。 PG BATTLEには前職で参加したことがあり、マネーフォワードでもPG BATTLEに一緒に参加してくれる仲間を探していたところ、RubyKaigiで仲良くなったk0iと、今年の新卒メンバーの1st_vilが競プロに取り組んでいることを知り、誘いました。

事前準備としては、チーム名を決めたり役割分担をしたりはもちろん、参加スタンスについても認識を合わせておきました。私たちは「絶対に1位を取ろう！というよりは、まずは自分たちが楽しむことを重視して、半分以上にランクインすれば嬉しいね」という目的で参加することにしました。

またPG BATTLEではAtCoderとは異なり、回答を提出後、すぐに結果がわからないということも確認しておきました。

そして個人的な対策としては、コードを書くのが1年ぶり…だったので、社内のエンジニア懇親会の際、皆さんに教えていただきながらライブコーディングをしました（笑）。社内のエンジニアがとても優しくて、無事にいろいろ思い出すことができました。ありがとうございます！

参加した感想と問題解決

今回参加した3名で感想を書きました。またachaとk0iはそれぞれ解いた問題の中から1問選んで問題解説もしています。今回出題された問題は公開されているので、興味を持った方は他の問題も解いてみてください！

products.sint.co.jp

ましゅまろ

改めましてこんにちは、achaです。私はもちろん強い希望でましゅまろを担当させていただきました。普段はRubyで問題を解いていて、AtCoderのB問題までであれば、ギリギリ解けるレベルで、競プロはゲーム感覚で取り組んでいます。

感想

「2問解ければ、個人的には大満足」という気持ちで参加したのですが、3問正解することができました。

3問目は2進数と10進数の問題で、Rubyでは .to_s というメソッドがあり、例えば １０.to_s(2) と書くと2進法の10、 1010 が出力されます。このメソッドのおかげで無事正解することができ、日々Rubyを開発してくれている皆さんの顔を思い浮かべながら、感謝の気持ちでいっぱいになりました。

問題解説

難易度:2 微分(Derivative)

問題

Ax^Bという単項式が Ax^B という形の文字列Sとして与えられるので、xで微分して同じ形式で出力してください。但し、 Ax^Bを出で微分すると（A×B）x^B-1となります。

制約

Sは問題文中の条件を満たす
A,Bは整数
2≤A≤10⁹
3≤B≤10⁹

回答（Ruby）

入力に文字と数字が混じっているので、まず文字配列として入力をし、それぞれを分解する処理をしました。その後 .to_i で数字に戻し、答えを計算します。

個人的には、 Array#shift が破壊的メソッドであることを忘れていて、使い方で大混乱してしまいました。配列の3番目以降の要素が欲しいときに s = s.shift(2) と書いてしまいましたが、実際には s.shift(2) が正でした。

s = gets.chomp.chars
a = [ ]

s.each do |i|
  if i == "x"
    break
  else
    a.push(i)
  end
end

s.shift(a.size)
s.shift(2)

s = (s.join).to_i
a = (a.join).to_i

answer = [s*a,"x^",s-1]

puts answer.join

せんべい

せんべいを担当したk0iです。福岡拠点でバックエンドエンジニアとしてRubyを書いております。一緒に働く仲間も絶賛募集中です。競プロは個人開発で使っているRustで頑張っています。

感想

チーム戦ということでとても緊張してしまい、1問正解という悔しい結果に終わりました。最初の問題を凡ミスで落としてしまったのが悔やまれる... 来年リベンジするためにも、競プロは細く長く続けていこうと思います。

問題解説

難易度4: 距離 K

問題文

長さNの数列Aおよび非負整数Kが与えられます。あなたは次の操作を0回以上好きな回数だけ繰り返すことができます。

j−i=Kかつ1≤i≤j≤Nを満たす整数の組(i,j)を選び、 A_iとA_jを入れ替える。操作によって得られる数列は何種類ありますか？答えは非常に大きくなる可能性があるので998244353で割ったあまりを答えてください。ただし、数列が異なるとは、あるi(1≤i≤N)が存在して、一方の数列のi番目の要素が他方と異なることをいいます。

制約

1≤N≤200000
0≤K≤200000
1≤A_i≤10⁹
入力はすべて整数である。

回答(Rust)

kずつ離れた要素しか入れ替えることができないので、自分から見てkの倍数だけ離れている数列の要素は同じグループとし、そのグループ内で組み合わせが何通りあるかを計算、他のグループの組み合わせ数との積をとれば答えです。計算自体は「同じものを含む順列」の求め方と、逆元の知識が必要です。

#![allow(unused_imports)]
use itertools::Itertools;
use proconio::{
    fastout, input as ip,
    marker::{Bytes, Chars, Isize1, Usize1 as U1},
};
use std::collections::{HashMap, HashSet};
use superslice::*;

const MOD: usize = 998244353;

#[fastout]
pub fn main() {
    ip! {
        n:usize,
        k:usize,
        a:[usize;n]
    }
    let mut ans = 1;
    if k == 0 {
        println!("{}", ans);
        return;
    }
    let mut col = vec![];
    for i in 0..k {
        col.push(a.iter().skip(i).step_by(k).collect_vec());
    }
    for i in col {
        let mut same_num_hash = HashMap::new();
        for j in i.iter() {
            *same_num_hash.entry(j).or_insert(0) += 1;
        }
        let mut denominator = 1;
        for j in same_num_hash.values() {
            if *j > 1 {
                denominator *= factorial(*j);
                denominator %= MOD;
            }
        }
        let top = factorial(i.len()) % MOD;
        ans *= moddiv(top, denominator, MOD);
        ans %= MOD;
    }
    println!("{}", ans % MOD);
}

fn factorial(n: usize) -> usize {
    let mut ans = 1;
    for i in 1..=n {
        ans *= i;
        ans %= MOD;
    }
    ans
}

fn modpow(mut a: usize, mut b: usize, m: usize) -> usize {
    let mut ret = 1;
    while b > 0 {
        if b & 1 == 1 {
            ret = ret * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    ret % m
}
fn moddiv(mut a: usize, mut b: usize, m: usize) -> usize {
    a %= m;
    b = modpow(b, m - 2, m);
    a * b % m
}

かつおぶし

かつおぶしを担当した1st_vilです。普段はクラウド会計内部のマイクロサービスの開発保守を行っています。

感想

私は学生の頃は競プロに熱中していた人間なので、こうして社内でも競プロに触れる機会ができて嬉しく思います！ PG BATTLEは他の多数の競プロコンテストとは異なり、一度しか提出ができないルールなので「不正解の結果を受けてプログラムを修正する」という試行錯誤ができません。個人的にはこの緊張感が非常に大きく、ずっとヒヤヒヤしながら見直しをしていました。その甲斐あって提出した問題は無事正解することができたので一安心でした。来年はさらに上位を目指したいと思っています。（ちなみに個人目標として密かに全問完答を目指していたのですが、かつおぶしの名に恥じない難易度で仰天しました。）

結果

私たちチームまねきねこの今回の結果は、184チーム中50位でした🎉話をしていた上位半数以上という結果を大きく上回り、とても嬉しかったです。また全体の順位の中のキリがいい数字に割り振られるスポンサー賞（飛び賞）もいただくことができ、とても良い思い出になりました。（サイオステクノロジー様ありがとうございます！）

個人的には、久しぶりに競プロができてとても楽しかったです。こうやってコードを見ながら社内のエンジニアメンバーと話をしたり、一緒にコンテストに参加して結果に一喜一憂したりする体験は貴重だなと思いました。

来年も参加できるように頑張っていこうと思います！写真は今回参加したメンバーの集合写真です✌️