AtCoder Beginner Contest 150 C - Count Order
1月も終わるのが早いです、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc150/tasks/abc150_c)にて開催されました、AtCoder Beginner Contest 150 C問題「C - Count Order」の問題と僕との戦闘記です。
0.はじめに
1.問題文
大きさ N の順列 ( 1 , 2 , . . . , N ) を並び替えてできる数列) P , Q があります。
大きさ N の順列は N ! 通り考えられます。このうち、 P が辞書順で a 番目に小さく、 Q が辞書順で b 番目に小さいとして、 | a − b | を求めてください。
2.制約
- 2 ≤ N ≤ 8
- P , Q は大きさ N の順列である。
- 入力は全て整数である。
3.入力例
- 入力
8 7 3 5 4 2 1 6 8 3 8 2 5 4 6 7 1
- 出力
17517
4.初見の感想
- 制約が2~8なので入力として考えられるパターンを全部列挙して、何番目かを確かめたい
- どうやって辞書順に並べ替えるか
5.学びポイント
- 順列を辞書順で作成するPermutationクラスを作った
- 再帰的処理で順列を作成
- 先頭で「1」を使う→「2,3,4」で残りの順列を作るという感じ
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; public class Permutation { //再帰の初期セットを代入する処理 public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items) { return _GetPermutations<T>(new List<T>(), items.ToList()); } //再帰関数 private IEnumerable<T[]> _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> items) { if (items.Count() == 0) { yield return perm.ToArray(); } else { foreach (var item in items) { //先頭の文字を省いて再帰を回す var result = _GetPermutations<T>(perm.Concat(new T[] { item }), items.Where(x => x.Equals(item) == false)); foreach (var xs in result) yield return xs.ToArray(); } } } } class Program { public static void Main() { int N = int.Parse(Console.ReadLine()); string[] input = Console.ReadLine().Split(); string[] input2 = Console.ReadLine().Split(); int[] A = new int[N]; int[] B = new int[N]; int[] temp = new int[N]; int pattern = 1; for (var i = 0; i < N; i++) { A[i] = int.Parse(input[i]); B[i] = int.Parse(input2[i]); //patternで順列の総数を計算 pattern *= (i + 1); //最初に入力する1~Nまでの順列を準備 temp[i] = i+1; } int[,] all_list = new int[pattern, N]; var perm = new Permutation(); int count = 0,a_num=0,b_num=0; bool A_flag = true; bool B_flag = true; foreach (var n in perm.Enumerate(temp)) { A_flag = true;B_flag = true; for (int i = 0; i < N; i++) { //辞書順でAやBと一致しないところがあればflagをfalse all_list[count, i] = n[i]; if (A[i] != n[i]) A_flag = false; if (B[i] != n[i]) B_flag = false; } count++; //辞書順をa_num,b_numに保存 if (A_flag == true) { a_num = count; } if (B_flag == true) { b_num = count; } } Console.WriteLine(Math.Abs(a_num - b_num)); } }
7.最後に
この問題みんな通してるんだけど、僕は苦手な気がします…
AtCoder Beginner Contest 150 B - Count ABC
緑色になってから毎回コンテストに緊張します、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc150/tasks/abc150_b)にて開催されました、AtCoder Beginner Contest 150 B問題「B - Count ABC」の問題と僕との戦闘記です。
0.はじめに
1.問題文
英大文字のみからなる長さ N の文字列 S があります。
S の連続する部分列 (入出力例をご覧ください) として ABC がいくつ含まれるかを求めてください。
2.制約
- 3 ≤ N ≤ 50
- S は英大文字のみからなる。
3.入力例
- 入力
33 ABCCABCBABCCABACBCBBABCBCBCBCABCB
- 出力
5
4.初見の感想
- string型は配列形式で要素にアクセスできる(input[i]の形)
- for文でABCを検出
5.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { public static void Main() { int N = int.Parse(Console.ReadLine()); string input = Console.ReadLine(); int ans = 0; for(int i = 0; i < N - 2; i++) { if (input[i] == 'A' && input[i+1] == 'B' && input[i+2] == 'C') ans++; } Console.WriteLine(ans); } }
6.最後に
最近のB問題は灰色パフォーマンスなのは驚きです…
AtCoder Beginner Contest 153 B - Common Raccoon vs Monster
最近のABCではこの辺の問題は早解き選手権ですね、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc153/tasks/abc153_b)にて開催されました、AtCoder Beginner Contest 153 B問題「B - Common Raccoon vs Monster」の問題と僕との戦闘記です。
0.はじめに
1.問題文
アライグマはモンスターと戦っています。
モンスターの体力は H です。
アライグマは N 種類の必殺技を使うことができ、 i 番目の必殺技を使うとモンスターの体力を A i 減らすことができます。 必殺技を使う以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を 0 以下にすればアライグマの勝ちです。
アライグマが同じ必殺技を 2 度以上使うことなくモンスターに勝つことができるなら Yes を、できないなら No を出力してください。
2.制約
- 1 ≤ H ≤ 109
- 1 ≤ N ≤ 105
- 1 ≤ A i ≤ 104
- 入力中のすべての値は整数である。
3.入出力例
- 入力
211 5 31 41 59 26 53
- 出力
No
4.初見の感想
- 配列Aの和がHを超えているかどうかで条件分岐です
5.学びポイント
- C#では.sum()で和が計算できます
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { public static void Main() { string[] input = Console.ReadLine().Split(); long H = int.Parse(input[0]); long N = int.Parse(input[1]); input = Console.ReadLine().Split(); long[]A = new long[N]; for(long i = 0; i < N; i++) { A[i] = int.Parse(input[i]); } long sum = A.Sum(); if (H <= sum) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } }
7.最後に
少し問題解釈に時間かかりましたので反省です…
AtCoder Beginner Contest 153 D - Caracal vs Monster
最近Official髭男dismにハマってます、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc153/tasks/abc153_d)にて開催されました、AtCoder Beginner Contest 153 D問題「D - Caracal vs Monster」の問題と僕との戦闘記です。
0.はじめに
1.問題文
カラカルはモンスターと戦っています。
モンスターの体力は H です。
カラカルはモンスターを 1 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。
- モンスターの体力が 1 なら、そのモンスターの体力は 0 になる
- モンスターの体力が X>1 なら、そのモンスターは消滅し、体力が ⌊ X / 2 ⌋ のモンスターが新たに 2 体現れる ( ⌊ r ⌋ は r を超えない最大の整数を表す)
全てのモンスターの体力を 0 以下にすればカラカルの勝ちです。
カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。
2.制約
- 1 ≤ H ≤ 1012
- 入力中のすべての値は整数である。
3.入力例
- 入力
1000000000000
- 出力
1099511627775
4.初見の感想
- 体力が2以上ある敵をすべて分裂させ体力1にした後、全部倒していく戦略をとることになる
- 体力1になるまでループなのでwhile文で回す
- 今何体いるかをnumで数えときます
- num体全員に魔法を打つのでその回数を変数ansでcountします
5.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { public static void Main() { long H = long.Parse(Console.ReadLine()); long num = 1; long ans = 0; while (H >= 2) { H = H / 2; //分裂する前に魔法をうつ回数を数える ans+=num; //2倍にモンスター数が分裂 num *= 2; } //体力1の軍団を倒す魔法の回数を計測 ans += num; Console.WriteLine(ans); } }
6.最後に
本番中は意外と手間取ったんですが、この問題灰パフォなんですね…
AtCoder Beginner Contest 150 A - 500 Yen Coins
雨模様が続いてますね、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc150/tasks/abc150_a)にて開催されました、AtCoder Beginner Contest 150 A問題「A - 500 Yen Coins」の問題と僕との戦闘記です。
0.はじめに
1.問題文
高橋君は 500 円玉を K 枚持っています。 これらの総額が X 円以上である場合は Yes を、そうでない場合は No を出力してください。
2.制約
- 1 ≤ K ≤ 100
- 1 ≤ X ≤ 105
3.入力例
- 入力
4 2000
- 出力
Yes
4.初見の感想
- 500×K>=Xを判定する
5.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { public static void Main() { string[] input = Console.ReadLine().Split(); int K = int.Parse(input[0]); int X = int.Parse(input[1]); if (500 * K >= X) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } }
6.最後に
シンプルに書けた気がします!
AtCoder Beginner Contest 153 E - Crested Ibis vs Monster
今週はこの問題が解けず悔しかったです、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc153/tasks/abc153_e)にて開催されました、AtCoder Beginner Contest 153 E問題「E - Crested Ibis vs Monster」の問題と僕との戦闘記です。
0.はじめに
1.問題文
トキはモンスターと戦っています。
モンスターの体力は H です。
トキは N 種類の魔法が使え、 i 番目の魔法を使うと、モンスターの体力を A_i 減らすことができますが、トキの魔力を B_i 消耗します。
同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。
モンスターの体力を 0 以下にすればトキの勝ちです。
トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。
2.制約
- 1 ≤ H ≤ 104
- 1 ≤ N ≤ 103
- 1 ≤ A_i ≤ 104
- 1 ≤ B_i ≤ 104
- 入力中のすべての値は整数である。
3.入力例
- 入力
9999 10 540 7550 691 9680 700 9790 510 7150 415 5818 551 7712 587 8227 619 8671 588 8228 176 2461
- 出力
139815
4.初見の感想
- とりあえずMP効率のよい魔法をたくさん使って、HPが小さくなってきたらどの魔法使うか考え始める方針を最初に思いつきました(貪欲法的な感じ)
- 効率良いけどMPを大幅に使う魔法を2回使ってMP大幅に使うより、多少効率悪い魔法でも同じくHPを綺麗に削りきることができればMP効率が良いパターンが存在する
- 上の損得の分岐点を単純に見つけるのは非常に難しい
- そもそもNが103制約なので、いつもと違う感じがする
5.学びポイント
- 「体力Nを削り切るのに、最小何MPいるか」という値を繰り返し計算で求める
- 繰り返し計算なのでDP(動的計画法)が使える
- 計算量が許せば、全探索的な手法が最強ということを体現しています
- 実は個数制限なしナップサック問題だった
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { public static void Main() { string[] input = Console.ReadLine().Split(); long H = long.Parse(input[0]); long N = long.Parse(input[1]); //DPの初期化 long[] DP = new long[H + 1]; DP[0] = 0; for(int i = 1; i <= H; i++) { DP[i] = long.MaxValue; } //各魔法ごとにDPで体力Nを削り切るのに、最小何MPいるかの表を埋める for(int i = 0; i < N; i++) { input = Console.ReadLine().Split(); long a = int.Parse(input[0]); long b = int.Parse(input[1]); for(int j = 0; j < H; j++) { //魔法を使った時のMPを計算し比較 if (DP[j] == long.MaxValue) continue; int k = (int)Math.Min(j + a, H); DP[k] = Math.Min(DP[k], DP[j] + b); } } Console.WriteLine(DP[H]); } }
7.最後に
この問題解けないの、悔しい…
AtCoder Beginner Contest 152 C - Low Elements
修論を書き上げるため競プロのペースが落ち気味の、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc)にて開催されました、AtCoder Beginner Contest 152 C問題「C - Low Elements」の問題と僕との戦闘記です。
0.はじめに
1.問題文
1 , … , N の順列 P_1 , … , P_N が与えられます。 次の条件を満たす整数 i ( 1 ≤ i ≤ N ) の個数を数えてください。
任意の整数 j ( 1 ≤ j ≤ i ) に対して、 P_i ≤ P_j
2.制約
- 1 ≤ N ≤ 2 × 105
- P_1 , … , P_N は 1 , … , N の順列である。
- 入力はすべて整数である。
3.入力例
- 入力
8 5 7 4 2 6 8 1 3
- 出力
4
4.初見の感想
- 2×105の計算量なのでO(N2)は厳しい
5.学びポイント
- 問題を言い換えると、数列の中で最後の数字が最小値であれば条件を満たす
- for文で前から見ていって、最小値を更新していき更新回数を数えていく
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main(string[] args) { int N = int.Parse(Console.ReadLine()); string[] input = Console.ReadLine().Split(); int[] P = new int[N]; for(int i = 0; i < N; i++) { P[i] = int.Parse(input[i]); } int min = int.MaxValue; int ans = 0; for(int i=0; i < N; i++) { if (min >= P[i]) { min = P[i];ans++; } } Console.WriteLine(ans); } }
7.最後に
この問題が早く解けたので成長を感じます!