PCK2023プログラミング部門予選 参加記

sora

大会の参加記を書くの、ちょっと面白そうだったのでやってみる試みです。
2023/9/9(土)、パソコン甲子園のプログラミング部門の予選に「Code-M.K.」というチーム名で参加しました。順位表凍結時点(競技終了30分前)は42位で、凍結後に一問解いたことを反映すると30位相当です。なので多分32,3位とかが最終的な順位ではないでしょうか。まぁ善戦はできたはず。

P.S. 思ったより余計なことを書きすぎてかなり長くなりました。文中に過去形と現在形が混じっているのはご了承ください。


回想：過去のPCK

私は1年の頃からコンピュータ部のしきたりとして(?)PCKプログラミング部門に参加していました。
1年のとき(PCK2021)は「_beginners」、2年のときは(PCK2022)「中間管理職」という名前で参加していました。こうして見ると名前に統一性が一切なく、適当に付けてるのがわかります。
（「中間管理職」は二人とも副部長だったことから付けたのですが、今年は私だけ役職なしに降格されたので付けられなくなりました。「中間管理職と平社員」とかでもよかったかも。）
ちなみに3年とも相方は同じ人です。私が競プロ以外のプログラミングナニモワカラナイとなっているのとは裏腹に、彼はUnityでゲーム制作をしています。すごい。（さすがに今年度に入ってからは競プロの実力では私が上回ったと思っていますが、競プロ以外何もできない時点で私の負けです。）
さて去年まではどんな戦果を挙げていたのかという話ですが…

1年目、PCK2021

1年のときは凍結時点でノーペナ(最速かも?)2完の265位でした。最終的には1-3の3完で9点です。この年までは予選も二人で考察して解く形式でしたね。しかし二人とも所詮AtCoder灰コーダーの文字通りbeginners、寄ってたかってもこの程度ということでした。
ところで競技終了4分前に何とか3問目を解いたのですが、これが中々酷い解法でした。
こんな感じの問題(https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0455)だったのですが、これを…

(中略)

こうです。よくもまぁバグらせなかったな…

2年目、PCK2022

この年から予選だけ2人それぞれの個人成績を合算してチーム成績とする、的なルールに変わりました。私たちのチームは双方さほど実力が変わらない感じだったので、ちょっとありがたい変更だったのかもしれません。あまり意図はわかりませんが…

私が1-6の6完、相方が1-7の7完でした。キャリーされてしまいました。チーム成績は52点6ペナ?で42位でした。
灘高を除けば凍結時点で兵庫県内1位だったので本選進出したものと思っていましたが、凍結後に白陵のチーム「cpc」に抜かされたらしく逃しました。私が7問目を解けていたら違った結果になったのでは？と考えてしまい、これがかなり悔しい経験となりました。
それはそうと、この年のPCKは今までと比べて、かなり7問目くらいまで簡単な気がします。実質個人戦という初の試みだったので、難易度調整に苦心したのでしょうか。

あとこの年は「もうひとつの本選」という、本選進出を逃したチーム向けのミラーコンテスト(?)に参加しました。これは本選仕様なので、2人で考察,実装ができます。実際2,5問目は相方に任せていました。
12問中1-5の5完2ペナで22点、もうひとつの本選6位で凍結時の本選22位相当でした。
結構いい成績に見えるんですが、後日AOJに追加されたジャッジに同じコードを投げたら4問目は落ちたので嘘解法だったらしいです。あのさぁ…

本題：3年目、PCK2023

ようやく本題です。PCK2023の参加記と言っておきながら前置きが長くなりすぎた、これだから遅筆なのです…

Day-x 大会前（夏休み）

PCK2022の雪辱を晴らすべく、そして高校生以下限定の競プロ大会でこれまで好成績を残せていないのがコンプレックスにならないようにするべく、といった意味で以前からPCK2023をかなり意識していました。今年のJOIにも参加はしますが、あちらはもう学年的に本選進出の資格がないので、これが実質最後の大会みたいなものでした。

まず本選進出のためには、同県のライバルが少ないほうが有利です。なので参加チーム一覧をこまめに見ては兵庫県勢増えるな！と願っていました。…しかし最終的には去年よりライバル校が2つくらい増えました。カスな願いには相応の報いがあるようです。

仕方がないので実力でねじ伏せる必要が出てきました。なので夏休みは精進に一層励む…ということは特にした記憶がないです。PCKの過去問を埋めていくつもりだったのですが、結局一切やっていませんでした。あの…
というのも、7月末から友人に「2.5周年で始め時だからやれ」と言われて"ブルーアーカイブ"をうっかり始めてしまったのですが、これがまぁ大ハマりしてしまいまして。可処分時間はこれまでよく競プロに割いていたのですが、ブルーアーカイブのほうが優先度が高くなってしまいました。間違いなく競プロ界隈の高三で一番受験生としての意識が低いです。
他の言い訳としては、7月中はLEGO分野の大会に2年の頃から強制的に出場することになったので向けて準備をしていて、8月半ばまでは基本情報技術者試験の勉強をしていたから、というのがあります。まぁ大会は一応3位(ただし6チーム中)で基本情報も受かったみたいなので、よかったね。

Day0 大会直前

さすがに何もPCKに向けてやっていない、どころか競プロを最近あんまりしてなくないのでやばいよねと思い、PCK2022予選の7,8問目を解いたり2017,2018をバチャ気分で解いたりしました。
8月中はブルーアーカイブにかまけていたにも関わらずAtCoderでは成功続きだったので、なんか強くなってるから大丈夫だろうと思っていたのですが…2017も2018も5問目が解けず6問目は解ける、という感じで危機感しかなかったです。図形とか数学的な考察が要りそうだとか実装が重いとか、AtCoder Beginner Contestの問題とは違った要素が多すぎました。判断が遅い。

まぁもう前日ではどうしようもないので、本番に向けてライブラリを少々印刷して早寝をしました。いい加減何事に対しても前日に動き出す癖を解消するべき。

Day1 大会当日（本当の本題）

(あの、今更ですが大会は一日しかないので"Day"が謎になってきました。なにこれ)

競技開始45分前くらいに部室に入りました。1,2年は割ともう揃っているそうで部室内が賑やかでした。3年は自チーム含めて2チームしか出ておらず、寂しく思いました。
半年ぶりくらいに使うほうの部室だったので少しだけ懐かしんでいたのですが、なぜか自分の席のPCだけマウスがありません。探してもそれらしい余りがなく困りましたが、教員席2のマウスを無断拝借することで事なきを得ました。ちなみにこれを返却し忘れたことに今気づきました。ごめんなさい。

部室の鉄則本と螺旋本をこれまた勝手に拝借して、いよいよ競技開始です。1年目も2年目もコンテスト用サイトのURLが無いとかで競技開始から3分程度ロスした記憶がありますが、今年はスムーズに開始されました。

1問目…の前に、以下の汎用テンプレを3,4分くらいかけて写経しました。早くもちょっと疲れる。

#include <bits/stdc++.h>
using namespace std;
struct Init { Init() { ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(13); } }init;  

using ll = long long;
using ull = unsigned long long;
using pll = pair<ll,ll>;  

#define rep(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.end()
#define el '\n'
#define spa " "  

const double pi = 3.141592653589793238;
const int inf = 1073741823;
const ll infl = 1ll << 60;

template<class T> inline bool chmax(T& a, T b){
    if(a < b){
        a = b; 
        return true;
    }
    return false;
}
template<class T> inline bool chmin(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}

1問目、A%(N+1)を出力するだけの問題です。N+1にしなくてはいけないことを見落とす人がいそうだなぁと思いながら解きました。

2問目、図形問題は出るなと願っていたのに早速やばそうな見た目の問題が出てきます。しかしされど予選2問目、問題文中に解法が書いてあるのを見つけました。入力で負の値があることを失念してabsをつけ忘れかけましたが、まぁやるだけで助かりました。

3問目、なんとなくABC274-Cを思い出しました。

ABC274-Cは当時少し苦戦しましたが、今回はそれより簡単な問題だったのですぐ解けました。bをstd::vectorにpushして,b/=2を繰り返すだけです。相方もちょうど3問目までをノーペナで解けていたようです。いい調子。

4問目、また図形です。勘弁してくれというお気持ちに。
4点を順にA,B,C,Dとおいて、ABのマンハッタン距離、BCのマンハッタン距離、CDの,DAの という風に2点間の距離を4つstd::setに入れて、set.size()==1なら正方形　と考えました。
ただ、これではひし形も正方形と判定してしまうのではないか？と頭によぎりました。実際正答率が低く、嫌な予感がします。しかし、残念ながら「内角全てが90°でなければひし形」という条件が合っているのか確証を得られませんでした。義務教育の敗北かな？それに角度を検知する方法を思いつきませんから、賭けで提出してみます。不正解が返ってきました。まぁはい。

嫌だなぁと思いながら5問目を覗いてみると、明らかに見覚えのある問題でした。素数p,qを用いてp*p*qで表せる という保証はないものの、ABC284-Dとほぼ同じだと一目で気づきました。

なんならあれより制約が小さく、簡単そう。既出はアド！と思いながら記憶を頼りに実装をしていきますが、手が止まります。ABC284-Dはコンテスト中に解けなかった上にコンテスト後も苦戦したのですが、その苦戦したという記憶しかなく、実装の詳細を忘れていたようでした。カス過ぎる。
min(p,q)がNの3乗根より小さいことを利用するのは覚えていましたが、そこからが上手く書けなさそうでした。4問目も5問目も落としているようでは明らかにまずすぎます。
ここで、このABC284-Dはポラード・ロー素因数分解法を用いた高速な素因数分解で解けることを思い出します。奇跡的に写経できる準備は整っていたので、75行近くを必死に写経します。途中で__int128_tが出てきてジャッジ環境が対応しているか不安だったので諦めかけましたが、long longに書き換えて事なきを得ました。制約が小さくて助かった…
写経を終え、std::setに素因数を入れてsize()==2ならYesとしましたが、不正解が返ってきました。え、これは無駄だったのか…？と倒れそうに。
入力に適当に小さめの数をたくさん投げて素因数分解の結果を眺めていると、N=6のようなp*qで表されるケースで落ちていることがわかりました。素因数分解した元の配列のsize()==3が成り立つかも調べてやり、何とかAC。

5問目を通した時点で開始から1時間経過していました。4問目はまだ解けてないことも踏まえると、去年と比べて割と遅い気がします。相方も4問目で1ペナを踏んでいたようで、かなり雲行きが怪しいです。あまり考えないようにと4問目に戻ります。ついでにこの辺りでお手洗いに行きたくなってきましたが、知らぬふりをします。

まぁひし形の判定を加えたら解けるのだろうとある程度確信していたので、どうにかして角度が直角かを判定したいです。幾何問題に強い螺旋本を漁ると、線分同士の直交判定なるものが載っていました。内積が0なら90°だね、というやつです。言われてみれば数学Ⅱでやった気がします。(あの…)
じゃあそれを写経すれば終わりという感じになりましたが、直交判定関数には内積を求める関数が入っていて、内積を求める関数には独自の線分やベクトル構造体が使用されていました。ライブラリ整備ではないので内積の求め方だけ読み解けばよかったのに、考えることを放棄した私は構造体から写経をしてしまいました。
どこを写経すればよさそうか、この問題に対してライブラリをどう対応付けして解こうか、と結局考えることになってしまい、30分ほどかけてようやく直交判定ができるようになりました。提出すると無事AC。
たしかこの辺りで相方も4問目を通していました。これで何とか大爆死を免れた、という感じです。

残り時間は半分を切ったところ、6,7,8,9問目に目を通してみます。6は面倒そうで、7は解けなさそうで、8はほぼ読まずに去って(自分が順位表を見たときに確かKobLaチームが解いていなくて、難しいのかと思ったからです)、9は明らかに確率DPです。

AtCoderでは確率DPだと格上の問題でも通せることがたまにあったので、少し考えてみます。しかし当然というべきか、わかりません。

大人しく6問目にシフトします。読み進めると制約的にもBFSでよさそうな雰囲気がしてきます。例のごとく正当性は考えていませんでしたが、なんとなく[何拍目か]の情報も持たせた三次元配列でBFSをするとうまくいきそうに見えます。
いつもの上右下左4方向への近傍とか範囲外判定のテンプレを写経して実装をしてみます。しかし実装が重い。というか、せっかく近傍を用いて4方向への移動を使いまわしたいのに、移動可能か判定をする都合上使いまわせないのが厳しいです(使いまわせないよね？)。
結局55行くらい書きました。ライブラリを無駄に写経しまくったこともあり目も手も疲れが出始めている中で実装をしたのですが、何とかサンプルは問題なく通るコードができました。頼むぞと思いながら投げるも、不正解。
普段なら何が違うんだと声を出しそうなところですが、こらえて考えます。入力の形式がわかりづらいのでメモを取りながら考察していたのですが、これが功を奏しました。

殴り書きとはいえ全体的に中々字が汚い

サンプルと同じH=2,W=3ではあるものの扉の周期を変えたケースを考えてみます(上画像の赤矢印のやつです)。適当なケースでしたが、プログラムが想定通りに動作していないことがわかりました。(2,2)のマスに上から侵入可能なはずですが、侵入していません。H=4のケースを考えてみて気づきましたが、縦方向の扉の状態の持ち方が間違っていたらしいです。
どういう入力なんだと困惑しながら修正すると、無事ACを得られました。安堵&安堵。

AC時点で残り時間は10分。7問目を考えてはみますが、全然解法が見えてこず、正直燃え尽きたので順位表を眺めるなどします(凍結されているので何も変動がないことにしばらく気づいてなかった)。
そこから何も進展はなく、競技終了。相方は1行分抜けてたので5問目を解けなかった、らしいです。そういうときもあるよね(何目線?)。

競技終了後、おわり

私の提出一覧

ということで、1-6の6完と1-4の4完で合計33点5ペナという形に終わりました。多分。この成績を凍結時点の順位表に合わせると30位相当です。実際は33位くらいと踏んでいます。凍結時点では42位で去年と同じ順位ですが、少なくとも去年より伸びているとは思います。
ところで33位程度だったとしたら、30チーム程度が本選に進出でき、また同校制限の影響もあって本選に出られる可能性がゼロではないです。ただし、地域性という観点を考慮しなければですが。PCK運営さん、ちょっと今年は地域性を排して選出してみませんか？？

競技終了後、直ちにお手洗いに駆け込みました。2時間くらい我慢してたので、さすがに大変でした。競技開始前にも行ったんだけどなぁ…
その後3年4人で解法を話し合いました。競プロトークなんて普段やらないので、新鮮で楽しかったです。相方曰く、4問目はAB,AC,ADの距離をユークリッド距離で,ただしルートをつけずに取っておいて、AB==AD && AB*2==AC かみたいな感じで判定したらしいです(多分)。思考を放棄してライブラリに頼っていた私、反省…

本選に進出できるかと言われると、県内だけで上に5チームは確実に存在するのでかなり厳しいと思います。なんで兵庫県はこんなに激戦区なんだ…？
とはいえ、自分の実力は出し切れたと思っているので、後悔はないです。私は競プロ以外ろくに何もやってないのに2年のPCK,JOI二次予選では悔いの残る形に終わってしまいましたから、今までは深く考えだすと劣等感のようなものを抱かざるを得なかったのですが、今回で挽回できたと思います。あとはJOI予選Aランクを取れれば復讐成功です(?)。
大会直前までやる気あるの？というムーブをしていましたが、満足のいく結果でよかった。何かの間違いで本選進出できないかな…と淡い願いをしながら発表を待つこととします。

さっと書き綴るつもりが、無駄なことを書きすぎたか7500字を超えて自分でも驚いているのですが、ここあたりで切り上げることとします。ここまで駄文にお付き合いいただきありがとうございました。

この記事が気に入ったらサポートをしてみませんか？