夏休み最後の模擬戦 解説

A - 山手線

問題文

A君は山手線に乗って目的地にたどり着きたい．
A君は電車に乗ってから a 分起きて b 分寝ることを繰り返す． 目的地までは乗車後 c 分であり，このとき起きていれば下車できるが，逆に寝ている途中であれば乗り過ごしてしまう．また，A君は乗り過ごしてもずっと同じ電車に乗り続け，電車は山手線を一周するのに60分かかる．したがって，A君は目的地に 60t+c ( t は非負整数) 分後に着くことになる．
何分後にA君は目的地に到着できるか． 到着不可能なときは-1を出力せよ．
ただし，目的地に到着した時が寝ている時間と起きている時間の境目だった場合は降りることができるものとする．

制約

• 0<a,b,c<60

解説

色々賢い方法を考えるかもしれませんが、この問題にそのような賢い解法なく(多分)、実際にシミュレーションを行ってみるのが最適な解法でしょう。ただ、問題は何回シミュレーションを行うのかという問題ですが、この問題では１時間は60分なので少なくてとも60回ループを回せば全パターンを確認することが可能です。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  for(int i=0; i<60; i++) {
    if((c+i*60)%(a+b)<=a) {
      cout << c+i*60 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

A - 時差

問題文

PAKEN 君は地理の授業で「時差」というものを学んだ.
地球上だと経度が 15 度違うごとに 1 時間の時差がある.
東経か西経かを表す文字 $C_1,C_2$ (西経ならば W, 東経ならば E) と二地点の経度
A,B (それぞれ $C_1,C_2$ に対応する) が二行にわたって与えられるので, その間の時差を求めなさい.
ただし, 日付変更線は東経 180 度にあるものとし, 時差は日付変更線をまたがないように差を取ったものだとする.

制約

• C_1,C_2 は W か E のどちらかである.
• A,B は 0 以上 180 未満の 15 の倍数である.

解説

この条件分岐は非常に単純です。
A == B なら $C_1$, $C_2$ の差の絶対値を, A!=B なら $C_1,C_2$ の和を表示するだけです。

#include <bits/stdc++.h>
using namespace std;
int main() {
   string s1,s2;
   int a,b;
   cin >> s1 >> a >> s2 >> b;
   if(s1==s2)cout << abs(a-b)/15 << endl;
   else cout << (a+b)/15 << endl;
}

B - チーム作り

問題文

CODE FESTIVAL 2014 には 200 人の参加者がおり、1 から 20 までの計 20 チームに分かれてリレー（物理）を行います。
参加者は本戦の順位によって、以下のような手順でチームが決まります。

• 1 ~ 20 位までの人は、順に 1 ~ 20 までのチームに入る
• 21 ~ 40 位までの人は、逆順に 1 ~ 20 までのチームに入る
• 41 ~ 60 位までの人は、順に1 ~ 20 までのチームに入る
• ...

さて、ある参加者の本戦での順位が与えられるので、その参加者がどのチームになるかを求めてください。

制約

• 1 行目には、ある参加者の本戦での順位を表す整数 n (1≤n≤200) が与えられる。

解説

これはそれぞれのパターンで条件分岐させましょう.
n%20の値が20以上なら 41-n を出力、それ以外なら n をそのまま出力。
ただ、n==0 ならそのまま出力する必要があります。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  n %= 40;
  if(n==0)cout << 1 << endl;
  else if(n>20)cout << 41-n << endl;
  else cout << n << endl;
}

B - もう1年遊べるドン？

問題文

amylase 伯爵さんは今年卒業を控えた大学生です。
今度行われる期末試験において s 点以上の点数を得ることができれば無事に卒業できますが、そうでなければ留年してしまいます。
さて、来たる期末試験当日、amylase 伯爵さんは a 点を獲得しました。数値の比較が苦手な amylase 伯爵さんに代わって、彼が卒業できるかどうか判定してください。

制約

• 1 行目には、amylase 伯爵さんの試験の点数を表す整数 a (0≤a≤100) と、卒業のために必要な点数を表す整数 s (0≤s≤100) が与えられる。

解説

a,bの大小を比較するだけです。簡単でしょう。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b;
  cin >> a >> b;
  if(a<b)cout << "Enjoy another semester..." << endl;
  else cout << "Congratulations!" << endl;
}

B - 未提出者は誰だ

問題

JOI 大学の M 教授はプログラミングの授業を担当している． クラスには 30 人の受講生がいて各受講生には 1 番から 30 番まで の出席番号がふられている． この授業の課題を 28 人の学生が提出した ． 提出した 28 人の出席番号から提出していない 2 人の出 席番号を求めるプログラムを作成せよ．

制約

入力は 28 行あり， 各行には提出者の出席番号（ 1 以上 30 以下）が 1 つずつ書かれている． 入力される出席番号 に重複はないが， どのような順に入力されるかはわからない．

解説

とりあえずbool型の配列を用意してそれに提出されたか否かを記録します。
そして、for文で1~30までの記録をそれぞれ確認していき提出されていないものだけを表示するようにしましょう。

#include <bits/stdc++.h>
using namespace std;
int main() {
  vector<bool> v(31,true);
  for(int i=0;i<28;i++){
    int a;
    cin >> a;
    v.at(a) =  false;
  }
  for(int i=1;i<=30;i++)if(v.at(i))cout << i << endl;
}

C - amylasemania IIDX

問題文

kawatea さんは空から降ってくる複数の amylase 伯爵さんを順番に一度ずつ、音楽に合わせて叩くゲームにはまっています。
このゲームにはコンボというシステムが存在し、amylase 伯爵さんを音楽に合わせて叩くことに成功するとコンボの数が 1 増え、叩くことに失敗してしまうとコンボの数が 0 に戻ってしまいます。
合計で n 個の amylase 伯爵さんを叩き終わったとき、最大のコンボの数が m となりました。
このときに考えられる最小の失敗の回数を求めるプログラムを作成してください。

制約

• 1 行目には、amylase 伯爵さんの数を表す整数 n (1≤n≤1,000,000,000) と、最大のコンボの数を表す整数 m (1≤m≤n) が与えられる。

解説

基本的には全てのコンボ数が最大コンボ数であればそれが最小の失敗回数をとる時の結果になります。
そして、 最大コンボ数+1回の失敗 を1セットとして繰り返すので a/(b+1) を出力すれば良いということがわかります。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b;
  cin >> a >> b;
  cout << a/(b+1) << endl;
}

B - Contests

問題文

あなたはプログラミングコンテストを開催するため問題を N 問作成しました。 このうち i 問目をコンテストに出題する場合、配点は $P_i$ 点となります。
これらの問題を使って、以下の条件を満たすコンテストをできるだけ多く開催したいと思います。 異なるコンテストの間で問題の重複があってはいけません。 最大で何回のコンテストを開催できますか。
問題が 3 問出題され、1 問目の配点は A 点以下、2 問目の配点は A+1 点以上 B 点以下、3 問目の配点は B+1 点以上である。

制約

• 3≤N≤100
• 1≤P_i≤20 (1≤i≤N)
• 1≤A<B<20 入力値はすべて整数である。

解説

この問題は1問目,2問目,3問目に入る問題は完璧に分離可能なので、それぞれに当てはまる問題の個数をカウントしてその３つの中で最小の値を出力すれば解くことが可能です。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,a,b;
  cin >> n >> a >> b;
  int cnt1=0,cnt2=0,cnt3=0;
  for(int i=0;i<n;i++){
    int m;
    cin >> m;
    if(m<=a)cnt1++;
    else if(a<m && m<=b)cnt2++;
    else if(b<m)cnt3++;
  }
  cout << min(cnt1,min(cnt2,cnt3)) << endl;
}

B - Picture Frame

問題文

縦 H ピクセル、横 W ピクセルの画像があります。 各ピクセルは英小文字で表されます。 上から i 番目、左から j 番目のピクセルは $a_{ij}$ です。この画像の周囲 1 ピクセルを '#' で囲んだものを出力してください。

制約

• 1≤H,W≤100
• $a_{ij} は英小文字である。

解説

まずは W+2 回だけ '#' を表示して、
その次に入力された各文字列を '#' で囲んで出力します。
そして、最後にまた W+2 回 '#' を出力すれば完成です。

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<string> s(H);
  for(int i=0;i<H;i++)cin >> s.at(i);

  for(int i=0;i<W+2;i++)cout << "#";
  cout << endl;

  for(int i=0;i<H;i++)cout << "#" << s.at(i) << "#"<< endl;

  for(int i=0;i<W+2;i++)cout << "#";
  cout << endl;

}

B - Tap Dance

問題文

高橋君はタップダンスをすることにしました。タップダンスの動きは文字列 S で表され、S の各文字は L, R, U, D のいずれかです。各文字は足を置く位置を表しており、1 文字目から順番に踏んでいきます。
S が以下の 2 条件を満たすとき、またその時に限り、S を「踏みやすい」文字列といいます。

• 奇数文字目がすべて R, U, D のいずれか。
• 偶数文字目がすべて L, U, D のいずれか。

S が「踏みやすい」文字列なら Yes を、そうでなければ No を出力してください。

制約

• S は長さ 1 以上 100 以下の文字列
• S の各文字は L, R, U, D のいずれか

解説

この問題は踏みやすい条件よりも踏みにくい条件で書いた方がスマートです。
踏みにくい条件は 奇数の時に L 、偶数の時に R を踏む必要があればその時点で No ということがわかります。
ちなみにですが条件式の計算の優先順位は && は先で || が後です。
掛け算と足し算の関係に似ていますね。

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

int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(i%2==1 && s.at(i)=='R' || i%2==0 && s.at(i)=='L'){
      cout << "No" << endl;
      return 0; 
    }
  }
  cout << "Yes" << endl;
}

B - Uneven Numbers

問題文

整数 N が与えられます。N 以下の正の整数のうち、(先頭に 0 をつけずに十進法で表記したときの) 桁数が奇数であるようなものの個数を求めてください。

制約

• $1≤N≤10^5$

解説

Nの個数も対して多くないので直接数えてしまいましょう。
桁数の計測はいつものwhile文を使用した物を使用しています。今回は各桁の合計ではないのでdigitという桁数を格納する変数をインクリメントしてるだけです。

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

int main(){
  int n;
  cin >> n;
  int cnt=0;
  for(int i=1;i<=n;i++){
    int cp=i,digit=0;
    while(cp){
      digit++;
      cp /= 10;
    }
    if(digit%2)cnt++;
  }
  cout << cnt << endl;
}

C - 755

問題文

整数 N が与えられます。1 以上 N 以下の整数のうち、七五三数 は何個あるでしょうか？
ここで、七五三数とは以下の条件を満たす正の整数です。

• 十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1 回以上現れ、これら以外の数字は現れない。

制約

• $1≤N<10^9$
• N は整数である。

解説

時間切れになるパターン

この問題で時間切れになるパターンとして 1~N まで全探索するパターンがあげられます．
Nが小さなケースならこの方法で問題ないのですが計算量が $N=10^9$ の時にこのパターンだと 計算量が約 $10^{10}$ 程度になってしまいます．この問題の時間制約にひっからないように実装するには 計算量を $10^7$ 以下にする必要があるので全探索だと不可能です．

#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n;
  cin >> n;

  int ans=0;

  // 1~Nまで確認
  for(long long i=1;i<=n;i++){

    //3,5,7それぞれが出たかどうかを記録するフラグ
    bool isThree=false;
    bool isFive=false;
    bool isSeven=false;

    //3,5,7以外が出たのかを記録するフラグ
    bool isOther=false;

    //現状の数値のコピー
    long long cp=i;

    //下から一桁ずつ確認していく
    while(cp){
      if(cp%10 == 3) isThree=true; //3が存在する
      else if(cp%10 == 5) isFive=true; //5が存在する
      else if(cp%10 == 7) isSeven=true;  //7が存在する
      else isOther=true; //3,5,7 以外が存在する
      cp /= 10;
    }

    //3,5,7がいずれも存在していたならansを増やす
    if(isThree && isFive && isSeven && !isOther) ans++;
  }

  cout  << ans << endl;
}

再帰関数を使用するパターン

この問題の予想される想定解は再帰関数を使用するというものです．
解説より先に全体のソースコードを確認していきましょう．

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

// 引数の役割:
// isThree -> 3があるかないかのフラグ,
// isFive -> 5があるかないかのフラグ,
// isSevem -> ７があるかないかのフラグ,
// digit -> 現在の桁数,
// state -> 現在の値,
// limit -> 最大数,
int dfs(bool isThree,bool isFive, bool isSeven,int digit,long long state,long long limit){

    if(limit < state) return 0;

    int result=0;
    result += dfs(true, isFive, isSeven, digit+1, state+3*pow(10,digit),limit);
    result += dfs(isThree, true, isSeven, digit+1, state+5*pow(10,digit),limit);
    result += dfs(isThree, isFive, true, digit+1, state+7*pow(10,digit),limit);

    if(isThree && isFive && isSeven) result++;

    return result;
}

int main() {
  long long n;
  cin >> n;
  cout << dfs(false,false,false,0,0,n) << endl;
}

この問題は再帰関数を使って深さ優先探索(以下,dfs)を呼ばれる探索を行なっています．

dfsの詳しい説明は以下のサイトがわかりやすいのでそこで確認しましょう．
https://qiita.com/shki/items/cc9806564a2690e90fdb

それでは早速ですが今回実装した再帰関数の説明を行います．

大まか流れ

このプログラムは大まかにいうと0からスタートして，
それぞれの結果にその桁よりも一つ多い位置に 3 or 5 or 7 を足すという処理を繰り返します．
グラフで表現するとこんな感じです．

このような探索はSTLのコンテナを使えば再帰関数を使用せずに実装可能なのですが皆さんにはSTLコンテナを既に取得済みな人はほとんどいないと思うので今回は再帰関数をしようした実装を行います．

引数部

// 引数の役割:
// isThree -> 3があるかないかのフラグ,
// isFive -> 5があるかないかのフラグ,
// isSevem -> ７があるかないかのフラグ,
// digit -> 現在の桁数,
// state -> 現在の値,
// limit -> 最大数,
int dfs(bool isThree,bool isFive, bool isSeven,int digit,long long state,long long limit){

これはコメントアウトに定義した通りですので特に説明はいらないでしょう．
わからなかったら上級生にきてみてください．きっと教えててくれるはずです．

最初のreturn

上記のグラフの数値がstateに当たります．
limitはnの値ですね．
if文の条件を満たす時はそもそも探索範囲外なので探索を続ける必要はないです．

    if(limit < state) return 0;

再帰部

    int result=0;
    result += dfs(true, isFive, isSeven, digit+1, state+3*pow(10,digit),limit);
    result += dfs(isThree, true, isSeven, digit+1, state+5*pow(10,digit),limit);
    result += dfs(isThree, isFive, true, digit+1, state+7*pow(10,digit),limit);

    if(isThree && isFive && isSeven) result++;

    return result;

resultで返す内容はその時の state 3であれば 33,33,53,73,333,533,733,353,... というような上のグラフに置いてそこから伸びる子ノードの中で条件を満たすものの個数をカウントしていきます．

そのやり方ですが，
例えば3を追加する処理では3のフラグをtrueにしてその他のフラグは現状のまま渡します．
そして，桁は一つ追加して，stateは現状の桁より一つ大きい位置に3を追加します．

    result += dfs(true, isFive, isSeven, digit+1, state+3*pow(10,digit),limit);

この基本的なやり方はは5,7のパターンでも同様なのがわかるでしょう．

    result += dfs(isThree, true, isSeven, digit+1, state+5*pow(10,digit),limit);
    result += dfs(isThree, isFive, true, digit+1, state+7*pow(10,digit),limit);

そして最後に現状の値が条件を満たすかを確認しないことには永遠に0なので
3,5,7が全て存在する時に result に１を加算します．

    if(isThree && isFive && isSeven) result++;

返却部

ただ，resultを返すだけだよ．
難しいことは何もしないよ．

    return result;

main関数

上記のような再帰関数を定義すればstateを0から開始した場合に上記の木構造内のN以下の条件を満たすものの個数を呼び出せるのでmain関数では以下のように定義すれば終了です．

int main() {
  long long n;
  cin >> n;
  cout << dfs(false,false,false,0,0,n) << endl;
}

高速なの???

結論から言うと元々の全探索と比較すると超高速です．
今までは全パターン試していたのに対してこちらは3,5,7を上に積み重ねていくパターンしか検証していません．

なので計算量は 全探索が $O(N)$ だったのに対して $O(3^{log{N}})$ になります．
こう計算量で記載されても分かりにくいと思うので実際にここに $N=10^9$ を代入して考えると

全探索: O(10^9) = O(1000000000)

再帰関数: O(3^{log{10^9}}) = O(3^9) = O(19683)

と言うふうな感じで全然速度が違うのがわかると思います．

C - Pyramid

問題文

古代すぬけ国では, AtCoder 社長「高橋君」の権威を高めるために, ピラミッドが建てられていた.
ピラミッドには 中心座標 $(C_X,C_Y)$ と 高さ H が定まっており, 座標 $(X,Y)$ の高度は $max(H−|X−C_X|−|Y−C_Y|,0)$ であった.

探検家の青木君は, このピラミッドの中心座標と高さを求めるために調査を行った.
その結果, 次のような情報が得られた.
- $C_X,C_Y$ は 0 以上 100 以下の整数で, H は 1 以上の整数であった.
- 上記と別に N 個の情報が得られた. そのうち i 個目の情報は, 「座標 $(x_i,yi_)$ の高度は $h_i$ である」

この情報は, ピラミッドの中心座標と高さを特定するのに十分であった. 情報を手掛かりに, これらの値を求めなさい.

制約

• N は1 以上 100 以下の整数
• $x_i, y_i$ は 0 以上 100 以下の整数
• $h_i$ は 0 以上 $10^9$ 以下の整数
• N 個の座標 $(x_1,y_1),(x_2,y_2),(x_3,y_3), ..,(x_N,y_N)$ はすべて異なるピラミッドの中心座標と高さをちょうど 1 つに特定することができる

解説

これは色々な解法を考えられますが Nが最大でも100と言うふうな条件より中心座標のパターンが最大でも 10,000 通りしかないのがわかります．なのでそれらのパターンで条件を満たすのかを全探索すればOKです．

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

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

  for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){

            int ansH; //基準となる高さを格納する変数

            // 一番最初に1以上の数値を見つけた場合はそれで成り立つような高さを基準として設定
            for(int k=0;k<n;k++)if(h.at(k) > 0){
                ansH = h.at(k)+abs(i-x.at(k))+abs(j-y.at(k));
                break; //一つ目を見つけたら強制終了
            }

            bool fin=true;
            //基準の高さで全ての座標で辻褄が合うのか確認
            for(int k=0;k<n;k++){
                if(h.at(k) != max(ansH-abs(i-x.at(k))-abs(j-y.at(k)),0)){
                    fin = false;
                    break;
                }
            }

            //全ての場合は辻褄が合えばその結果を表示して終了
            if(fin){
                cout << i << " " << j << " " << ansH << endl;
                return 0;
            }
        }
    }
}

基本的にはコメントに記載している通りの考え方です．

まずは基準となる高さを固定してあげる為に条件に合うものを一つ取り出します．
この時の条件として０以上である必要があります．なぜなら0ならmax関数で弾かれてしまったものを参照してしまう可能性がある為，そうなると答えが一意に定まらない原因になってしまいます．
検索方法ですが当たられた式を中学校で習った移項を使って ansH(基準の高さ)= の形にしてあげましょう！

次はその固定してあげた高さで全てのデータをマッチするのかを確認します．
ここは問題文の計算式をそのまま変形せずに確認するだけです．一致しないのが一つでもあればその時点で中断して次の基準点を探しましょう．