競プロ参戦記 #32 偶奇 | みんぷろ2019 [ABC]

今週はヤフー主催の「みんぷろ」に参加しました。

## みんなのプロコン2019

問題一覧: https://atcoder.jp/contests/yahoo-procon2019-qual/tasks

## A - Anti-Adjacency

問題概要: N, K が与えられる。1 以上 N 以下の整数から、どの2つの数も差が2以上であるように K 個選ぶことができるか、判定せよ。


考察: 要するに 1, 3, 5, .. と奇数を K 個選べばよいです。逆にこの選びかたがダメなら、他の選びかたもダメです。

K 番目の奇数 (2K - 1) が N 以下であれば YES、そうでなければ NO となります。

筆者の回答 [AC]: https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4205299


## B - Path

問題概要: 4つの街があり、街の間には合計で3本の道があります。いずれかの街を出発して、1つの道をちょうど1回通ることで、すべての街を訪れることができるか判定せよ。


考察: このような経路をオイラー路といい、オイラー路の存在判定は有名な問題です。次数 (街に接続している道の個数) が奇数の街が2個以下なら存在する、そうでなければ存在しない、ということが知られています。

筆者の回答 [AC]: https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4204518


## C - When I hit my pocket...

問題概要: はじめ、ビスケット1枚がある。以下の操作を合計 K 回行なうとき、最終的なビスケットの個数を最大値を求めよ。

1. ビスケットを1つ得る
2. A個のビスケットを1円と交換する
3. 1円を B 個のビスケットと交換する


考察: 「円」には B 個のビスケットと交換する以外に使いみちがない、というのがポイント。

A 個のビスケット → 1円 → B 個のビスケット、という2段階の操作をひとまとめに考えてよいです。交換して得られた円を使わないままにする、というのは常に損だからです。

したがって、問題を以下のように捉えなおします。

はじめ、コスト K とビスケット1枚を持っている。以下の操作を好きなだけ行なって、最終的なビスケットの枚数の最大値を求めよ。

4. コストを1消費して、ビスケットを1つ得る。
5. ビスケットをA個以上持っているなら、コストを2消費して、ビスケットを (B-A) 個得る。

(B-A) < 0 のケースでは、操作 5. を行う理由はないので、操作 4. を繰り返せばいいです。以降、(B-A) ≥ 0 であるとします。

ビスケットが A 個未満なら操作 4. しかできません。ビスケットが A 個になるまで操作 4. を繰り返す、というのは確定です。

ここでコストが奇数なら、操作 4. を1回行います。これによってコストが偶数になります。

あとは操作 4. を繰り返すか、操作 5. を繰り返すかです。A, B の値をによって決まりますが、両方試して結果が大きくなるほうを選ぶだけでよいです。

筆者の回答 [AC]: https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4209801


## おわりに

C完でした。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

AC
1

ベイン

競プロ参戦記を書いていました。言語実装 | 競技プログラミング | Webアプリ開発 | ほか

競プロ参戦記

競技プログラミングの問題を解いて考察を書いていく日記
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。