部内バチャ解説 (PCK対策2nd by コン研)

部内バチャ

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

A - HEX (AtCoder Beginner Contest 078)

リンク: https://atcoder.jp/contests/abc078/tasks/abc078_a

問題文

プログラミングでは 16 進数がよく使われます。
16 進数では 0,1,...,9 の数字の他に A, B, C, D, E, F の 6 つのアルファベットを使い，それぞれ 10,11,12,13,14,15 を表します。
この問題では 2 つのアルファベット X,Y が与えられます。
X と Y はどちらも A, B, C, D, E, F のうちどれかです。
X と Y を 16 進数として見たとき，どちらのほうが大きいかを判定してください。

制約

• X,Y は A, B, C, D, E, F のうちどれかである。

解説

与えられる二つのアルファベットを文字列として受け取り辞書順で比較すれば終了です．

回答コード

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

int main() {
  string x,y;
  cin >> x >> y;
  if(x == y)cout << "=" << endl;
  else if(x < y)cout << "<" << endl;
  else cout << ">" << endl;
}

A - Still TBD (AtCoder Beginner Contest 119)

リンク: https://atcoder.jp/contests/abc119/tasks/abc119_a

問題文

文字列 S が入力されます。これは、西暦 2019 年の実在する日付を yyyy/mm/dd の形式で表したものです。(例えば、
2019 年 4 月 30 日は 2019/04/30 と表されます。)
S が表す日付が 2019 年 4 月 30 日またはそれ以前なら Heisei、そうでなければ TBD と出力するプログラムを書いてください。

制約

• S は西暦 2019 年の実在する日付を yyyy/mm/dd の形式で表す文字列である。

解説

入力された文字列と "2019/04/30" を辞書順で比較するだけです．

回答コード

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

int main() {
  string s;
  cin >> s;
  if(s<="2019/04/30")cout <<  "Heisei" << endl;
  else cout << "TBD" << endl;
}

A - WAsedAC (早稲田大学プログラミングコンテスト2019)

リンク: https://atcoder.jp/contests/wupc2019/tasks/wupc2019_a

問題文

WUPC 2019の開催を記念して、カトーくんは文字列 s をプレゼントとしてもらいました。
しかしながら、カトーくんは WA という文字列が嫌いなので、 WA という文字列がなくなるまで以下の行動をすることにしました。
文字列 s を先頭から見ていき、連続する2文字が WA である場合、これを AC という文字列に置換する。
1回の置換を行った場合、文字列の先頭から再び上記の行動を行い、置換が行われなかった場合、終了する。
カトーくんが行動を終了したときの文字列を答えよ。

制約

• $1≤|s|≤10^5$
• 入力される文字列は英大文字のみで構成される。

解説

単純に置換していくだけで問題内容に見えますがACに変更した影響でその前のWと置換したのAによりWAが生まれてしまいます．
これを防ぐために何回も見直してしまうと$10^5$という長い文字列なのでTLEが発生してしまいます．
なので愚直に確認していくだけではいけません．

ただ，よく文字列を見ると後ろから置換すれば新たにWA発生することはありません．
つまり，文字列を反転させてAWをCAに変換し,変換後にもう一度反転させて出力することで解くことが可能です．

回答コード

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

int main(){
  string s;
  cin >> s;
  reverse(s.begin(),s.end());
  for(int i=0;i<s.size()-1;i++){
    if(s.at(i)=='A' &&  s.at(i+1)=='W'){
      s.at(i)='C';
      s.at(i+1)='A';
    }
  }
  reverse(s.begin(),s.end());
  cout << s << endl;
}

A - ニコニコ文字列判定 (第4回 ドワンゴからの挑戦状 予選)

リンク: https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_a

問題文

dwango社員のニワンゴくんは長さ 4 の数字のみからなる文字列 s を見つけました。
s がニコニコ文字列(後述)ならば Yes を、そうでなければ No を出力してください。
ある数字 x,y が存在して、s が xyxy と表されるとき、 s はニコニコ文字列であると呼ばれます。例えば 2525 や 4141、9999 はニコニコ文字列ですが、2255 や 1221、3334 はニコニコ文字列ではありません。

制約

• |s|=4
• s は数字のみからなる

解法

ニコニコ文字列は1文字目3文字目,２文字目と3文字目を比較すれば解くことが可能です．

回答コード

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

int main(){
  string s;
  cin >> s;
  if(s.at(0)==s.at(2) && s.at(1)==s.at(3))cout << "Yes" << endl;
  else cout << "No" << endl;
}

A - ネクスト・クリスマス (パ研合宿コンペティション 3日目)

リンク: https://atcoder.jp/contests/pakencamp-2018-day3/tasks/pakencamp_2018_day3_a

問題文

今日は 2018 年 12 月 25 日。 クリスマス当日です。
これにちなんで、Y 年 M 月 D 日が何年後のクリスマスかどうかを計算するプログラムを書きなさい。
ただし、そもそもクリスマスではない場合は NOT CHRISTMAS DAY と出力しなさい。

制約

• Y は 2018 以上 2299 以下の整数
• M は 1 以上 12 以下の整数
• D は 1 以上 31 以下の整数
• Y 年 M 月 D 日は、グレゴリオ暦において存在する日付である。

解説

この問題はまずはその日がクリスマスであるかを確認します．
クリスマスの条件は M==12 && D==25 です．
クリスマスであれば 今のクリスマスとの差なので Yから2018を引いた数値を出力しましょう．

回答コード

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

int main(){
  int y,m,d;
  cin >> y >> m >> d;
  if(m==12&&d==25)cout << y-2018 << endl;
  else cout << "NOT CHRISTMAS DAY" << endl;
}

A - 配点 (CODE FESTIVAL 2018 qual A)

リンク: https://atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_a

問題文

あなたはあるコンテストのために問題を 3 問作りました。 検討の結果、これらの問題の配点は以下のようにすることになりました。

• 1 問目の配点は A 点または A+1 点にする。
• 2 問目の配点は B 点または B+1 点にする。
• 3 問目の配点は C 点または C+1 点にする。

3 問の配点の合計をちょうど S 点にすることができるかどうか判定してください。

制約

• 1≤A,B,C≤20
• 1≤S≤60
• 入力値はすべて整数である。

解説

複雑に見えますが，結局はdがA+B+CとA+B+C+3の範囲内に存在するのかを判別するだけです．

回答コード

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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a+b+c <= d && d <= a+b+c+3)cout << "Yes" << endl;
  else cout << "No" << endl;
}

B - ㍻の終焉を告げる (パ研合宿コンペティション 3日目)

リンク: https://atcoder.jp/contests/pakencamp-2018-day3/tasks/pakencamp_2018_day3_b

問題文

2018 年も間もなく終わりです。2019 年 5 月 1 日に新元号になることが発表されて以来、
2018 年は「㍻の終焉を告げる」年になりました。
さて、古くから続く PAKEN 国は、情報暦 1 年 1 月 1 日に第 1 代天皇が即位し、第 i 代天皇は丁度 $a_i$ 年間在位しました。天皇の退位式は情報暦の一年の一番最後の日である 12 月 31 日、即位式は情報暦の一年の一番最初の日である 1 月
1 日に行われるので、元号は天皇が変わる年の 12/31 と 1/1 の間に変わります。
現在の天皇は第 N+1 代天皇であるため、第 1 代から第 N 代天皇に関する在位期間のデータが与えられます。
PAKEN 国では、第 i 代 (1≤i≤N) 天皇がいる最後の年のことを「〇〇時代の終焉を告げる」年といいます。
情報暦 2018 年までに、何回「〇〇時代の終焉を告げる年」があったのでしょうか。ただし 2018 年も含めて数えるものとします。また、現在は情報暦 2018 年より後であるとします。

制約

• N は 1 以上 8000 以下の整数
• $a_i$ は 1 以上 10000 以下の整数

解説

この問題はそれぞれの天皇の在籍期間が順番に与えられるのでこれらを順番に足し合わせていった値が「〇〇時代の終焉を告げる」年になります．
なので，これらの累積が2018を超えるまでひたすら前から入力された数値を足していき，それができた回数が最終的な解になります．

回答コード

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

int main(){
  int n;
  cin >> n;
  long long cnt=0,sum=0;;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    sum += a;
    if(sum>2018)break;
    cnt++;
  }
  cout << cnt << endl;
}

B - チーム戦　(Teamwork)　(パ研合宿コンペティション 2日目)

リンク: https://atcoder.jp/contests/pakencamp-2018-day2/tasks/pakencamp_2018_day2_b

問題文

パ研という部活には、N 人の部員がいます。それぞれの部員には、年齢順に 1, 2, 3, ..., N と番号が付けられています。
部員 i の競技プログラミングの実力は $A_i$ です。競技プログラミングではチーム戦が多くあります。パ研では、「チームの戦闘力」を、チームで最も実力が低い人の実力の値、と定義しました。例えば、実力が 5, 4, 10 の人がいる 3 人チームの戦闘力は、4 となります。ある日突然、2020 年に開催される東京オリンピックの種目に、「競技プログラミング」が追加されました。この大会には、ちょうど D 人で構成されるチームで出場しなければなりません。パ研の部員全員が、代表選抜に応募したいです。その為、パ研はチーム分けを以下のような方法で行うことにしました。出来るだけ多くの人が、代表選抜に応募できることにする。その中で、チームの戦闘力の合計 が最大になるようにチーム編成をする。ただし、同じ人が複数のチームに入ってはならない。さて、チームの戦闘力の合計はいくつになるでしょうか？

制約

• N は 1 以上 1000 以下の整数
• D は 1 以上 10 以下の整数
• $A_i%$ は 1 以上 4208 以下の整数
• 全く同じ実力の部員はいない

解説

チームの戦闘力の合計の総和が最高になる条件は各チームの最弱の人の戦闘力がチームの戦闘力ということで強い人は強い人同士，弱い人は弱い人同士でチームを組むのが最適です．すると強い順にランキングをつけた時,上からの順位がdの倍数の人が各チームの最低の戦闘力の人となります．なので降順にソートしたのそれらの人の戦闘力を全て足すと答えが出てきます．

回答コード

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

int main(){
  int n,d;
  cin >> n >> d;
  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;
  if(n<d){ //１チームも作成できない時の処理
    cout << 0 << endl;
    return 0;
  }
  for(int i=d;i<=n;i+=d){
    ans+=vec.at(i-1);
  }
  cout << ans << endl;
}

A - 立て看板　(Kyoto University Programming Contest 2018)

リンク: https://atcoder.jp/contests/kupc2018/tasks/kupc2018_a

問題文

京都大学の周辺には立て看板が立てられています。
この立て看板が京都の伝統的な景観を破壊しているという噂を耳にしたあなたは、この噂が本当かどうか確かめることにしました。大学周辺には 1 から N まで番号付けられた N 枚の立て看板があり、 立て看板i は面積が $s_i$、派手さが $a_i$ となっています。立て看板i の景観破壊指数は $s_i$×$a_i$ で与えられます。
N 個の立て看板の景観破壊指数のうち最大の値を出力してください。

制約

• $1≤N≤100$
• $1≤s_i≤100 (1≤i≤N)$
• $1≤a_i≤100 (1≤i≤N)$
• 入力は全て整数である。

解説

各列の上下の積を出力するだけです．
二つの配列を用意してその上下でかけるのが一般的でしょう．
場合によっては多次元配列を使用すると楽かもしれないです．
ただ少し工夫をすれば配列一つだけにししてfor文の数を減らすことが可能です．

回答コード

#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);
  int ans = 0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    ans = max(ans,vec.at(i)*a);
  }
  cout << ans << endl;
}

B - Counting Roads (AtCoder Beginner Contest 061)

リンク: https://atcoder.jp/contests/abc061/tasks/abc061_b

問題文

N 個の都市があり、M 本の道路があります。i(1≦i≦M) 番目の道路は、都市 $a_i$ と 都市 $b_i (1≦a_i,bi≦N)$ を双方向に結んでいます。同じ 2 つの都市を結ぶ道路は、1 本とは限りません。各都市から他の都市に向けて、何本の道路が伸びているか求めてください。

制約

• $2≦N,M≦50$
• $1≦a_i,b_i≦N$
• $a_i≠b_i$
• 入力は全て整数である。

解説

一見難しそうに見えますが実は簡単です．AとBを繋ぐ道が１本あるということは都市Aと都市Bからそれぞれ1本の道が出ているということです．つまり$A_i$と$B_i$が入力される度にそれらに対応する都市の道の数を一つずつ加算するだけです．

回答コード

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> ans(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    ans.at(a-1)++;
    ans.at(b-1)++;
  }
  for(int i=0;i<n;i++)cout << ans.at(i) << endl;
}

B - Not Found(AtCoder Beginner Contest 071)

リンク: https://atcoder.jp/contests/abc071/tasks/abc071_b

問題文

英小文字からなる文字列 S が与えられます．
S に現れない英小文字であって，最も辞書順（アルファベット順）で小さいものを求めてください． ただし，S にすべての英小文字が現れる場合は，代わりに None を出力してください．

制約

• 1≤|S|≤105 (|S| は文字列 S の長さ)
• S は英小文字のみからなる．

解説

弊部の一年生には教えていないですが先日共有した記事に乗っていたASCIIコードを使用するとスマートに解くことが可能です．char型をint型に変換して(引くと自動的にint型にキャスト変換されます)してそれに対応する添字を持つ配列に呼び出された否かを格納します．その後a~zの範囲で呼び出されていあに数値があるか否かを全探索し，対応するものがあれば即表示して終了．最後までなければNoneを出力するという手順です．

回答コード

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

int main(){
  string s;
  cin >> s;
  vector<bool> vec(26,true); //一度も呼び出されていないのであればtrue
  for(char c:s)vec.at(c-97) = false; //小文字の'a'はASCIIコードが97なので97引いている
  for(int i=0;i<26;i++)if(vec.at(i)){
    cout << (char)(i+97) << endl; //97を足して元の数値を復元している
    return 0;
  }
  cout << "None" << endl;
}

B - Two Anagrams(AtCoder Beginner Contest 082)

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

問題文

英小文字のみからなる文字列 s, t が与えられます。 あなたは、
s の文字を好きな順に並べ替え、文字列 s′ を作ります。 また、t の文字を好きな順に並べ替え、文字列 t′ を作ります。 このとき、辞書順で s′<t′ となるようにできるか判定してください。

制約

• s, t の長さは 1 以上 100 以下である。
• s, t は英小文字のみからなる。

解説

sもtも好きなように並び替えれるのでsを辞書順で一番前の方になるように昇順にsortして,tを辞書順で一番後ろになるように降順にsortしましょう．そのsort後の２つの文字列をif文で比較すれば答えはすぐにわかります．

回答コード

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

int main(){
  string s,t;
  cin >> s >> t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  if(s<t)cout << "Yes" << endl;
  else cout << "No" << endl;
}

異世界転生 (技術室奥プログラミングコンテスト#4 Day1)

リンク: https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_c

問題文

kaisei705君は 10 進法で N 円を持ってコンビニに行こうとしていました。しかし、疲れからか不幸にもトラックに轢かれ、なんと異世界に転生してしまいます。神様によると、世界にはそれぞれ番号が付いており、番号 M の世界では M 進法が使われているということです。どうやら、転生した後の所持金は、転生先の表示で X 円のようです。

kaisei705「お願いします、元の世界に戻してください！」
神様「この世界の番号が分かったら、考えてやろう。」
kaisei705「（分からないよ...）」

さて、整数 N と文字列 X が与えられるので、彼の代わりに、転生した先の世界の番号 M を求めてあげてください。ただし、転生する前と後で所持金額は変わらないものとします。

制約

• N は整数である。
• 9≤N≤$10^18$
• 1≤|X|≤60
• 答え M は 2 以上 10 以下の整数であり、この問題の制約において 1 つに定まることが保証されている。

解説

この問題の難点は異常に大きな数字です．特にXをそのまま数字として受け取ってしますと$10^{60}$というとても受け取れない数値になってしまいます．なのでこれは文字列として受け取りましょう．なのでXの数値ではなく文字列として受け取りましょう．
あとはfor文で2~10までの全てのパターンを確認するのみです．その確認方法ですが１０進数であるnを各進数に変換します．
ただ，愚直に変換してしまうとlong long型でさえ格納できない可能性があるのでstring型に格納するために各桁をchar型にキャスト変換して文字列として格納していきます．この際，後ろから文字が追加されていくので事前にxを反転させておくと比較をスムーズに行うことが可能です．

回答コード

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

int main(){
  long long n; //nも大きいため long long を使用
  string x;
  cin >> n >> x;
  
  long long ans;
  reverse(x.begin(),x.end());
  for(ans=2;ans<11;ans++){
    string result="";
    long long cp=n;
    while(cp){
      result += (char)(cp%ans+48);
      cp/=ans;
    }
    if(x==result)cout << ans << endl;
  }
}

B - Emblem (square869120Contest #5)

リンク: https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_b

問題文

E869120 君は, square869120Contest #5 の開催を記念するために, 1,2,3,⋯,N+M の番号がつけられた N+M 個の円を用いて
2 次元平面上にエンブレムを作ろうとしている.番号 1,2,3,⋯,N の円は, 中心座標 $(x_i,y_i)$ と半径 $r_i$ が決まっている.その一方で, 番号N+1,N+2,N+3,⋯,N+M の円は, 中心座標 $(x_i,y_i)$ が決まっているが, 半径は決まっていない.エンブレムに使われる円は接してもよいが, どの円も他の円と交わるまたは含んではならないとき, 最も小さい円の半径を最大化しなさい.

制約

• N は 0 以上 100 以下の整数.
• M は 0 以上 100 以下の整数.
• N+M≥2
• $x_i,y_i(1≤i≤N+M)$ は −100 以上 100 以下の整数.
• $r_i$ は 1 以上 100 以下の整数.
• 入力で与えられる座標はすべて異なる.
• 番号 1,2,3,⋯,N の円は交差せず, ある円がほかの円を含まない.
• 番号 N+1,N+2,N+3,⋯,N+M の円は, 番号 1,2,3,⋯,N の円の内部または円周上にない.

解説

実装は面倒ですが回答が非常にわかりやすい問題です．
nもmも小さい数値なので
やる作業としては全ての円を比較し，その二つの円のみを考えた場合に取りうる最大の半径を求めます．
その取りうる最大の半径は以下のようになります．

• 比較元の半径がすでに決まっているなら比較元の半径
• 比較元の半径が決まっておらず比較対象の半径が決まっているなら二つの円の中心座標の直線距離から比較対象の半径を引いたものを
• お互いに決めっていないのであれば二つの円の中心座標の直線距離を２で割った値を

ただ，これは２つの円のみを考え場合なので他の円と重複する可能性があります．
なので全ての円でこれを行いその値の中で最小のもの値がその中で唯一ありうる値となります．
なのでその値を表示することでこの問題は解くことが可能です．

回答コード

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

int main(){
  cout << fixed << setprecision(16);
  int n,m;
  cin >> n >> m;
  vector<int> x(n+m);
  vector<int> y(n+m);
  vector<int> r(n);
  for(int i=0;i<n;i++)cin >> x.at(i) >> y.at(i) >> r.at(i);
  for(int i=0;i<m;i++)cin >> x.at(i+n) >> y.at(i+n);

  double ans = 1000000;
  for(int i=0;i<n+m;i++)for(int j=0;j<n+m;j++){
    if(i==j)continue; // 同じ円を比較しない
    if(i<n)ans = min(ans,(double)r.at(i)); //自分の半径が決まっているならそれを
    else if(j<n)ans = min(ans,pow(pow(x.at(i)-x.at(j),2)+pow(y.at(i)-y.at(j),2),0.5)-r.at(j)); // 相手の半径が決まっているなら二つの円の中心座標の直線距離からその半径を引いたものを
    else ans = min(ans,pow(pow(x.at(i)-x.at(j),2)+pow(y.at(i)-y.at(j),2),0.5)/2); //お互いに決めっていないのであれば二つの円の中心座標の直線距離を２で割った値を
  }
  cout << ans << endl;
}

バチャの結果

> Example様は部外からの参加の方です．

感想

普段と比較すると比較的難しい問題揃いだったのでもっと解けないかな〜と思っていたので以外にみなさんといてくれていたようで嬉しいです．今回から新しい試みとして ASCIIコード を使用する問題であったり long long 型が必要な大きな数値が出てくる問題を出したりしました．
こちらの記事に軽くまとめてありますので参考にしてください．
https://qiita.com/kubo_programmer/items/05f7b18c15a3e80b0d8a

今後のバチャ予定

• 9/10 13:30~16:30 PCK対策2.5 by コン研
• 9/12 13:30~16:30 PCK対策3rd by コン研
• 9/14 13:30~16:30 PCKの準備体操 by コン研

部外の人も参加可能なので是非ご参加ください