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

2019年2月9日 23:16

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

## みんなのプロコン2019

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

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

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

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

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

問題概要: はじめ、ビスケット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 の値をによって決まりますが、両方試して結果が大きくなるほうを選ぶだけでよいです。

C完でした。

この記事が気に入ったらサポートをしてみませんか？