AtCoderさんでYahooさん主催の「みんなのプロコン2019予選」が開催されました。
初めてコンテスト中にC問題が解けたコンテストでした。嬉しい。
復習も兼ねて、A~Cまでの解法を書きます。
A-Anti-Adjacency
問題文引用
以上 N 以下の異なる整数を、差が の整数をともに選ばないように 個選ぶことができるか判定してください。
筆者がたかをくくって2WA出した問題。許さない。
冷静に考えると、N/2の切り上げとKを比較するだけです。（公式の解説とはちょっと違うらしい）
切り上げはMath.Ceiling()メゾットを使用すると実装できます。参考サイト
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Atcoder { class AtCodeeeeeeeeeeeeeeeeeeeeeeeer { static void Main(string[] args) { string[] s = Console.ReadLine().Split(' '); double N = int.Parse(s[0]); int K = int.Parse(s[1]); Console.WriteLine( Math.Ceiling(N / 2) >= K ? "YES":"NO" ); } } } |
Math.Ceiling()メゾットを使用するためにNはdoubleの型を使用しました。
N/2の切り上げがK以上であれば”YES”、そうでなければ”NO”を出力してACです。
B – Path
問題文引用
4 つの街があり、順に 1,2,3,4と番号が付いています。 道が 3 本あり、i 本目の道は異なる街 ai,biを双方向に結んでいます。 同じ街の対の間を結ぶ道が複数あることはありません。街同士を行き来する手段は、道以外にはありません。 どの 2つの街の間も、道を何本か通ることで行き来することができます。
すべての道をちょうど 1回ずつ通ることですべての街を訪れることが可能かどうか判定してください。
制約
- 1≤ai,bi≤4(1≤i≤3)
- aiと bi は異なる (1≤i≤3)
- 同じ街の対の間を結ぶ道は複数存在しない
- どの 2つの街の間も、道を何本か通ることで行き来することができる
問題文から「どの 2つの街の間も、道を何本か通ることで行き来することができます。」に着目します。
この条件が適用されている状態で、すべての街を訪れることができないのは一つの街に3本道が伸びている場合のみです。
よって
一つの街の番号が3回出てくる→NO、それ以外はYES
というロジックが成り立ちます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Atcoder { class AtCodeeeeeeeeeeeeeeeeeeeer { static void Main(string[] args) { //入力受け取ってリストlsに追加 List<int> ls = new List<int>(); string[] s = Console.ReadLine().Split(' '); ls.Add(int.Parse(s[0])); ls.Add(int.Parse(s[1])); string[] t = Console.ReadLine().Split(' '); ls.Add(int.Parse(t[0])); ls.Add(int.Parse(t[1])); string[] u = Console.ReadLine().Split(' '); ls.Add(int.Parse(u[0])); ls.Add(int.Parse(u[1])); string ans = "YES"; if (ls.Count(n => n ==1) == 3 || ls.Count(n => n == 2) == 3 || ls.Count(n => n == 3) == 3 || ls.Count(n => n == 4) == 3) { ans = "NO"; } Console.WriteLine(ans); } } } |
int型のリスト「ls」を作成し、lsに入力を追加していきます。
条件「一つの街の番号が3回出てくる」を満たした場合のみ答えをNOにします。
list.Count()を用いて重複した要素が３つ存在する場合を判定しました。
C-When I hit my pocket…
問題文引用
すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。
すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。
- 持っているビスケットを叩き、1 枚増やす
- ビスケット A 枚を 1 円に交換する
- 1 円をビスケット B 枚に交換する
K 回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を求めてください。
制約
1≤K,A,B≤10^9
K,A,Bは整数である
ここで重要なのは「最後にお金を持っていても意味がない」ということと「ビスケットをお金を通じて交換すると2ターン消費する」ということ。
「最後にお金を持っていても意味がない」ということから、「ビスケット→お金、お金→ビスケット」という動作を一つとして見てあげると途端に楽になります。
また「ビスケットをお金を通じて交換すると2ターン消費する」ということから、持っているビスケットを叩いて、その間に2枚増やせるということはわかりますね？
この「ビスケットをお金を通じて交換する」行為は3枚以上の”うまみ”がなければする必要はないということになります。
つまりロジックはこうです。
”うまみ”が3枚以上あり、かつ2ターン以上残っていて、かつ現在のビスケットがA枚以上ある時にうまみ分ビスケットを増やして2ターン消費する。
”うまみ”がない時（3枚未満のとき）、そして残り1ターンのとき、またはビスケットがA枚以上ない時はビスケットを叩いて1枚増やす。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Atcoder { class AtCodeeeeeeeeeeeeeeeeeeeer { static void Main(string[] args) { string[] s = Console.ReadLine().Split(' '); long K = long.Parse(s[0]); long A = long.Parse(s[1]); long B = long.Parse(s[2]); long Biscuit = 1; long umami = 0; for (int i = 1; i <= K; i++) { umami = B - A; if (umami > 2) { if((K - i)+1>=2 && Biscuit >= A) { Biscuit += umami; i++;//2ターン消費させる } else { Biscuit++; } } else { Biscuit++; } } Console.WriteLine(Biscuit); } } } |
”うまみ”はB-Aで、残りターン数は現在のターンをiとすると（K-i）+1で表現できます。ビスケットの初めの個数を1にしておくことを忘れずに。
また、この問題の制約から型をlongにしておきましょう。多分intだとオーバーフローします。
感想
初めにも書きましたが初めてC問題をコンテスト中に通せました。みんプロさん、Yahooさん好きです。
