2023年4月7日
待望のプログラミングゼミも始まり、忙しくなってきた。
このゼミの為にAtcoder茶色になったのだが、そこから明確な目標が無くなり迷走気味だった。
そしたらゼミでPG BATTLEというプログラミングコンテストに参加する旨を伝えられたので、これをモチベーションにプログラミングを頑張ろうと思う。
人工知能も勿論やる。
PG BATTLEって？
PG BATTLEというのはチームを組んで90分間で競プロの問題を解き合うチームプログラミングのこと。
企業・学校対抗と書いてあるので、個人的にチームを組んでの参加はできなさそう。
このPG BATTLE、AtCoderの社長であるchokudaiさんが解説を努めるなど、かなり本格的。
ルール的なところだと年度によって変わるけど、最近だと。
-
1チーム3人で参加
-
問題は、ましゅまろ ＜ せんべい ＜ かつおぶし という3つの難易度を分担して行う
-
相談は無し
-
90分間
-
同点の場合は時間が速い方の勝ち
-
提出は一回のみ
といった感じ。
難易度感を探る
ましゅまろやら、かつおぶしやらで問題の難易度感が全く分からないので、とりあえず簡単に問題を自分で解いて難易度感を知る。
注意
・Atcoder茶色個人の感想。
・paizaの問題はそんな数を解いてないのでかなり適当。
・ジャッジがないので、実際は解けてない可能性あり。
・検索はok、ChatGPTは使わないルールで解く。
AtCoderの難易度感が分からない人は、AtCoder社長のブログを見てもらうのがいいかと。
AtCoderは
dif0〜399(灰色) < dif400〜799(茶色) < dif800〜1199(緑色)…
という感じで続いてて、dif400が解ければpaizaのSは解けるくらいのレベル感。
2022年度問題
ましゅまろ-難易度1「電話番号」
個人的にdif0〜10。
paizaだとCランクくらい。
ましゅまろ-難易度2「等式」
dif10〜30くらい？
paizaだとC上位かB下位くらい？
ましゅまろ-難易度3「試験の成績」
dif50〜100くらい？
まだ灰色下位のレベルな感じがする。
paizaならB。
ましゅまろ-難易度5「沈黙」
カニの問題。
この問題は私には解けなかった。
chokudaiさんの解説を見たら半分全列挙という聞いたことがないアルゴリズムを使ってたので、そりゃ解けないわ。
難易度的には解けないので測定不能。
少なくとも茶色以上、paizaで言えばそもそもこんな問題は出ないレベル。
マジで適当なことを言うと難易度は緑前後な感じはする。
かなり難易度に落差があることがわかった。
せんべい-難易度2「せんべい」
難易度せんべいの「せんべい」という問題。
dif10〜30くらい。
paizaならC上位くらい。
制約がもっと大きかったらむずいだろうけど、小さいから愚直にやれば問題ない。
せんべい-難易度3「食品の区別」
dif100〜200くらい。
paizaならA。というか、そもそもpaizaで処理時間を気にする系の問題は無かった気がする。
私の解法の場合Pythonのlistじゃなくてsetを使わないと恐らくn=10^5の時TLEになるので、そういう意味ではdif200〜300くらいかなと思う。
でも、公式解法ではsetを使った方法を使ってないので、他の解き方をする人もいると想定してのdif100〜200という感じ。
せんべい-難易度4「区間の削除」
dif300〜500くらい。
私の実力では解くのに1時間くらいかかった。
最大ケースを自分で作ってTLEにならないことは確認して、色んな自作ケースで解説の解法と自分の解法が同じ答えになることも確認した。
後ろから探索していくっていうのは過去に解いたことがあったので、解法はぱっと出たんだけど、実装が全然上手くいかなかった。
解説の解法のpythonは綺麗すぎてホントスゴイ。
paizaで言えば難易度Sだけど、paizaではそもそも解法とか処理時間を気にする系の問題は出ない気がするから、「例えられない」が正しいと思う。
せんべい-難易度6「都市の合併」
余裕で解けない。少なくとも茶色以上。
この問題は適当なことも言えないくらい何もわかんない。
でも、頑張って適当なことを言うと、緑より難しいのではと思う。
勿論paizaでは例えられないくらいの難しさ。
そもそも問題文として理解するのが大変なレベル。
ここまでくるとAtCoderでグラフ系問題に慣れてないと何言ってんのかわかんないのでは。
かつおぶし-難易度3「等差数列」
dif10〜50。
paizaだと早解き出来る系のBくらい？
制約も小さいので愚直に解いても解けると思われる。
かつおぶし-難易度4「反射」
dif400以上
paizaでは例えられないレベル。
私には解けなかった。
解説を見るとちょっとした数学的要素と、ちょっとした全探索の工夫が必要な感じなので、茶色の人でも解ける人は解けそう。
適当なことを言うとdif600〜800くらいなのでは。
かつおぶし-難易度5「模様」と難易度6「二歩」
どちらも解けなかったし、難易度はわからない。
けど、難易度5の「模様」の解法は面白くて茶色でも理解できるレベル。
適当なことを言うと、「模様」は緑レベルくらい？ 茶色でも解ける人は居そう。
「二歩」は解説も理解したくないのでマジで茶色には測定不能。
難易度のまとめ
難易度1はAtCoderで灰色下位。A問題レベル。
paizaではC問題くらい。
難易度2も同じく灰色下位レベル。
paizaでもC問題くらい。
難易度3になると処理時間を気にする問題も出てくる。
AtCoderで言う灰色下位から灰色上位。ちょっと歯ごたえのあるB問題か簡単なC問題くらい。
paizaならB~A。
難易度4はAtCoderで言う茶色レベル。恐らく茶色でも解ける人と解けない人がいるくらい。
paizaにこの難易度はないけど、強いて言うならS。
難易度5,6はもう正直私には難しくてわからないんだけど、適当なこと言うと難易度5が緑で、難易度6は難易度無制限という感じなのだろうか。
PG BATTLEへの目標
私はかつおぶしの難易度を任されそうなので、安定して難易度3と難易度4を解くには茶色上位または緑下位くらいの実力が必要になりそう。
更に、難易度5とかをわんちゃん解きたいなら緑上位とかそれ以上は欲しくなるのかなぁ。
他年度のPG BATTLEの過去問を見ると数学系の問題もちゃんと出てるから、そこら辺も対策しないといけないのかもしれない。
正直最近さぼり気味だったんだけど、精進を再開しようと思った日でした。
