AtCoderチャレンジまとめ（6） - AtCoder Beginner Contest 119
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
変数名が適当なのはご愛嬌
A問題: Still TBD
文字列 S が入力されます。これは、西暦 2019 年の実在する日付を yyyy/mm/dd の形式で表したものです。(例えば、2019 年 4 月 30日は 2019/04/30 と表されます。)
Sが表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力するプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { std::string s; cin >> s; char cary[10]; s.copy(cary, 10); std::string sn(""); for (int i=0;i<10;i++){ if (i != 4) { if (i != 7){ sn += cary[i]; } } } int num = atoi(sn.c_str()); if(num>20190430){ cout << "TBD" << endl; } else { cout << "Heisei" << endl; } return 0; }
B問題:
高橋くんは N人の親戚からお年玉をもらいました。
N個の値 x1,x2,...,xN と N 個の文字列 u1,u2,...,uN が入力されます。各文字列 ui は JPY または BTC であり、xi と ui が i人目の親戚からのお年玉の内容を表します。
例えば、x1=10000, u1= JPY であれば 1 人目の親戚からのお年玉は 10000 円であり、x2= 0.10000000, u2= BTC であれば 2 人目の親戚からのお年玉は 0.1ビットコインです。
ビットコインを 1.0BTC あたり 380000.0 円として換算すると、高橋くんがもらったお年玉は合計で何円に相当するでしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N
x1 u1
x2 u2
:
xN uN
出力
高橋くんが受け取ったお年玉が合計で Y 円に相当するとき、値 Y(整数とは限らない) を出力せよ。
出力は、ジャッジの出力との絶対誤差または相対誤差が 10−5以下のとき正解と判定される。
自分の回答
#include <iostream> using namespace std; int main() { int n; cin >> n; double x; std::string u; std::string str="JPY"; double ans; for (int i; i<n;i++){ cin >> x >> u; if (std::string(u)==str){ ans += x; } else { ans += x * 380000.0; } } cout << ans << endl; return 0; }
C問題: Synthetic Kadomatsu
あなたは N 本の竹を持っています。これらの長さはそれぞれ l1,l2,...,lNです (単位: センチメートル)。
あなたの目的は、これらの竹のうち何本か (全部でもよい) を使い、長さが A,B,Cであるような 3本の竹を得ることです。そのために、以下の三種類の魔法を任意の順に何度でも使うことができます。
延長魔法: 1 MP (マジックポイント) を消費し、1 本の竹を選んでその長さを 1増やす。 短縮魔法: 1 MP を消費し、1 本の長さ 2 以上の竹を選んでその長さを 1減らす。 合成魔法: 10 MP を消費し、2 本の竹を選んで接続し 1 本の竹とする。この新たな竹の長さは接続した 2本の竹の長さの合計に等しい。(以後、この竹に対してさらに魔法を使用することもできる。)目的を達成するには、最小でいくつの MP が必要でしょうか？
入力
入力は以下の形式で標準入力から与えられる。
N A B C
l1
l2
:
lN
出力
目的の達成に必要な MP の最小量を出力せよ。
自分の回答
時間以内に解けなかった...Cが解けないのは辛い。
全探索大事。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int N; int A,B,C; long long brute_force_search(int cnt, int a, int b, int c, int L[]) { long long INF = std::pow(10, 9.0); if (cnt==N) { if ((a!=0)&&(b!=0)&&(c!=0)){ return std::abs(a-A)+std::abs(b-B)+std::abs(c-C)-30; } else { return INF; } } vector<long long> ansc(4); ansc[0] = brute_force_search(cnt+1, a, b, c, L); ansc[1] = brute_force_search(cnt+1, a+L[cnt], b, c, L)+10; ansc[2] = brute_force_search(cnt+1, a, b+L[cnt], c, L)+10; ansc[3] = brute_force_search(cnt+1, a, b, c+L[cnt], L)+10; int min = *std::min_element(ansc.begin(), ansc.end()); return min; } int main() { cin >> N >> A >> B >> C; int len[N]; for (int i; i<N;i++){ cin >> len[i]; } long long ans; ans = brute_force_search(0, 0, 0, 0, len); cout << ans << endl; return 0; }
ちょっとだけ解説
a,b,c=0の状態から始まり初期の１本追加するときに10を足しているので、
最後にABC3本分の30を引いているのと、
一本も追加しない場合は成り立たないのでINFとしてる。
D問題: Lazy Faith
東西方向に伸びる道路に沿って A 社の神社と B 軒の寺が建っています。 西から i 社目の神社は道路の西端から si メートルの地点に、西から i 軒目の寺は道路の西端から tiメートルの地点にあります。
以下の Q個の問いに答えてください。
問 i (1≤i≤Q): 道路の西端から xi メートルの地点から出発して道路上を自由に移動するとき、神社一社と寺一軒を訪れるのに必要な最小の移動距離は何メートルか？ (必要数を超えた数の寺社を通過してもよい。)
入力
入力は以下の形式で標準入力から与えられる。
A B Q
s1
:
sA
t1
:
tB
x1
:
xQ
出力
Q 行出力せよ。i 行目に問 i への答えを出力すること。
自分の回答
これも時間以内にとけなかった。二分探索がポイント。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { int A,B,Q; cin >> A >> B >> Q; vector<long long> jin(A+2); vector<long long> tera(B+2); long long INF = std::pow(10, 18); jin[0] = -INF; jin[A+1] = INF; tera[0] = -INF; tera[B+1] = INF; for (int i=1; i<A+1;i++){ cin >> jin[i]; } for (int i=1; i<B+1;i++){ cin >> tera[i]; } long long q; for (int i; i<Q;i++){ cin >> q; long long b = upper_bound(jin.begin(), jin.end(), q) - jin.begin(); long long d = upper_bound(tera.begin(), tera.end(), q) - tera.begin(); long long ans = INF; vector<long long> jinv{jin[b-1],jin[b]}; vector<long long> terav{tera[d-1],tera[d]}; vector<long long> dv(3); for (auto j: jinv) { for (auto t: terav){ dv[0] = std::abs(j-q)+std::abs(t-j); dv[1] = std::abs(t-q)+std::abs(j-t); dv[2] = ans; ans = *std::min_element(dv.begin(), dv.end()); } } cout << ans << endl; } return 0; }
二分探索参考
所感
Cが解けずに時間が経過すると、めっちゃ焦る。。。冷静に解決のための手段を一個ずつ洗い出せるようにしないと。
まずいろんなアルゴリズムの知識を網羅的につけて正しく選択できるところを目指そう。
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頑張る。
あとはちょっとした初期化の書き方だったり、読みやすくて、短いコードを意識して書いていきたい。
AtCoderチャレンジまとめ（4） - みんなのプロコン 2019
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チャレンジコンテスト
Yahoo Programming Contest 2019 - AtCoder
変数名が適当なのはご愛嬌
問題A: Anti-Adjacency
1 以上 N 以下の異なる整数を、差が 1 の整数をともに選ばないように K 個選ぶことができるか判定してください。
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
整数を K 個選ぶことができるなら YES を、そうでないなら NO を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { int n,k; cin >> n >> k; int ans; ans = (n+1)/2; if(ans>=k){ cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }
問題B: Path
4 つの街があり、順に 1,2,3,4 と番号が付いています。 道が 3 本あり、i 本目の道は異なる街 ai,bi を双方向に結んでいます。 同じ街の対の間を結ぶ道が複数あることはありません。
街同士を行き来する手段は、道以外にはありません。 どの2つの街の間も、道を何本か通ることで行き来することができます。
すべての道をちょうど 1回ずつ通ることですべての街を訪れることが可能かどうか判定してください。
入力
入力は以下の形式で標準入力から与えられる。
a1 b1
a2 b2
a3 b3
出力
すべての道をちょうど 1 回ずつ通ることですべての街を訪れることが可能なら YES を、そうでないなら NO を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { int a1,b1; cin >> a1 >> b1; int a2,b2; cin >> a2 >> b2; int a3,b3; cin >> a3 >> b3; if (a1==a2 || a1==b2) { if(a1==a3 || a1 ==b3){ cout << "NO" << endl; return 0; } } if (b1==a2 || b1==b2) { if(b1==a3 || b1 ==b3){ cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0; }
解説
問題の構成から、異なる街を選ぶこと、同じ道は作らないことから、計3セットのa,bの中で同じ数字が3つない場合にすべて訪れることを発見。
つまり、3セットのすべてに同じ数が含んでいるものを除く。
問題C: When I hit my pocket...
すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K回行います。
・持っているビスケットを叩き、1枚増やす
・ビスケット A枚を 1円に交換する
・1円をビスケット B 枚に交換する
K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値を出力せよ。
自分の回答
#include <iostream> using namespace std; int main() { long long k,a,b; cin >> k >> a >> b; long long ans1; ans1 = (k-a+1) / 2; ans1 = (ans1-1) * (b-a); ans1 = ans1 + b + (k-a+1)%2; long long ans2; ans2 = k+1; if(ans1 > ans2){ cout << ans1 << endl; } else { cout << ans2 << endl; } return 0; }
解説
A+2 < Bのときは、お金に交換→ビスケット生成がより増やせる。
そうでないときは、交換せずにビスケットを叩きまくる。
A+2 < Bのときは、基本的に最初の一回交換するまでは叩いて増やす必要があるが、その後は
・ ビスケット A枚を 1円に交換する
・ 1円をビスケット B 枚に交換する
というように2回で(B-A)個を増やすことができる。
D: Ears
数直線上にすぬけ君がいます。すぬけ君は L個の耳を持っており、以下の条件を満たしながら数直線上を連続的に散歩します。
・座標 0未満の点や座標が Lより大きい点を通ることはない ・整数座標の点で散歩を開始し、整数座標の点で散歩を終了する ・整数座標の点でのみ、進む方向を変えることができるすぬけ君は、座標が整数 iを用いて i−0.5 と表される点を通るたびに、i 番目の耳に石を 1個入れます。
すぬけ君が散歩を終えた後、りんごさんは以下の操作を好きな順に何度でも繰り返すことで、 各 iに対しすぬけ君の i 番目の耳には Ai個の石が入っているようにしたいです。
・すぬけ君の耳をひとつ選び、石を 1個入れる ・石が 1個以上入っているすぬけ君の耳をひとつ選び、石を 1個取り出すすぬけ君の散歩の方法をりんごさんが好きに決められるとき、必要な操作の回数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
L
A1
:
AL
出力
必要な操作の回数の最小値を出力せよ。
入力例
4
1
0
2
3
出力例
1
自分の回答
これは時間以内に解けなかったので、解説を見て検討しました。
#include <iostream> #include <vector> #include <algorithm> using namespace std; long long cost(long long* A, const long long& index, const long long& area){ if (area==0 || area==4) { return A[index]; } else if (area==1 || area==3) { if (A[index]==0) { return 2; } else if(A[index]%2==0) { return 0; } else { return 1; } } else if (area==2){ if (A[index]%2==0){ return 1; } else { return 0; } } } int main() { long long n; cin >> n; long long A[n]; for(long long i=0;i<n;i++){ cin >> A[i]; } vector< vector<long long> > dp; dp.resize(n); for(long long i=0; i<n; i++){ dp[i].resize(5); } for(int j=0;j<5;j++){ dp[0][j] = cost(A,0,j); } for(long long i=1;i<n;i++){ dp[i][0] = dp[i-1][0]+cost(A,i,0); for(int j=1;j<5;j++){ long long mindp = *std::min_element(dp[i-1].begin(), dp[i-1].begin()+j+1); dp[i][j] = min(mindp+cost(A,i,j), dp[i][j-1]); } } long long ans = *std::min_element(dp[n-1].begin(), dp[n-1].end()); cout << ans << endl; return 0; }
解説
以下の5つにわけて、下図にあるような考え方、動的計画法（DP）で解きました。
まず、すぬけくんのスタート、ゴール位置をS,Tとし、散歩中の最小・最大位置をD,Uとします。
i <= DのときはXi=0なので、この範囲のコストはAiそのまま。りんごさんはAi回操作必要。
D < i <= Sのときは、Xiは0でない偶数であればコスト0。0であれば行って戻ってこないといけないのでコスト2。奇数の場合コスト1。
S < i < Tのときは、Xiが奇数ならばコスト0。偶数ならばコスト1。
T < i <= Uのときも2.と同様。Xiは0でない偶数であればコスト0。0であれば行って戻ってこないといけないのでコスト2。奇数の場合コスト1。
U < iのときも1.と同様。この範囲のコストはAiそのまま。
このコストの考え方を用いて、入力例を用いて示すと
のようなコストマップがかけ、緑☆のように左列と上ブロックの情報を用いてすべてのブロックが計算できる。
最後に最終列の最小値を求めればそれが答え。
問題E: Odd Subrectangles
問題F: Pass
所感
すぬけくんがバケモノ過ぎて問題解くときに焦った笑
メモ時の大量の耳がある、すぬけくん↓↓↓
Eigen事始め
やりたいこと
C++で行列計算を高速に行いたい！
ので、行列計算ライブラリEigenを学ぶ。
教科書
インストール
Eigen からダウンロードする。
もしくはROSが入っている場合、
/usr/include/eigen3/Eigen
にEigenがインストールされている。
コンパイル方法
g++ -I /path/to/eigen/ my_program.cpp -o my_program
Getting Started
#include <iostream> #include <Eigen/Dense> int main() { // 2行2列の行列作成 Eigen::Matrix2d m(2,2); m(0,0) = 3; m(1,0) = 2.5; m(0,1) = -1; m(1,1) = m(1,0) + m(0,1); std::cout << m << std::endl; // 1行2列のベクトル作成 Eigen::Vector2d v(1,2); std::cout << v << std::endl; // 上記行列とベクトルの積 std::cout << "m * v =" << std::endl << m * v << std::endl; }
出力
3 -1 2.5 1.5 1 2 m * v = 1 5.5
Dynamicに生成
以下のように記述することで行列サイズを動的に決めることができる
Eigen::MatrixXd m = MatrixXd::Random(3,3);
コンマで初期化
Matrix3f m; m << 1, 2, 3, 4, 5, 6, 7, 8, 9; std::cout << m;
便利機能まとめ
配列からEigenに変換
配列からEigenに変換するのに便利なEigen::Map
int array[8]; for(int i = 0; i < 8; ++i) array[i] = i; cout << "Column-major:\n" << Map<Matrix<int,2,4> >(array) << endl; cout << "Row-major:\n" << Map<Matrix<int,2,4,RowMajor> >(array) << endl;
出力
Column-major: 0 2 4 6 1 3 5 7 Row-major: 0 1 2 3 4 5 6 7
クオータニオン計算
参考なるブログ
所感
これは便利 ！ 使いやすいし、多機能
背中がITAI...
AtCoderチャレンジまとめ（3） - NIKKEI Programming Contest 2019
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チェレンジコンテスト
全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder
問題A : Subscribers
私たちは、新聞の購読に関する調査を行いました。 具体的には、調査の対象者 N 人に対し、それぞれ次の 2つの質問を行いました。
質問 1 : あなたは新聞 X を購読しているか？ 質問 2 : あなたは新聞 Y を購読しているか？その結果、質問 1 に対して「はい」と回答した人の数は A 人、質問 2 に対して「はい」と回答した人の数は B人でした。
このとき、調査の対象者のうち新聞 X, Y の両方を購読している人の数は最大で何人であり、また最小で何人であると考えられるでしょうか？
この問いに答えるプログラムを書いてください。
入力は以下の形式で標準入力から与えられる。
N
A
B
自分の回答
#include<iostream> using namespace std; int main(){ int a,b,c; cin >> a >> b >> c; int amax; int amin; if(a >= b+c){ amin = 0; }else{ amin = b+c - a; } amax = min(b,c); cout << amax << " " << amin << endl; return 0; }
問題B : Touitsu
三つの文字列 A,B,C が与えられます。これらはそれぞれ、英小文字からなる長さ Nの文字列です。
私たちの目標は、これら三つの文字列をすべて等しくすることです。そのために、あなたは次の操作を繰り返し行うことができます。
操作: 文字列 A,B,Cのうち一つを選び、さらに 1 以上 N 以下の整数 i を指定する。そして、選んだ文字列の先頭から i文字目を別の何らかの英小文字に変更する。
目標を達成するためには最小で何回の操作が必要でしょうか？
入力は以下の形式で標準入力から与えられる。
N
A
B
C
自分の回答
#include<iostream> #include <set> using namespace std; int main(){ int n; cin >> n; string s1,s2,s3; cin >> s1 >> s2 >> s3; int ans=0; for(int i=0;i<n;i++){ set<int> values; values.insert(s1[i]); values.insert(s2[i]); values.insert(s3[i]); ans += values.size() - 1; } cout << ans << endl; return 0; }
問題C : Different Strokes
高橋くんと青木さんの前に N 皿の料理が置かれています。 便宜上、これらの料理を料理 1、料理 2、…、料理 Nと呼びます。
高橋くんが料理 iを食べると彼は Ai ポイントの 幸福度 を得ます。 また、青木さんが料理 i を食べると彼女は Biポイントの幸福度を得ます。
彼らは、高橋くんから始めて交互に、料理を 1皿ずつ選んで食べることを料理が尽きるまで続けます。 ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。
このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？
入力は以下の形式で標準入力から与えられる。
N
A1
B1
:
AN
BN
自分の回答
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n; cin >> n; int a[n],b[n]; for(int i=0;i<n;i++){ cin >> a[i] >> b[i]; } std::vector<int> vec(n); long sumao=0; for (int i = 0; i < n; ++i) { vec[i] = a[i] + b[i]; sumao += b[i]; } std::sort(vec.begin(),vec.end(),std::greater<int>()); //降順ソート long sumta=0; for(int i=0;i<n;i++){ if(i % 2 == 0){ sumta += vec[i]; } } cout << sumta - sumao << endl; return 0; }
longで足りないこともあるから、競プロの人はlong longを使っている人が多い。
問題D : Restore the Tree
N 頂点の根付き木 (注記を参照) があり、その頂点には 1 から N までの番号が振られています。 根以外の各頂点には、その親から一本の有向辺が伸びています。 なお、根は頂点 1とは限りません。
高橋くんは、このグラフに M本の新たな有向辺を書き加えました。 書き足された各辺 u→v は、ある頂点 u からその子孫であるような頂点 vに向かって伸びています。
高橋くんが辺を書き加えたあとの N頂点 N−1+M 辺の有向グラフが与えられます。 より具体的には、N−1+M 組の整数のペア (A1,B1),...,(AN−1+M,BN−1+M) が与えられ、これらは i 番目の辺が頂点 Ai から頂点 Biに向かって伸びていることを表します。
元の根付き木を復元してください。
入力は以下の形式で標準入力から与えられる。
N
M
A1
B1
:
AN−1+M
BN−1+M
自分の回答
TDB 時間ができたら追記します。
参考: 有向非巡回グラフ（DAG）の意味とトポロジカルソート - 具体例で学ぶ数学
所感
やっぱりD問題が難しい。今回はトポロジカルソートを知らないと結構キツい。。。
D問題を解けるように頑張る!
AtCoderチャレンジまとめ（２） - AtCoder Beginner Contest 116
やりたいこと
そんなわけでAtCoderにチャレンジ ！
チェレンジコンテスト
AtCoder Beginner Contest 116 - AtCoder
変数名適当でごめんなさい。。。初めてのAtCoder。
問題A : Right Triangle
直角三角形 ABC があります。∠ABC=90°
です。
三角形 ABC の三辺の長さである |AB|,|BC|,|CA| が与えられるので、直角三角形 ABC
の面積を求めて下さい。
ただし、三角形 ABC の面積は整数となることが保証されています。
自分の回答
#include<iostream> using namespace std; int main(){ int a,b,c; cin>>a>>b>>c; int ans; ans = a*b/2; cout << ans << endl; return 0; }
問題B : Collatz Problem
数列 a={a1,a2,a3,......}
は、以下のようにして定まります。
初項 sは入力で与えられる。
関数 f(n) を以下のように定める: n が偶数なら f(n)=n/2、n が奇数なら f(n)=3n+1。
i=1のとき ai=s、i>1 のとき ai=f(ai−1)である。
このとき、次の条件を満たす最小の整数 m
を求めてください。
am=an(m>n)を満たす整数 n が存在する。
自分の回答
#include<iostream> #include <set> using namespace std; int main(){ int a; cin>>a; set<int> values; int ans = a; for(int i=0; i < 100000000; ++i){ values.insert(ans); if(ans%2==0){ ans = ans / 2; }else{ ans = 3 * ans + 1; } if (values.size()!=i+1){ break; } } cout << values.size() + 1 << endl; return 0; }
先生の回答
#include<iostream> #include <set> using namespace std; int main(){ int a; cin>>a; set<int> values; int ans = a; while(values.count(ans) == 0){ values.insert(ans); if(ans%2==0){ ans = ans / 2; }else{ ans = 3 * ans + 1; } } cout << values.size() + 1 << endl; return 0; }
- setのcountを使って重複があるかどうかを調べている（values.count(ans) == 0）。こっちのほうがイイね！
問題C : Grand Garden
花壇に N 本の花が咲いており、それぞれ 1,2,......,N と番号が振られています。最初、全ての花の高さは 0 です。 数列 h={h1,h2,h3,......} が入力として与えられます。以下の「水やり」操作を繰り返すことで、すべての k(1≦k≦N) に対して花 k の高さを hk
にしたいです。
整数 l,rを指定する。l≦x≦r を満たすすべての x に対して、花 x の高さを 1 高くする。
条件を満たすための最小の「水やり」操作の回数を求めてください。
先生の回答
#include<iostream> using namespace std; int main(){ int n; cin>>n; int a[n]; for(int i=0; i < n; i++){ cin>>a[i]; } int ans = 0; int active = 0; for(int i;i<n;i++){ if(active>=a[i]){ active = a[i]; }else{ ans += a[i]-active; active = a[i]; } } cout << ans << endl; return 0; }
とてもシンプル！素晴らしい。
問題D : Various Sushi
N 個の寿司があり、それぞれの寿司には「ネタ」ti と「おいしさ」di のパラメータが設定されています。 あなたはこの N 個の寿司の中から K
個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。
「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を x
としたとき、x∗x
である。
あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。
回答
TBD 時間あるとき追記します〜
所感
D問題解けるようになりたい。
AtCoderチャレンジまとめ（１）
やりたいこと
そんなわけでAtCoderにチャレンジ ！ の前の準備笑
教科書
けんちょんさんわかりやすい記事ありがとうございます！
計算オーダー
名言 : 標準ライブラリがあっても、中身の計算量を意識しよう！ ex: list (Python) からの検索処理は遅い
計算回数の目安: 1秒間で処理できる for 文ループの回数は、100,000,000 回程度(10の8乗)
計算時間の比較: logn < n < nlogn < n2 < n3 < 2n < n!
- 実用的なレベルとして、n3あたりが限界
全探索
幅優先探索 : グラフ を始点から近い順に1つずつ調べていく探索法
- 深い階層まで一本道で探索する場合は幅優先探索が有用。 ex: 迷路でスタートからゴールにたどり着きたいケース
深さ優先探索 : ある状態から始めて、遷移できなくなるまで状態遷移を続け、遷移できなくなったら一つ前の状態に戻って・・・を繰り返すことで、 グラフ の全頂点を漏れなく調べる探索法
- 1つの階層に大量のノードが存在する場合は深さ優先探索が有用。 ex: 辞書順で最初の解を求めるケース
があり、どちらを選択するかは問題に依る。
ソート
既存のライブラリの性能が高い。 ex: C++ の std::sort() はクイックソートをベースとしながらも最悪時の計算量も O(nlogn)O(nlogn) になっている
安定ソート : 同等なデータのソート前の順序が、ソート後も保存されるもの
ソート種類
- 挿入ソート : 基本的にはそんなに速くない安定ソート。
- マージソート : 高速な安定ソート。
- クイックソート : 安定ソートでないが高速。C++ の std::sort() もクイックソートがベース。
- ヒープソート : 最小値や最大値を常に取り出せるようなアルゴリズムで、安定ソートではない。
参考: ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
bit演算
45をbitで表すと？ : 0b00101101(0bは二進数を表す)
AND : int a,b; cout << a&b << endl;
OR : int a,b; cout << a|b << endl;
& ビットごとの AND | ビットごとの OR ^ ビットごとの XOR ~ ビットごとの反転（1 の補数） << 左シフト >> 右シフト
bitsetsで出力 : int a,b; cout << bitset<8>(a&b) << endl; // 00001001のように表示される
a ,b ,c 番目のフラグが立っている状態 : (1<<a) | (1<<b) | (1<<c)
マスク演算 : bit & mask ; // mask で表された部分の情報のみを取り出したもの
所感
次は練習問題をいろいろ解いてみよう。 D問題普通に難しい。。。
