東大卒のお金やりくり奮闘記~株、家計、趣味、経済~

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。既婚男性です。株、家計、趣味、経済の話をメインにゆるゆる話します。

競技プログラミング~ABC191~

おはようございます。しほみんです。

 

ゆるゆるやっている競プロの話します。まあ別に難しい問題やんなくてもA-C問題解けるだけでも十分強いっちゃ強いので...

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは1000程度(緑中堅)。

・C#でクラスとかつかってアプリケーションは作れます。

・pythonで自然言語処理勉強中....。

<Atcoderでのスタンス>

・アルゴリズムについて問題でいろいろ学ぶ。第3回PAST70点で中級取得。

・基本的に本番でやっている。現在65回以上参加、2年目。

・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色(1200以上)は欲しい。

 

今回はABC解けましたけど、Cでかなり混乱しました。ただ、普通に考えたらどんな風に問題ができるかを考えると判断できました。

Eはダイクストラ法を実装できれば良いのでもったいなかったなあと思います。

Dは...うんよくある小数点処理とかだよなあ...

レートは925でほぼ維持です。

 

今回はA,B,C,問題を解説します。

 

ここから問題です。問題は簡潔に書いています。

 

問題A

野球をしています。

ピッチャーは、等速直線運動でVm/sで投げて、TからS秒の間は魔球として消せます。

Dm離れていて、このとき、魔球が消えていなければ打てます。

打てるかどうか判定してください。

 

魔球が消えているときの距離は、T*V mから、S*V mまでです。

なので、T*V <= D <= S*V mのときは消えているので打てません。

それ以外は打てます。

簡単なif文でやっていきます。

 

問題B

長さNの数列Aと整数Xが与えられます。

数列AのうちXを除いたものを出力してください。

 

 

頭から数列を読んで、その要素がXでないならそのまま出力。

Xなら出力せず飛ばすをすればよいです。

 

 

問題C

マスで、黒に塗られている部分と白に塗られている部分があります。

このとき、塗られている黒が何角形か判断してください。

 

実際の問題文は結構きちんと定義しているのですが聞いていることはこれだけです。

 

で、どうやって解くかですが、

じつは周りを白で塗っているところがポイントです。

これがないと条件分けが難しくなってしまうのです。

 

つまり、これがあることで、実はもっと簡単に出ないか考えます。

 

そうすると頂点の候補になるのは実はたかだか、81個しかないことが分かります。

そしてそれらの候補はすべて、ブロックに囲まれています。

 

そうなると各候補になる点は、周りのブロック次第で決まるんじゃないか?という発想に至ります。

 

そこで、かんがえると、1つの頂点に対して、4つのブロックのうち、1つだけ白、1つだけ黒の場合のみその点が頂点になるとわかります。

 

なので、結局

これは全探索で、それぞれの候補頂点に対して、白の個数を数えて、1つまたは3つなら、頂点と判断すればよいです。

 

問題が分かりづらいですが、全探索に注意すればできます。なんかこんな問題ほかにもあったけどこういう発想はなかったので今後注意していこうかなと思います。

 

最後に....

C問題は厄介ですが、数学パズル要素的には悪くないです。まあ今後もゆるゆるやってみますか。

 

ではでは。