ゆらふなセンパイお誕生日コンテスト

ゆらふなプロの誕生日コンテスト。結構楽しめました。

A - 埋め立て

問題概要

10×10のマスに陸地と海がある。海を1マス埋め立てることで陸地を1繋ぎにすることが出来るか判定せよ。

A: 埋め立て - ゆらふなセンパイお誕生日コンテスト | AtCoder

解説

10×10マスのうちの全ての海のマスに対してそこを埋め立てた時に陸地が1つながりになるか判定する。

BFSでもDFSでも好きにしてください。

Submission #641826 - ゆらふなセンパイお誕生日コンテスト | AtCoder

B - 儀式

問題概要

R×Cの長方形状に並んだ石像をある手順に基づいて回転させる。最初石像は全て南を向いている状態から、ある区域内の石像を全て左回りに90度回転させることをN回行うのだが、何処かの操作1回を忘れてしまったらしい。最終的にM体が南を向いていた時、どの手順か、あり得るものを列挙せよ。

B: 儀式 - ゆらふなセンパイお誕生日コンテスト | AtCoder

解説

まずは正常に操作を行い、忘れることが無ければ何体が南を向いて終わっていたかを数えておく。

各操作を忘れたと仮定して、その操作の範囲の石像は90度回し過ぎていることになっているので、最終的な向きが90度なら元のものに+1、南を向いていたなら-1して、Mに一致すればその手順を忘れても矛盾は無いので出力。

Submission #641827 - ゆらふなセンパイお誕生日コンテスト | AtCoder

C - パスカルの三角形

問題概要

数値Nが与えられるので、パスカルの三角形上で何段目の左から何番目にあるかを求めよ。

C: パスカルの三角形 - ゆらふなセンパイお誕生日コンテスト | AtCoder

解説

パスカルの三角形は組み合わせのnCmと深い関係があり、n段目の左からm番目の要素はn-1Cm-1を示しています。

nC1=nだから、"N+1 2"を出力すれば終わり。

Submission #641829 - ゆらふなセンパイお誕生日コンテスト | AtCoder

D - 錬金術

問題概要

2N文字の文字列S1、S2、S3が与えられるので、S1からN文字、S2からN文字を取り出してS3を作ることが出来るか判定せよ。

D: 錬金術士 - ゆらふなセンパイお誕生日コンテスト | AtCoder

解説

一番苦労した。一度DPも考えたが、恐らくMLE&TLEします。

まず、S1〜3全てにおいて、文字列の順番は関係がないので、どのアルファベットが何回出たかを記録します。

S1に有ってS2に無い文字が有ったらS1から使えるだけ使うしかない。S2に1文字だけあるならS1はS3の数だけ使うか、S3の数-1を使うか選択肢が出来る。それ以降全て同様。

S1でN文字使うので、S1を極力使わないようにした時のS1の使用文字数≦N≦S1をなるべく使った時のS1の使用文字数であれば、上手く調整することでS3が作れる。

例として、上の不等式が4≦6≦15だったとすると、S1で使うことが可能な文字を2つ実際に追加することでS2では2文字使わなくなり、S1S2両方からN文字ずつ出したことになる。

Submission #641832 - ゆらふなセンパイお誕生日コンテスト | AtCoder

感想

体調不良で暫く競プロをやっていなかったので、リハビリには良かったです。