部内バチャ

パソコン甲子園プログラミング部門の対策として8/29に部内でAtCoderVirtualContestを開催しました．
その時の問題の解説です．

A - Round Up the Mean (AtCoder Beginner Contest 082)

リンク: https://atcoder.jp/contests/abc082/tasks/abc082_a

問題文

2つの正整数a,bが与えられます。a,bの平均値をxとします。xの小数点以下を切り上げて得られる整数を出力してください。

制約

a,bは整数である。
1≤a,b≤100

解説

a,bの平均を出力する必要があるので出力するxの値はaとbの和を2で割った値になります．
ですが，この問題で重要なところは 切り上げって得られる整数 という一文です．
整数型での除算はデフォルトでは切り捨てになっています．

これを切り上げにするた為の方法を普通に考えれば以下の様なif文を実装することになるでしょう

if((a+b)%2)cout << (a+b)/2+1 << endl;
else (a+b)/2 << endl;

このやり方，確かにこのやり方でも問題ないですがスマートなやり方とは言えません．
これをスマートにすると以下の様になります．

cout << (a+b+1)/2 << endl;

これは整数型の除算に置いて，例えばxをyで割った結果の切り上げを行いたいという場合

cout << (x+y-1)/y << endl;

というすることで割り切れる場合は y-1 の箇所が切り捨てられるので x/y が帰ってきて，
割り切れない場合は y-1 に必ず 1 以上 y 以下の数値が足されるので x/y+1 という風になります．

今回の問題ではxに当たるものはa+bでyに当たるものは2です．
それを踏まえた上でこのやり方を見るとわかりやすいでしょう．

cout << (a+b+1)/2 << endl;

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  cout << (a+b+1)/2 << endl;
}

A - Placing Marbles (AtCoder Beginner Contest 081)

リンク: https://atcoder.jp/contests/abc081/tasks/abc081_a

問題文

すぬけ君は1,2,3の番号がついた3つのマスからなるマス目を持っています。各マスには 0 か 1 が書かれており、マスiには $s_i$が書かれています。
すぬけ君は 1 が書かれたマスにビー玉を置きます。ビー玉が置かれるマスがいくつあるか求めてください。

制約

$s_1,s_2,s_3$は 1 あるいは 0

解説

これにはいくつか解き方があるのでその解説をしていきます．

char型

まず一つ目の解き方はchar型を使うやり方です．

#include <bits/stdc++.h>
using namespace std;

int main() {
  char a,b,c;
  cin >> a >> b >> c;
  int ans=0;
  if(a=='1')ans++;
  if(b=='1')ans++;
  if(c=='1')ans++;
  cout << ans << endl;
}

このやり方ではchar型の複数個連続して並んでいたら１文字ずつ取り出すという性質を利用します．
この場合は101であれば a='1', b='0', c='1' が格納されます．
これを一つずつifぶんで確認していくというものです．おそらくこの問題の想定解はこれだと思います．

string型

次はstring型を使ったやり方です．

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  int ans=0;
  for(int i=0;i<3;i++)if(s.at(i)=='1')ans++;
  cout << ans << endl;
}

多分これが一番短いやり方です．
やってることは先ほどと同じで入力された数値を文字列と見なして，前から'1'と一致するものの個数をカウントしているだけです．

int型

最後はint型を使ったやり方です．

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int ans=0;
  while(n){
    if(n%10)ans++;
    n/=10;
  }
  cout << ans << endl;
}

はっきり言うとこのやり方は変態です．上記の二つに比べると直感的とは言い難いです．
やってる処理の内容ですがwhile文の中で

nの１０で割った余りを参照→nを10で割る

と言う挙動を繰り返すことで下の方からの各桁の値が参照可能です．
この時if文はその参照されたn%10が0でなければ中身が実行されるので実質的な1個数ををカウントすると言う挙動になっています．

また，while文はnが0，すなわちこれ以上これ以上の上位の桁が全て0の場合になれば終了します．

回答コード

既に記載したのでここでは省略．

A - Something on It (AtCoder Beginner Contest 095)

リンク: https://atcoder.jp/contests/abc095/tasks/abc095_a

問題文

ラーメン店「高橋屋」のラーメンの値段は1杯700円ですが、トッピング（味玉、チャーシュー、ねぎ）を乗せた場合は1種類につき100円が加算されます。
ある客がラーメンを一杯注文し、店員にトッピングの希望を伝えました。店員は注文の内容をメモ帳に文字列Sとして記録しました。
Sの長さは3文字で、Sの1文字目が o のとき客のラーメンに味玉を乗せることを、x のとき味玉を乗せないことを表します。同様に、Sの2文字目、3文字目はそれぞれチャーシュー、ねぎの有無を表します。
Sが入力されると、対応するラーメンの値段を出力するプログラムを書いてください。

制約

Sは長さ3の文字列である。
Sの各文字は 'o' または 'x' である。

解説

先ほどと同じ解放ですね．解説なくてもいけるでしょう．
ただ，oとxが入力されるのでint型では扱えません．

回答コード

char型

#include <bits/stdc++.h>
using namespace std;

int main() {
  char a,b,c;
  cin >> a >> b >> c;
  int ans=700;
  if(a=='o')ans+=100;
  if(b=='o')ans+=100;
  if(c=='o')ans+=100;
  cout << ans << endl;
}

string型

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  int ans=700;
  for(int i=0;i<3;i++)if(s.at(i)=='1')ans+=100;
  cout << ans << endl;
}

A - Already 2018

リンク: https://atcoder.jp/contests/abc085/tasks/abc085_a

問題文

2018年1月某日、高木さんは書類を書いています。書類には、その日の日付を yyyy/mm/dd という形式で書き込む欄があります。例えば、2018年1月23日は 2018/01/23 となります。
書類を書き終えたあと、高木さんは日付欄の先頭に誤って 2017 と書いてしまっていたことに気がつきました。高木さんが日付欄に書いた文字列Sを入力すると、Sの先頭の4文字を 2018 に修正して出力するプログラムを書いてください。

制約

Sは長さ10の文字列である。
Sの先頭の8文字は 2017/01/ である。
Sの末尾の2文字は数字であり、1以上31以下の整数を表す。

解説

変更するのは2017の7と言う部分を８に変更するだけなので，なので配列のインデックスが3となる箇所を8に修正すれば解決します．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;
  s.at(3) = '8';
  cout << s << endl;
}

A - CODEFESTIVAL 2016 (CODE FESTIVAL 2016 qual A)

リンク: https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_a

問題文

このコンテストの名前は CODE FESTIVAL です。しかし、高橋君はいつも CODEFESTIVAL と書き間違えてしまいます。つまり、CODE と FESTIVAL の間の半角スペースを省いてしまいます。そこで高橋君は、省いてしまった半角スペースを復元するプログラムを作ることにしました。長さ12の文字列sが与えられます。 sの前半4文字と後半8文字の間に半角スペースを1つ挿入し、出力してください。

制約

sは長さ12である。
sは英大文字のみからなる。

解説

問題通りです．4文字目と5文字目の間に改行を挿入しましょう．
String型に空白を入れると言う方法もないわけではないですが,スマートな解法ではないので割愛させていただきます．
今回のケースではfor文で１文字ずつ表示してs.at(3)とs.at('4')の間に空白をcoutで表示するのが最も簡単です．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    cout << s.at(i);
    if(i==3)cout << " ";
  }
  cout << endl;
}

A - 動画検索 (第3回ドワンゴからの挑戦状予選)

リンク: https://atcoder.jp/contests/dwacon2017-prelims/tasks/dwango2017qual_a

問題文

ドワンゴ社の運営する動画サイトにはn本の動画があります。ニワンゴくんが検索してみたところ、そのうちタイトルに「ドワンゴ」を含む動画がa本あり、「ニコニコ」を含む動画がb本あることがわかりました。
ニワンゴくんは「ドワンゴ」「ニコニコ」の両方をタイトルに含む動画が何本あるのか気になっています。そのような動画は最低でも何本あると言えるでしょうか。

制約

1≦n≦14,000,000
1≦a≦n,1≦b≦n

解説

この問題のポイントは 最低何本あるか と言う一文です．
これによりa+bがnより小さい場合は２つの条件が重複がしなくてもa,bがそれぞれ規定数分存在しうるので 0 ．
逆にそれより多い場合は最低でもa+bからnを引いた値が最低でも存在しうる二つの条件を満たす動画の本数になります．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,a,b;
  cin >> n >> a >> b;
  cout << max(0,a+b-n) << endl;
}

B - i18n (AtCoder Beginner Contest 069)

リンク: https://atcoder.jp/contests/abc069/tasks/abc069_b

問題文

"internationalization" という英単語は、i18n と略されることがあります。これは、先頭文字iと末尾文字nの間に18文字が挟まっていることに由来します。長さ3以上の英小文字のみからなる文字列sが与えられます。同様の規則によってsを略してください。

制約

3≤|s|≤100(ただし、|s|はsの長さを表す。)
sは英小文字のみからなる。

解説

この問題は一見複雑に見えますが非常にシンプルです．
表示したい内容は最初の文字と前後以外の文字数,最後の文字のみです．
なので最初の文字は s.at(0)
前後以外の文字数は s.size()-2
そして，最後の文字は s.at(s.size()-1)
で取得可能です．これを順番に表示すれば解くことが可能です．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;
  cout << s.at(0) << s.size()-2 << s.at(s.size()-1) << endl;
}

B - Some Sums (AtCoder Beginner Contest 083)

リンク: https://atcoder.jp/contests/abc083/tasks/abc083_b

問題文

1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めてください。

制約

$1≤N≤10^4$
$1≤A≤B≤36$
入力はすべて整数である

解説

みんなこの問題に苦戦していたみたいだけどなかなか難問だったみたいです．
やはり各桁の和と言う項目がきつかったのですかね?
それでは解法としてはfor文で0~Nまで各桁の和が条件を満たすのか確認するためにfor文で全探索を行います．
自明ですがそのfor文は以下の様になります．

for(int i=0;i<=n;i++){

この中にそのiの各桁の和がわかれば良いので以下の様な処理を書きます

for(int i=0; i<n; i++){
  int c=i, wa=0;
  while(c){
   wa+=c%10;
   c/=10;
  }
  if(a<=wa && wa <= b)ans+=i;
}

cはiのコピーです．ここでコピーを生成する理由はwhile文内で値を操作するのでiをそのまま利用するとループ回数に影響が出るのを防ぐためです．
waは各桁の和を格納する変数です．これに2問目のint型の解法でやった様に

nの１０で割った余りを参照→nを10で割る

を繰り返すことで各桁の値を取得し加算していきます．
この総和が条件を満たしていくのであれば基準となったiを最終的な答えに加算すれば解決可能です．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,a,b;
  cin >> n >> a >> b;

  int ans = 0;
  for(int i=0; i<n; i++){
    int c=i, wa=0;
    while(c){
      wa+=c%10;
      c/=10;
    }
    if(a<=wa && wa<=b)ans+=i;
  }

  cout << ans << endl;
}

B - Snake Toy (AtCoder Beginner Contest 067)

リンク: https://atcoder.jp/contests/abc067/tasks/abc067_b

問題文

すぬけくんは N本の棒を持っています。 i番目の棒の長さは$l_i$です。すぬけくんはK本の棒を選んでつなげて、ヘビのおもちゃを作りたいです。ヘビのおもちゃの長さは選んだ棒たちの長さの総和で表されます。ヘビのおもちゃの長さとしてありうる長さのうち、最大値を求めなさい。

制約

$1≤K≤N≤50$
$1≤l_i≤50$
$l_i$は整数

解説

この問題はN個の棒の中から長さが大きい順にK個選びその総和を求めれば解くことが可能です．
やり方はsort関数で昇順に並び替えた後にreverce関数で配列を反転させて降順に切り替えて,最初のK個を答えに加算しくと言う方法が最適でしょう．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> vec(n);
  for(int i=0; i<n; i++)cin >> vec.at(i);

  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());

  int ans = 0;
  for(int i=0; i<k; i++)ans += vec.at(i);
  cout << ans << endl;
}

B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)　 (AtCoder Beginner Contest 042)

リンク: https://atcoder.jp/contests/abc042/tasks/abc042_b

問題文

いろはちゃんは長さLの文字列をN個持っており、それぞれ $S_1,S_2,...,S_N$ です。
それらの文字列を好きな順番で全て結合してできる文字列のうち、もっとも辞書順で小さいものを求めてください。
なお、ある文字列 $s=s_1s_2s_3...s_n$ と $t=t_1t_2t_3...t_m$ について、以下のどちらかを満たすとき、辞書順比較で $s<t$ であるといいます。

ある整数 $i(1≦i≦min(n,m))$ に関して、 $1≦j<i$ を満たす任意の整数jにおいて $s_j=t_j$ が成立し、かつ $s_i<t_i$ が成立する。
任意の整数 $i(1≦i≦min(n,m))$ に関して $s_i=t_i$ が成立し、かつ $n<m$ が成立する。

制約

1≦N,L≦100
全ての i(1≦i≦N) に対し、$S_i$ の長さは L に等しい。
各 i について, $S_i$ は全て半角英小文字のみから成る文字列である。

解説

このN個の数列を辞書順に並べた文字列が最終的な解です．
弊部では余り知られちぇいなかった様ですがstring型のvectorをsort関数でsortすると辞書順に並び替えられます．
なのでsortしてから前から表示していくと言う処理だけでこの問題を解くことは可能です．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,l;
  cin >> n >> l;
  vector<string> vec(n);
  for(int i=0; i<n; i++)cin >> vec.at(i);
  sort(vec.begin(),vec.end());

  for(int i=0; i<n; i++)cout << vec.at(i);
  cout << endl;
}

B - Kagami Mochi (AtCoder Beginner Contest 085)

リンク: https://atcoder.jp/contests/abc085/tasks/abc085_b

問題文

X 段重ねの鏡餅 (X≥1)とは、X枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は $d_i$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

$1≤N≤100$
$1≤d_i≤100$
入力値はすべて整数である。

解説

結局，この問題で求めたい内容は連続して同じ大きさの餅は存在できないと言う条件より数字の個数になります．
それを求める方法は2通りあります．

ソートする

数字はソートすると同じ大きさの値は必ず隣接します．
これを利用して隣接する値通しを比較して数値の種類を求めます．

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  for(int i=0; i<n; i++)cin >> vec.at(i);

  sort(vec.begin(),vec.end());
  int ans = 1;
  for(int i=0; i<n-1; i++)if(vec.at(i)!=vec.at(i+1))ans++;
  cout << ans << endl;
}

バケット法

こちらは$d_i$の範囲が狭いことを利用してそれぞれの変数が一度でも入力されたかをbool型の配列に記録すると言うプログラムです．

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<bool> d(101);
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    d.at(a)=true;
  }
  
  int ans = 0;
  for(int i=0;i<101;i++)if(d.at(i))ans++;
  cout << ans << endl;
}

回答コード

既に解説に記載したので省略

B - すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit) (AtCoder Beginner Contest 047)

リンク: https://atcoder.jp/contests/abc047/tasks/abc047_b

問題文

xy平面上に、左下の座標が (0,0)、右上の座標が (W,H) で、各辺が x 軸か y 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。すぬけ君はこの長方形の中に N 個の点を打ちました。i 個目 (1≦i≦N) 点の座標は $(x_i,y_i)$ でした。
また、すぬけ君は長さ N の数列 a を決めて、各 1≦i≦N に対し、

$a_i=1$ のときは長方形の $x<x_i$ をみたす領域
$a_i=2$ のときは長方形の $x>x_i$ をみたす領域
$a_i=3$ のときは長方形の $y<y_i$ をみたす領域
$a_i=4$ のときは長方形の $y>y_i$ をみたす領域

を黒く塗りました。
塗りつぶしが終わったあとの長方形内での白い部分の面積を求めてください。

制約

$1≦W,H≦100$
$1≦N≦100$
$0≦x_i≦W (1≦i≦N)$
$0≦y_i≦H (1≦i≦N)$
$W, H, x_i, y_i$ は整数である
$a_i (1≦i≦N)$ は 1,2,3,4 のいずれかである

解説

この問題は塗られていない領域を新たな長方形として考えると以下の様に考えることが可能です．

$a_i=1$ のときは長方形の左側面のx座標を更新
$a_i=2$ のときは長方形の右側面のx座標を更新
$a_i=3$ のときは長方形の下面のy座標を更新
$a_i=4$ のときは長方形の上面のy座標を更新

ここまでわかればあとはこれを実行するのみです．
ただ，注意点として 右側面のx座標-左側面のx座標や 上面のy座標-下面のy座標 が負の数になる場合は長方形の面積は0になります．

回答コード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int w,h,n;
  cin >> w>> h >> n;
  int left=0,right=w,bottom=0,top=h;
  for(int i=0; i<n; i++){
    int x,y,a;
    cin >> x >> y >> a;
    if(a==1)left=max(left,x);
    if(a==2)right=min(right,x);
    if(a==3)bottom=max(bottom,y);
    if(a==4)top=min(top,y);
  }
  int ans = 0;
  cout << max(0,right-left)*max(0,top-bottom) << endl;
}

感想

リンク: https://not-522.appspot.com/contest/5697386359816192
今回は僕も参加者側で参加しました．
事前に問題は目は通していたので他参加者よりか有利な状況なので一位以外許されないなぁと思っていました．
結果，1位は死守できましたが２位とは36秒差...．
恐ろしい...．

弊部の一年生もB問題をACできる人が増えていき順調に成長していってるなぁなどと思うなどしました．

今後の予定

こちらも部外の人の参加大歓迎なので皆さん時間が合えばご参加ください！

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 コン研