AtCoderチャレンジまとめ（5） - AtCoder Beginner Contest 118
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
変数名が適当なのはご愛嬌
A : A - B +/- A
正整数 A,Bが与えられます。
Aが B の約数なら A+B を、そうでなければ B−A を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
A が B の約数なら A+B を、そうでなければ B−A を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { int a,b; cin >> a >> b; if(b%a==0){ cout << a+b <<endl; } else { cout << b-a<< endl; } return 0; }
B : Foods Loved by Everyone
カツサンドくんはオムライスが好きです。
他にも明太子や寿司、クリームブリュレやテンダーロインステーキなどが好きで、これらの食べ物は全て、誰もが好きだと信じています。
その仮説を証明するために、N人の人に M種類の食べ物について好きか嫌いかの調査を行いました。
調査の結果、i番目の人は Ai1 番目, Ai2 番目, ..., AiKi番目の食べ物だけ好きだと答えました。
N人全ての人が好きだと答えた食べ物の種類数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N M
K1 A11 A12 ... A1K1
K2 A21 A22 ... A2K2
:
KN AN1 AN2 ... ANKN
出力
N 人全ての人が好きだと答えた食べ物の種類数を出力せよ。
自分の回答
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n,m; cin >> n >> m; vector<int> v; for(int i=0;i<n;i++){ int a; cin >> a; for (int j=0;j<a;j++){ int b; cin >> b; v.push_back(b); } } int ans=0; for(int i=1;i<m+1;i++){ int n_count = std::count(v.begin(), v.end(), i); if (n_count==n){ ans += 1; } } cout << ans << endl; return 0; }
C : Monsters Battle Royale
N 体のモンスターが居て、それぞれ 1,2,...,Nと番号付けられています。
はじめ、モンスター iの体力は Aiです。
以降、体力が 1以上のモンスターを生きているモンスターと呼びます。
生きているモンスターが 1体になるまで以下を繰り返します。
- ランダムに 1体の生きているモンスターがランダムに別の生きているモンスターに攻撃します。
- その結果、攻撃されたモンスターの体力を攻撃したモンスターの体力と同じ値だけ減らします。
最後に生き残ったモンスターの最終的な体力の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N
A1 A2 ... AN
出力
最後に生き残ったモンスターの最終的な体力の最小値を出力せよ。
自分の回答
基本的に体力の小さい２つのみに着目して解けることに気づいた。
体力の小さい順にソートして、 2番目に1番小さいもので割り切れれば、最小体力は1番目のままなので、2番目を削除。
割り切れない場合は、2番目 = 2番目-1番目とし、2番目を更新する。そして、2番目が1番目を下回ったら再度sort。
以降これらの繰り返しで最後の一つが残るまで繰り返す。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { long long n; cin >> n; vector<long long> a(n); for(long long i;i<n;i++){ cin >> a[i]; } std::sort(a.begin(),a.end()); while(true){ if(a.size()==1){ break; } if (a[1]%a[0]==0){ a.erase(a.begin()+1); } else { a[1] = a[1] - a[0]; if(a[1]<a[0]){ std::sort(a.begin(),a.end()); } } } cout << a[0] << endl; return 0; }
D : Match Matching
ちょうど N本のマッチ棒を使って作れる整数の中で最大のものを求めてください。
ただし、以下の条件を満たさなければなりません。
作る整数の各桁は、1から 9 までの数字のうち A1,A2,...,AM(1≤Ai≤9)のいずれかでなければならない。
数字 1,2,3,4,5,6,7,8,9を 1 つ作るには、それぞれちょうど 2,5,5,4,5,6,3,7,6 本のマッチ棒を使う。
入力
入力は以下の形式で標準入力から与えられる。
N M
A1 A2... AM
出力
問題文の条件下でちょうど N本のマッチ棒を使って作れる整数の最大値を出力せよ。
けんちょんさんの回答の写経
いつもありがとうございます!!! そして、またしてもDが解けない。。。
教科書: AtCoder ABC 118 D - Match Matching (400 点) - けんちょんの競プロ精進記録
以下のかんたんな例を用いて動的計画法の内容を理解。
入力例:
8 2
3 7
3を作るのにマッチ5本、7を作るのにマッチ3本。なので、73が答えだとわかる。
これをけんちょんさんのDP（iはマッチの本数で dpは作れる数字が入る）で考えると
i = 0の時 dp[5] = 3, dp[3] = 7 i =1,2の時は作れる数字がないのでスキップ i = 3の時 dp[3+5] = 73, dp[3+3] = 77 i = 4の時は作れる数字がないのでスキップ i = 5の時 dp[5+5] = 33, dp[5+3] = 73 (*) ここで前のdp[8]に73が入っているので、37と比較して大きい73を入れる i = 6の時 dp[6+5] = 773, dp[6+3] = 777 i = 7の時は作れる数字がないのでスキップ i = 8の時 dp[8+5] = 733, dp[8+3] = 737
よってdp[8]=73より73が答えだとわかる。8本与えられたときに作れる最大の数。
以下写経コード。
#include <iostream> #include <string> #include <vector> using namespace std; const string MINUS_INF = "-"; void update_char_max(string &a, string b){ if (a == MINUS_INF){ a = b; } else if (a.size() < b.size()) { a = b; // stringの比較のため、まず桁違いのものは更新 } else if (a.size() == b.size()) { if (a < b) { a = b; // 同じ桁のstringは純粋に値の比較 } } } long long match_map[10] = {2,5,5,4,5,6,3,7,6}; string dp[100000]; int main() { int n, m; cin >> n >> m; vector<int> a(m); for (int i=0; i<m; ++i) { cin >> a[i]; } // 初期化 for (int i=0; i<100000; ++i) { dp[i] = MINUS_INF; } // 初期条件 dp[0] = ""; // DP ループ for (int i = 0; i <= n; ++i) { if (dp[i] == MINUS_INF) continue; for (auto ae : a) { update_char_max(dp[i+match_map[ae-1]], dp[i]+(char)('0'+ae)); } } cout << dp[n] << endl; }
所感
autoが便利だし、どんどん使っていこう。
動的計画法を使いこなせるようになったら、Dの解ける問題が増える気がする。DP頑張る。
あとはちょっとした初期化の書き方だったり、読みやすくて、短いコードを意識して書いていきたい。
