PG BATTLE 2021 に参加しました

はじめに
問題の紹介と感想
まとめ

はじめに

はじめまして。プラットフォーム事業部の岩井です。

2021/10/23(土)に開催された「PG BATTLE 2021」に、オプティムから3人で参加しました。 PG BATTLEは企業・学校対抗の競技プログラミング大会です。3人1チームになりそれぞれのメンバーが「ましゅまろ」「せんべい」「かつおぶし」の3つのレベルのうち1つの問題セットに挑戦すること、問題の提出は一発勝負であること、などが特徴です。

ちなみに、メンバーは違いますが去年の「PG BATTLE 2020」にもオプティムから参加しております。

本記事の内容はあくまで個人レベルの考察や感想であり、正確性は保証しません。問題についての正確な内容や解法を知りたい方は公式ページをご覧ください。

問題の紹介と感想

問題へのリンクはこちらです。

ましゅまろ

ましゅまろを担当した大内です。競プロは始めたばかりなのでお手柔らかにお願いします。 Pythonで解いてみました。 1と2問目を提出して1問目のみ正解でした。2問目でかなり時間を使ってしまい3問目以降にたどり着けませんでした。

1問目物理現象グラフィックバトル

底面積 $X[\mathrm cm^{2}]$ で高さが $Y[\mathrm cm]$ 、重さが $K[\mathrm g]$ である円柱があります。これを、円柱の底面と水面が平行になるように水に浮かべると、下から $K/X[\mathrm cm^{2}]$ の部分が水に沈みました。この時、円柱の水面より上に出ている部分の高さは何cmですか？

l = list(map(int, input().split()))

a = l[0] * l[1]
b = a - l[2]
c = b / l[0]

print(c)

引き算と割り算で解ける問題でした。

2問目ゼロのない整数

整数 $X$ が与えられます。 $X$ 以上であり、かつどの桁にも $0$ を含まない整数のうち、最小のものを求めてください。

この問題は例えば802という数字なら、811を出力しなければなりません。 1桁ずつ0のチェックをしていたら、テストが半分くらいタイムアウトしていましたorz

この問題はinputを文字列で扱えばOKでした。まずinputをfind("0")で0の位置を出して、0以降をすべて"1"にするという解き方で解けます。

答えを見るとすごく簡単なので、悔しい問題でした(泣)

所感

2週間前くらいに急遽PG BATTLEに出ることになり、とりあえずAtCoder Beginners SelectionのB問題までを解いてきましたが、甘かったです（笑）ただ、競プロが面白いことに気づけたので、次出ることになったらしっかり準備していきたいです。

せんべい

せんべいは新卒の田中が担当しました。 1,2,3問目を提出して3問目のみ正解でした。

1問目７番勝負

$P$ パーセントの確率で青木くんに勝てる高橋くんが、青木くんと7回勝負して勝ち越す確率は何パーセントか求める問題です。

$P$ は整数

$0 \leq P \leq 100$

$7$ 回勝負して勝ち越す確率 = $4$ 回勝つ確率+ $5$ 回勝つ確率+ $6$ 回勝つ確率+ $7$ 回勝つ確率であり、 $k$ 回勝つ確率は、 $p=\frac{P}{100}$ として、 ${}_7 C_k \cdot p^{k} \cdot (1-p)^{7-k}$ で求められます。

最後に答えをパーセントに戻す（100倍する）のを忘れていて、この問題を落としました...（注意力０）

2問目連結成分数の見積もり

$N$ 頂点 $M$ 辺からなる多重辺や自己辺のない無向グラフについて、連結成分の個数としてありうる最小値と最大値を求める問題です。

$N, M$ は整数

$1 \leq N \leq 10^{9}$

$0 \leq M \leq \frac{N(N-1)}{2}$

最小値について

$N \leq M-1$ なら $N$ 個の頂点すべてを辺で繋げるので、最小値は $1$ です。 $N \gt M-1$ なら $M$ 個の辺で最大 $M+1$ 個の頂点を繋げます。この連結成分 $1$ つと残りの $N-(M+1)$ 個の頂点を足すことで、連結成分は $N-M$ 個です。

最大値について

できるだけ少ない数の頂点を使って辺を使い切ることを考えます。 $k$ 個の頂点で消費できる辺の本数は $\frac{k(k-1)}{2}$ 本なので、 $M \leq \frac{k(k-1)}{2}$ を満たす最小の $k$ を求めれば、残りの $N-k$ 個の頂点と合わせて $N-k+1$ 個の連結成分を作れます。

この問題は通せたと思っていたのですが、いくつかのテストケースが通らず不正解でした。そのテストケースを調べたところ、最大値について $\pm 1$ だけ答えがずれていました。

あとで見直したところ、最小の $k$ を求める部分で、（今回Python3で参加したのですが）int型の値とint型÷int型の値を比較する際の割り算に/を用いてしまったために、整数になるべき値が浮動小数点数として解釈され、丸め誤差が比較の結果に影響を与えてしまっていたことが分かりました。 /を//に変えたら正解でした。

3問目トーナメント表

人 $1$ から人 $2^{N}$ までの $2^{N}$ 人がトーナメント形式のプログラミング対決を行いました。勝負の結果、人 $i$ はベスト $a_i$ になりました、トーナメント表の人の並び方としてあり得るものを $1$ つ出力してください（あり得る組み合わせが存在しない場合は $-1$ を出力）

細かい定義については実際の問題文を参照してください。

トーナメント表で左から $j$ 番目に並んでいる人がベスト $b_j$ になるような有効なトーナメント表 $\{b_j\}_{j \in1\dots 2^{N}}$ を1つ生成して、 $\{a_i\}_{i \in1\dots 2^{N}}$ を置換することを考えました。

生成したいトーナメント表 $\{b_j\}_{j \in1...2^{N}}$ は再帰的に求められます。具体的には、 $2^{k}$ 人による有効なトーナメント表 $\{b_j\}_{j \in1\dots 2^{k}}$ に対して、 ${b_j} \to \{2^{k+1}, b_{2j} \}$ とすることで $2^{k+1}$ 人による有効なトーナメント表が生成できます。

このトーナメント表に合うように与えられた $\{a_i\}_{i \in1...2^{N}}$ を並び替える（並び替えられない場合は $-1$ を返す）ことで、所望の結果を得られます。

組み合わせが存在しない場合を完全に考慮できているか少し不安でしたが、これは無事正解でした。

4問目 [リ[[スー]バ][ズパ]ル]

（問題文は長いので割愛）

反転器で決まる区間の両端だけを覚えておけばいいのかな〜など少しだけ考えましたが、今の自分には解けそうもなかったのでパスしました。

所感

3問通して役目は果たしたなと思っていたので、結果が出たときはびっくりしました。詰めの甘さが如実に結果に出てしまったので、来年はきっちり解ける問題は解ききりつつ、解ける問題を増やせるよう精進していきたいです。

かつおぶし

かつおぶしは本記事執筆者の岩井が担当しました。 1,2問目を提出して1問目のみ正解でした。3,4問目については時間中にたどり着けず、解説を見たところ「自分にはちょっと早いかな…」というレベルの難しさだったので、割愛します。

1問目階乗の桁数

$N!$ は $10$ 進表記で何桁ですか? ただし $N!$ の最上位桁は $2$ 以上 $8$ 以下とします。

$1\leq N \leq 5 \times 10^{5}$

$N!$ の最上位桁は $2$ 以上 $8$ 以下である。

$10$ 進表記の桁数は $10$ を底とする対数を取ることで求められるので、 $\log_{10}N! = \sum_{n=1}^{N} \log_{10}n$ を計算すればOKです(正確には小数部分を切り捨てたり $1$ を足したりの操作があります)。高校数学の知識を使えば簡単ですね!

しかし、ここまで考えて私は二の足を踏みます。なぜなら $\log$ の計算結果が小数であるため、誤差が発生して正しい答えにならない恐れがあるからです。普段のコンテストであればこの考え方で一旦提出してしまうのですが今回は一発勝負故、ビビって提出できません。

最終的に2問目をある程度考えた後に「factorial digits」で検索をかけたところ当初の方針でよいことがわかったので、コードを拝借して提出しました。最上位桁の条件が存在することで $N!$ の値が $10^{x}$ に近い場合を考える必要が無くなり、誤差が出るようなケースを回避しているのだと思います。

2問目桁と数列

正の整数 $N, S$ と、正の整数からなる長さ $N$ の数列 $D=(d_1,d_2,\dots ,d_N)$ が与えられます。以下の条件を満たす長さNの数列 $A=(a_1,a_2,\dots ,a_N)$ を $1$ つ出力してください。

$a_1+a_2+\cdots + a_N = S$

$1\leq i \leq N$ について、 $a_i$ は $10$ 進表記で $d_i$ 桁で表される正の整数である。

ただし、 $021$ のようにleading zerosをつけた表記はここでは認められない。

ただし、条件を満たす数列が存在しない場合は $-1$ を出力してください。

$1\leq N \leq 100$

$1\leq S \leq 10^{9}$

$1\leq d_i \leq 9(1\leq i \leq N)$

入力は全て整数である。

問題の理解に少し時間を要しましたが、簡単に言うと、数列 $A$ の各要素の桁数のみ指定されているので、総和が $S$ になるような $A$ の具体例を挙げよ、という問題です。

まず最初に考えたのは、与えられた $D$ に対して $A$ を構成可能な $S$ の最大値です。各 $a_i$ の最大値は $10^{d_i}-1$ 、つまり $9$ を $d_i$ 個並べた数なので、 $S$ の最大値はそれらを全部足した値であり、 $S$ がこの値を越えたら条件を満たす $A$ は存在しません。 …と、ここまでは順調だったのですが、 $S$ が小さい場合どうなるのか、 $A$ の構成はどのように行うのか、などを考えているうちに集中力が限界を迎えてしまいました…。結果的に $a_i$ の最小値についての考慮が抜けていて誤答でした。

$S$ の最大値と同じように最小値もあって、それは各 $a_i$ が全て $10^{d_i-1}$ の場合です。そして、 $S$ が最大値と最小値の間であれば $A$ は必ず構成可能です。 $A$ を構成するには、各 $a_i$ の最小値を確保した上で $a_1$ から順に値を詰めていけばよいでしょう。シャンパンタワーのようなイメージです。

この問題は特定のアルゴリズムを要求しないという意味で、極論誰でも解ける問題でした。このような問題を確実に取れるようになりたいものです。

所感

かつおぶしを選んだことにより自分が通せる可能性がある問題は恐らく4問中2問だけ、そして一発勝負という環境。これらが揃うことにより一問も解けないのではないかという恐怖によってメンタルがガリガリと削られていきました(泣)。それに加えて1問目が解けていない状態で2問目に移ったことにより、2問目の途中でバテてしまったのだと思います。

まとめ

順位は192チーム中78位でした。兎にも角にも、全メンバーが1問ACを取れたことを嬉しく思います。終了後にはチームのメンバーと問題について語り合い、盛り上がりました。次回は競プロerが増えて弊社から複数チームで参加できたら嬉しいですね。

本記事でオプティムにご興味を持っていただけた方は、こちらをご覧ください!

はじめに

問題の紹介と感想

ましゅまろ

1問目 物理現象グラフィックバトル

2問目 ゼロのない整数

所感