ABC167

ABC167に参加しました。

A~Dの四完だったので悪くなかったと思います。

Tasks - AtCoder Beginner Contest 167

All Submissions - AtCoder Beginner Contest 167

A-Registration

Tの末尾を削除して比較すればいいです。

B-Easy Linear Programming

A,B,Cの優先順位でとっていけばいいので、KがA以下ならばK、A+B以下ならばA、それ以外ならば2A+B-kを出力します。

C-Skill Up

ここでbit全探索が！？！？！？！？となりました。

可能なら全通り試すという方向で考える習慣がついてきたので、制約を見てすぐにbitかなあとなったのは成長している感じがしました。Cで出るとは思わなかったので面食らいましたが、何も見ずにかけたので良かったです。一般的なbit全探索なので考察は割愛します。

D-Teleporter

テレポートの回数が明らかに町の数よりも大幅に多いです。テレポート回数のほうが多くなる場合、当然同じ町に複数回訪れることになります。ある町からテレポートする先は固定されているので、どこかに同じところをぐるぐる回っている箇所があることになります。町1からスタートして訪れた街に何番目に訪れたのかをメモしていき、ある街に二度目に訪れたタイミングで探索を打ち切ります。K回のテレポートでは二度訪れた街に到達できていなかった場合と、ループ中にK回目のテレポートをする場合に分けて答えを出します。

E-Colorful Blocks

DPで答えを出すことはできるけれど、たぶん制約的にTLEしそうだなとすぐに思いつきました。前から調べていって、そこまでにいくつ同じ色の組があるかをメモしていく感じです。DPを勉強したばかりだったので、嬉しくなってとりあえずコードを書いてみました。サンプルは通ったものの大半はTLEで1/3はWAになったので全然ダメでした。この時点で残り10分でしたが、コンビネーションでn-1個のうち色が同じ組と違う組のコンビネーションだなというところまで考えて時間になりました。二項係数の計算は一度勉強したのですが、とっさには書けなかったのでまた復習しておきたいです。

Fはコンテスト中は問題文も見ていなかったのですが、何も見ない場合はFよりも正直手が出そうでした。Si内で’(’が’)’に先行しているか、’()’の合計の数は’(’のほうが多いかで前から貪欲に並べていくんだと思いましたが、実装がうまくいきません…。一週間弱寝かせて次のコンテスト日の昼に解くのはやめたいですね…。

Eの二項係数のテンプレのような一応勉強はして理解はしたけれど、すぐには書けない程度のものをライブラリを用意するかどうかをそろそろ考えたほうがいいのかなと思い始めました。使わないほうが力はつきそうですが、コンテストの成績は使ったほうが出ると思われるので悩ましいです。

今回は以上です。