もふふろぐ

by

東京工業大学プログラミングコンテスト2019 参加記

atcodercompetitiveeventprogram

8月31日の東京工業大学プログラミングコンテスト2019オンサイトに参加しました。

オンサイト参加者はATNDで募集され60人程がフューチャー株式会社オフィスの一角に集まりました。 参加者にはAtCoderのプロフィールが記された名札が配られます。

コンテスト

15問5時間のコンテスト。 5完でした。

A Next TTPC

ABCのA問題からB問題くらいの問題。

B okyoech

正規表現で.*okyo.*ech.*か判定する問題。 めったに使わないので空（そら）では書けませんでした。

C XOR Filling

整数列のXORが与えられた整数になるように構築する問題。 先頭から貪欲に決めることができます。

D 素数取りゲーム

三山崩しを素数に限定したゲーム。 具体的には次のように行動が制限されています。（各山にある石の初期個数も素数。）

一度に取ることができる石の数は素数個で、かつその山の残る石の数も 0 個または素数個である必要がある

素数を普通の三山崩しに置き換えてから、三山崩しの判定方法を検索して解きました。

E N法陣

WA

Nが偶数の場合にすべてNoであると気づかず悩んでしまいました。 想定難易度は500だそうなので、さっと解けなければならなかったと思います。 迷走した結果、魔方陣生成関数が生まれたので競プロスニペットに加えておきます。

ここで詰まった後、残りの問題に目を通し、易しそうに見えたO問題に移りました。 15問もあれば幾何問題もあるだろうと予想していましたが、ありませんでした。

O oneesan puzzle

SからGまでの自己回避歩行の個数がNとなるグリッドマップを構築する問題。 自己回避歩行という語を知りました。

まず「フカシギの数え方」を観るとたった5×5のマップ（動画の数え方では4×4の格子）でも今回のNの上限2019を超える数になることがわかります。 出力するグリッドマップの高さ・幅の上限はともに32であり、複数の部屋を組み合わせる余裕があります。 しばらくグリッドを眺めていたら、自己回避歩行の数がそれぞれa, bの部屋を並列につなぐとa + bに、直列につなぐとa * bになることに気づきました。

あとは構築問題でおなじみの2の累乗数を並べるなどして実装することができます。 私はNを適当な2整数の和に分けてから、それぞれ適当な小さい数の積で表すという実装をしてACしましたが、余白の取り方が雑だったため、後になってN = 1559の1ケースのみで落ちると気づきました。 （その夜のうちに直しました。）

出力の見た目が多様で楽しい問題です。

懇親会

フューチャー株式会社のご厚意によって、寿司とピザが無料で振舞われました。 皆がおなか一杯食べられる量が並べられていました。

同じ大学の人が少なく寂しかった半面、Twitterでしか見たことの無かった方々とお会いすることができました。

有志コンテストながら問題の質が高く、運営の滞りがなく、食事も豪華で素晴らしいイベントでした。 運営の方々に感謝です。