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
所感
すぬけくんがバケモノ過ぎて問題解くときに焦った笑
メモ時の大量の耳がある、すぬけくん↓↓↓
