もふふろぐ

by

ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状 参加記

competitiveeventprogram

9月14日のゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状に参加しました。

希望者はconnpassで募集され、抽選で参加可能者が決まりました。

開場に着くと、アイコンとAtCoderレーティングが表示された名札が配られました。 手軽にAtCoderじゃんけんをすることができます。

ハッシュタグは#ゆるふわオンサイト

コンテスト

HackerRank ゆるふわ競プロオンサイト #2

12問2時間のコンテスト。 目安は1問10分でしょうか……。 結果はA～Iの9完2900点（1:50:08）で11位（スコア8位タイ）になり、バナナをいただきました。

A honda’s janken

hondaとのカードバトルの勝敗判定をする問題。 100点問題らしく、問題文通りの分岐を書けば解けます。

B sentouryoku

入力された文字列の「戦闘力」を求める問題。 A問題と同じく、問題文通りに実装すれば解けますが、ループを含むので200点問題です。

C mosaic tile art

N×Nのグリッドについて、どの行・列もちょうど1マスだけ色が塗られるような選び方が何通りあるか計算する問題。 Nクイーン問題から斜めの規則を消した問題とも言えます。

Nクイーンと同様、1行目からN行目まで順に見て、各行で何通りの選び方があるかを考えることで、行ごとに1マスの規則を満たすことができます。 i行目では、1～i - 1行目で選んだ列を選ぶことができません。 ゆえに、i行目での選び方はN - (i - 1)通りになります。 よって、N!（mod 1e9 + 7）が答えになります。

D n-dwich box

1個以上の「n-ドイッチ」文字列を結合した文字列をパースする問題。 くすっとなりました。

  • 1-ドイッチ := “|”
  • n-ドイッチ := (n-1)-ドイッチ + “#|”

例えば|#||#|#|は|#|+|#|#|と分割され、2 3が出力になります。

先頭から（実際の実装では先頭の次から）1文字ずつ読み、#なら次の|も飛ばしてn++、|ならnを解答にpushしてからn = 1、として解けます。

E usagi vs kame

問題概要を省略。 クエリがソート済みである点が良心的です。 行動のキューとクエリのキューの先頭を見比べて、時刻が小さいほうを処理すればO(N+Q)の解答になります。

実装で楽をするために、行動とクエリを1個の配列に混ぜて入れました。

F mneme game

累計q番目の暗唱が何周目に含まれているかを二分法で求めます。

周数が最大でも10^5だったので、怠けて、i * (i + 1) / 2を入れた配列にupper_boundを使いました。

G double range cards

二次元累積和を使います。

1回の操作で矩形領域が2個ずつ指定されていますが、この2個は同時に処理する必要が無いため、Q個の入力を2 * Q個に読みかえて実装を簡潔にできました。

H gori uho game

ゲームの勝敗を判定する問題。 完全ゲーム木が小さいため、単純な全探索で解くことができますが、類題をAtCoderで見かけないため、手こずったかもしれません。

I pino assort

ピノアソートという商品があること、また、その箱にはバニラ, アーモンド, チョコ味が10, 7, 7個入っていることを知りました。

入力の制約が小さめだったので、いいかんじに前処理をしてから、必要人数が集まるまでループを回しながら貪欲に選択すれば解けました。 AtCoderで出題されるなら、制約に10^9などの数が現れるのではないでしょうか。

J swapping paths

I問題を終えたところ残り10分になり、J問題を実装できませんでした。

グリッドの最大幅10^9を見て物怖じしそうになりますが、一息ついて考えると、グリッドの幅をすべて使うことはありえないとわかります。 適当に小さな領域を切り取って、DPすれば解けそうです。

懇親会

おいしいピザ🍕が振舞われました。 JAG夏合宿と重なったため、知人は少なかったですが、新たな知人が増えました。 また幸運にも、オンサイトにはあまり参加されていなかったサークルの先輩に久々にお会いできました。

コンテストはもう1時間あれば……という結果に終わったものの、ちょうどよい難易度の問題が揃っていて、よい勉強になりました。 考察よりも実装寄りの問題が多かったかもしれません。 2時間のみの競技でありながら、詰まって座るだけになる時間がなかったため、非常に疲れましたし、上位の方々との実装力💪の差を思い知りました。

参加者に合わせた問題数・難易度設定は学科内コンテストの運営でも毎年課題になることなので、今回の作問には技を感じました。 （1問1日のペースで準備したとのこと。）

次回も参加できたら嬉しいです。