部内バチャ
パソコン甲子園プログラミング部門の対策として8/29に部内でAtCoderVirtualContestを開催しました．
その時の問題の解説です．
A - Grouping 2 (AtCoder Beginner Contest 089)
問題文
ある学校には、N人の生徒がいます。生徒たちをいくつかのグループに分け、グループごとにあるテーマについて話し合ってもらうこととなりました。あなたは、 2 人以下のグループだと効果的な話し合いが出来ないと考えており、なるだけ多くのグループを 3 人以上にしたいです。生徒たちを上手く分けて、3人以上のグループの数を最大化してください。
制約
- 1 ≤ N ≤ 1000
- 入力は全て整数
解説
Nを3で割ってしまえば良い．小数点以下はint型であれば自動的に切り捨てられるのでそのままで問題ない．
回答コード
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
cout << n/3 << endl;
}
A - New Year (AtCoder Beginner Contest 084)
問題文
12月30日のM時から次の年になるまでは何時間か、求めてください。
制約
- 1 ≦ M ≦ 23
- 入力は全て整数
解説
12月30日から翌年になるまでの時間は48時間です．なので48からMを引いた値が解になります．
回答コード
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
cout << 48-n << endl;
}
A - One out of Three (AtCoder Beginner Contest 075)
問題文
3つの整数A,B,Cが与えられます。
A,B,Cのうち2つは同じ整数であり、残りの1つだけ異なる整数です。
例えば、A=5,B=7,C=5の場合、A,Cの 2つは同じ整数であり、Bは1つだけ異なる整数です。
3つの整数のうち、1つだけ異なる整数を求めてください。
制約
- 100 ≦ A,B,C ≦ 100
- A,B,Cは整数
- 入力は問題文の条件を満たす
解説
スマートな解き方はありません．脳筋です．
A==BならC,B==CならA,A==CならBが解となります．
回答コード
#include<iostream>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
if(a == b)cout << c << endl;
else if(b == c)cout << a << endl;
else cout << b << endl;
}
A - Sharing Cookies (AtCoder Beginner Contest 067)
問題文
すぬけくんは3匹のヤギにクッキーを渡したいです。
すぬけくんはA枚のクッキーが入った缶と、B枚のクッキーが入った缶を持っています。すぬけくんはA,B,A+Bのいずれかの枚数のクッキーをヤギたちに渡すことができます。
3匹のヤギが同じ枚数ずつ食べられるようにクッキーを渡すことが可能かどうか判定してください。
制約
- 1 ≤ A,B ≤ 100
- A,Bはいずれも整数
解説
これも脳筋.bool型(0の時false,1の時にtrue)を使用することでif文の条件式が簡潔になる．
回答コード
#include<iostream>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
if(a%3 && b%3 && (a+b)%3)cout << "Impossible" << endl;
else cout << "Possible" << endl;
}
A - Harmony (AtCoder Beginner Contest 135)
問題文
相違なる整数A,Bがあります。
|A−K|=|B−K|となるような整数Kを出力してください。
そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力してください。
制約
- 入力は全て整数である。
- $0 ≤ A,B ≤ 10^9$
- AとBは相違なる。
解説
Kの値は必ずAとBの平均となる．平均は(A+B)/2となる．
この時A+Bが奇数であれば整数Kは存在しない
回答コード
#include<iostream>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
if((a+b)%2)cout << "IMPOSSIBLE" << endl;
else cout << (a+b)/2 << endl;
}
A - Happy Birthday! (AtCoder Beginner Contest 100)
問題文
もうすぐE869120君とsquare1001君の16才の誕生日が来る.
そこで,AtCoder王国の高橋君は, 円形のケーキ 1個に放射状に切れ目を入れ16等分したものを, 彼らにプレゼントした.
E869120君はそのうちA切れ、square1001 君はB切れを食べようとした.
しかし, ケーキと一緒についていた紙を見ると, 「同じ人が隣り合う2切れのケーキを両方取ってはならない」と書かれていた.
さて、彼らは紙に書かれたことを守って、2人とも食べたい数のケーキを取ることができるだろうか？
制約
- A,Bは1以上16以下の整数
- A+Bは16以下である.
解説
となり合わなければ十分なのでそれぞれ偶数と奇数で分けてとって行けば相手の個数関係なく最大数のケーキを獲得可能．
なので今回の場合だとどちらも食べることの可能な最大ケーキは16/2,すなわち8である．
回答
#include<iostream>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
if(a>8 || b>8)cout << ":(" << endl;
else cout << "Yay!" << endl;
}
B - Long Long Ago (技術室奥プログラミングコンテスト#4 Day1)
問題文
昔々、Paken王国にはアゴが長い王様がいました。
王様が結婚相手を募集したところ、N人の候補が応募しました。
王様は、「自分よりアゴが短い候補者の中で、最もアゴが長い人」と結婚すると決めました。
王様のアゴの長さはK、i番目 (1≤i≤N) の応募者ののアゴの長さは$a_i$です。
王様は何番目の人と結婚するでしょうか？
ただし、王様よりアゴが短い候補者がいない時は−1と出力してください。
ただし、アゴの長さが王様を含め同じ人はいないものとします。
制約
- 入力は全て整数である。
- $1≤N≤2×10^5$
- $1≤K,a_i≤10^9$
- $a_i≠a_j(i≠j)$
- $a_i≠K$
解説
結構相手の候補人数のNと王様の顎の長さの変数であるKを入力したのち．
N回入力を受け取り,王様より顎が短く現状の最大の顎の長さを持つ結婚相手の顎の長さを超える長さの値が入力されるたびに現状最大の顎の長さを更新し，その番号を記録する．そうすれば最終的な顎が最長の結婚相手の長さが記録されてるはずなのでそれを出力する．
回答コード
#include<iostream>
using namespace std;
int main(){
int n,k;
cin >> n >> k;
int ans = -1; // 現状，条件を満たす最長の顎の長さの結婚相手の番号を格納
int l = 0; // 現状，条件を満たす結婚相手の最長の顎の長さ
for(int i=0;i<n;i++){
int a;
cin >> a;
if(l < a && a < k){
ans = i+1; //番号の更新
l = a; //顎の長さの更新
}
}
cout << ans << endl;
}
B - ∵∴∵ (AtCoder Beginner Contest 058)
問題文
すぬけ君は新しくできたプログラミングコンテストに会員登録しました。 登録に使ったパスワードを覚えておく自信が無かったすぬけ君は、 手元の紙にパスワードをメモしておくことにしました。 ただし、そのままメモをすると誰かにパスワードを盗まれてしまうかもしれないので、 文字列の偶数番目の文字と奇数番目の文字をそれぞれ別々の紙にメモしておくことにしました。パスワードの奇数番目の文字だけを順番を変えずに取り出した文字列Oと、偶数番目の文字だけを順番を変えずに取り出した文字列Eが与えられます。すぬけ君のかわりにパスワードを復元してください。
制約
- O,Eは小文字のアルファベット('a'-'z')からなる文字列
- 1≤|O|,|E|≤50
- |O|−|E|は0または1である。
解説
文字列をO,Eを交互にE.size()回出力する．
|O|!=|E|であれば余分Oが一つ余分に多いのでOの最後の最後の要素を余分に出力する必要あり．
回答コード
#include<iostream>
using namespace std;
int main(){
string o,e;
cin >> o >> e;
for(int i=0;i<e.size();i++){
cout << o.at(i) << e.at(i);
}
if(o.size()!=e.size())cout << o.at(o.size()-1);
cout << endl;
}
B - Tensai (CODE FESTIVAL 2018 qual B)
問題文
CODE FESTIVAL 2015本戦で, 「『天才』と書かれた大きな紙を持って立つ」という面白い行動をし, みんなを笑わせた人がいた.
そこで,CODE FESTIVAL 2018 本戦参加者のN人全員が同じ行動をして, 集合写真を撮ることにした.
それぞれの人は「字の綺麗さ」「顔の面白さ」の2つの値を持ち,i番目の人の「字の綺麗さ」は$a_i$,「顔の面白さ」は$b_i$である. 「写真の好感度」は, 全ての人の (字の綺麗さ) × (顔の面白さ) の合計になる.
本戦の参加者たちは, 「写真の好感度」を最大化しようと思った. 「顔の面白さ」は変えることはできないが, ある人が1回トレーニングをすると, この人の「字の綺麗さ」は1上がる.
全ての人のトレーニング回数の合計をX回以内にしなければならないとき, 写真の好感度の最大値を求めなさい.
制約
- Nは1以上100以下の整数
- Xは0以上100以下の整数
- $a_i$ , $b_i (1≤i≤N)$は 1以上 100以下の整数
解説
この問題で写真の好感度を最大にする手法は顔が面白い人にトレーニングをすべて集中させた場合である．
なのでこの解は 元々の合計 と トレーニングにより上昇した数値 の和となる．
トレーニング回数に上昇した数値は 最も面白い顔の数値に最大可能トレーニング数 をかけたものである
回答コード
#include<iostream>
using namespace std;
int main(){
int n,x;
cin >> n >> x;
int ans = 0; //トレーニングをしない場合の写真の好感度
int face = 0; //最も面白い顔の得点
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
ans += a*b;
face = max(face,b);
}
cout << ans + face*x << endl;
}
A - Jumping!! (技術室奥プログラミングコンテスト#4 Day2)
問題文
座標平面上にAliceがいます。彼女のいる座標は (0,0)です。
彼女は「桂馬飛び」のみで座標 (x,y)に行けるでしょうか。行ける場合は、最小で何回の桂馬飛びで行けるのかを求めてください。なお、1回の「桂馬飛び」とは以下の移動のことを指します。
- 座標(a,b)にいる時、座標 (a+1,b+2)または (a−1,b+2)に移動する。
制約
- 入力は全て整数である。
- $10^5≤x,y≤10^5$
解説
座標(x,y)にたどり着ける場合，そこまでの移動回数は必ずy/2となる(-y方向に移動できないので)．
なのでたどり着ける場合はy/2,たどりつけないなら-1と表示する．
たどり着けない条件は
- y<0 (-y方向に移動できないので)
- abs(x)*2>y (一回移動するたびにxは1,yは2移動するので)
- xが偶数の時
- yが4で割り切れない場合
- xが奇数の時
- yを4で割った余りが2以外の場合
回答コード
#include<iostream>
using namespace std;
int main(){
int x,y;
cin >> x >> y;
if(y<0)cout << -1 << endl;
else if(abs(x)*2>y)cout << -1 << endl;
else if(x%2){
if(y%4==2)cout << y/2 << endl;
else cout << -1 << endl;
}else{
if(y%4)cout << -1 << endl;
else cout << y/2 << endl;
}
}
B - Shift only(AtCoder Beginner Contest 081)
問題文
黒板にN個の正の整数 $A_1$,...,$A_N$が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
黒板に書かれている整数すべてを，2で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．
制約
- $1≤N≤200$
- $1≤Ai≤10^9$
解説
全ての数値を何回２で割れるのかを確認して，その結果が最小のものが解になります
回答コード
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
int ans = 9999999;
for(int i=0;i<n;i++){
int a;
cin >> a;
int cnt=0;
while(a%2==0){
cnt++;
a/=2;
}
ans = min(ans,cnt);
}
cout << ans << endl;
}
A - 値札
問題文
すぬけ君は、店を開こうとしています。N個の商品を販売する予定です。 i番目の商品は、$p_i$円で販売されます。
すぬけ君は、それぞれの価格の末尾についた 0 をたくさん書くのが大変に感じたので、N個全ての商品の値札の末尾に連続する0を全ての商品について同じ個数だけ取り除き、会計の時にその分の0を補完することにしました。
商品の値札1枚あたり、0を最大何個取り除けるかを求めてください。
制約
- $1≤N≤100$
- $1≤p_i≤10^9$
- $p_i$は整数
解説
全ての数値を何回10で割れるのかを確認して，その結果が最小のものが解になります
回答コード
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
int ans = 99999999;
for(int i=0;i<n;i++){
int a;
cin >> a;
int cnt=0;
while(a%10==0){
cnt++;
a/=10;
}
ans = min(ans,cnt);
}
cout << ans << endl;
}
感想
あと，大雨警報が発令した中の開催だったので参加者は少ないと思っていましたが１年生は8人(半分以上)も来てくれました．僕はすごい嬉しいです！
あと問題文が面白い問題の反応が良かったので安心しました．
結果
部長が威厳を見せて一位！
一年生にB問題を３問も自力で通した強者もいました！
今後のスケジュール
部外の人も是非ご参加ください！
- 9/3 13:30~16:30 PCK対策1st(リベンジ) by コン研
- 9/5 13:30~16:30 PCK対策2nd by コン研
- 9/12 13:30~16:30 PCK対策3rd by コン研
- 9/14 13:30~16:30 PCKの準備体操 by コン研
- 8/30 15:00 ~ 10/11 19:00 ラボバチャ