AtCoder Beginner Contest 149参戦記
ということで2回目のABCに参加してきました。
結果から言うとABCDの4完でD問題で一回WA出しました。
ただしunratedになるという不幸が待ち構えていた。
まだ最初だから回数稼いでレート上げたかったのに残念。
それとunratedなの気づかなくてめっちゃ必死に考えてて終了5分前に気がついた。
A - Strings
S Tと文字を受け取ってTSと出力するだけ。
var N = Console.ReadLine().Split(); var S = N[0]; var T = N[1]; Console.WriteLine(T + S);
B - Greedy Takahashi
A(高橋くんのクッキーの枚数) B(青木くんのクッキーの枚数) K(繰り返しの回数) の形で入力が与えられて
高橋くんがクッキーを食べていく問題。
制約が1012と大きいことに注意。
高橋くんは自分のクッキーがなくなれば、青木くんのクッキーを食べていく。
なのでA>Kならば単純に高橋くんがA-K枚で青木くんはB枚
A<Kのときは不足分のK-A枚を青木くんの分から引くので高橋くん0枚 青木くんB-(K-A)枚
ただしB+A<Kならば二人共0枚になることに注意。
var amari = A - K; if(A + B < K) { A = 0; B = 0; } else { if (amari < 0) { B = B + amari; A = 0; } else { A = A - K; } }
急いで書いたら可読性の可の字もない。
C - Next Prime
Nが与えられて次に大きい素数を探す問題。
素数かどうかを判定する関数isPrimeを作っておいて単純にfor文で線形探索。
上限が1010なので、一個一個調べても余裕で間に合う。
var N = Inputer.Int1Char(); for(int i= N; i <= 1e10; i++) { if (IsPrime(i)) { Console.WriteLine(i); break; } }
D - Prediction and Restriction
無駄にソースコードが長くなってしまったので省略。
解説見るとDPで解く方法と貪欲法で解く方法の2パターン。
自分の場合は貪欲法にて解いた。
高橋君が読み取った情報は文字列 Tに対して前から順番に考えていって勝てるなら勝ちます。
前の手が邪魔しているなら次の手に邪魔にならない手を出します。
7 1 100 10 1 ssssppr
の入力例のときに前から見ていって
最初のs(1個目)は勝てるのでr出します。
次のs(2個目)は前回出した手と被ってしまうので別の手を出します。
このときに、3回目のじゃんけんに邪魔にならない手を出しておきます。(この場合pかs)
4個目のs は勝てるのでrで勝ちます。
5個目のpは勝てるのでsで勝ちます。
6個目のpは前回にsを出したので、別のものを出します。選択肢はrかpですが、次のじゃんけんで勝つためにはpを出す必要があるので、必然的にrを出すしかありません。
という感じに、前回出した手と次に出す手を参照しながら出す手を決めていくと最適値が求まります。