ABC #019参加しました。
ABCもARCと同じく、公式解説があるので説明は最小限です。
A – 高橋くんと年齢
問題概要
3つの数字が与えられるので中央値を答える。
解法
与えられる数値が3つなので、条件分岐で他の値以上、他の値以下の数値を判定しても問題無いです。また、単純にソートして2つ目の値を出力しても解けます。
コード
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| int a[3]; | |
| cin>>a[0]>>a[1]>>a[2]; | |
| sort(a,a+3); | |
| cout<<a[1]<<endl; | |
| return 0; | |
| } |
B – 高橋くんと文字列圧縮
問題概要
文字列が与えられるので、その文字列で同じ文字が連続する箇所を［文字］[繰り返し回数](ex. aaa -> a3)のような形式に変換して出力する。
解法
文字列の先頭から文字が連続している回数をカウントして、違う文字の箇所、または文字列の終端まできたら手前の文字と回数を出力すればOKです。
今回、答えを一回別のString変数に保存していますが、普通にC++ でやろうとするとint->stringの変換でsstreamやsprintfを使う等、ちょっと一手間かかります。ただ、C++11から変換関数が追加されているので、今回はそれを使用しています。ただ今回の問題であれば、別に変換しなくてもintのまま標準出力に出力してもOKです。
コード
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| string s; | |
| cin>>s; | |
| string ans; | |
| char tmp=s[0]; | |
| int cnt=1; | |
| for(int i=1;i<=s.size();i++) | |
| { | |
| if(i==s.size() || tmp!=s[i]) | |
| { | |
| ans+=tmp; | |
| ans+=to_string(cnt); | |
| if(i<s.size()) | |
| { | |
| tmp=s[i]; | |
| cnt=1; | |
| } | |
| } | |
| else | |
| cnt++; | |
| } | |
| cout<<ans<<endl; | |
| return 0; | |
| } |
C – 高橋くんと魔法の箱
問題概要
ある整数を入れると、その整数に対応する違う整数を返す箱がある。箱にxを入れた場合と2xを入れた場合、同じ数値が返ってくる。
N個の整数を箱に入れた時に、何種類の整数が返ってくるか答える。
解法
2xを入れた時とxを入れた時の値が同じなので、1度値を入れた際にその値を2で割り切れる間の数値でできる値は全て同じになります。
その元になるxの値を全てhashに保存しながら、すでにその値をチェックしていないかを確認して、はいっていなければその種類の数値は今まで発生していないため、種類のカウントを1増やし、全ての数値をチェックした後のカウントの値を返せばOKです。
(ただ、後で公式解説聞いてよく考えたら、値を割り終わるまで高々30回程度なので、途中結果をhashに入れなくても問題ありませんでした。)
コード
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| int n; | |
| set<int> hash; | |
| int ans=0; | |
| cin>>n; | |
| for(int i=0;i<n;i++) | |
| { | |
| int tmp; | |
| cin>>tmp; | |
| bool flag=true; | |
| if(hash.count(tmp)!=0) | |
| flag=false; | |
| hash.insert(tmp); | |
| while(tmp%2==0 && flag) | |
| { | |
| tmp/=2; | |
| if(hash.count(tmp)!=0) | |
| { | |
| flag=false; | |
| break; | |
| } | |
| hash.insert(tmp); | |
| } | |
| if(flag) | |
| ans++; | |
| } | |
| cout<<ans<<endl; | |
| return 0; | |
| } |
D – 高橋くんと木の直径
問題概要
ある重み付き根なし無向木がある。この木に対して2点間の距離を質問することができる。
木の任意の2点間の距離の最大値（木の直径）を求める。
ただし、質問の回数は100回以下とする。(部分点:質問回数:1300回)
解法
部分点解法の場合は、全ての2点間を質問しても質問回数は1300回を超えない(i=jやi,j とj,iを別個で聞かない場合)ので、全ての2点間についての距離を質問して、その最大値が答えです。
満点解法の場合、木の直径を求める方法としてdouble-sweep法という方法があります。ある1点と他の点の距離を調べ、最も遠い点を探します。そしてその点から最も遠い2点の距離が木の直径となります。(今回の問題であればN<=50なので、最大でも49+48=97回で解くことができます。)
私はこのやり方を知らなかった（あるいはどこかでやっても忘れてる）ため、本番後に公式解説を聞いてやっと解けました。なので、この方法の証明などは公式解説スライド等を参考にしてください。
（制約から2点*他の点の処理をしそうということまでは行けたのですが…）
コード
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| int n; | |
| cin>>n; | |
| long long int ans=0; | |
| for(int i=1;i<n;i++) | |
| for(int j=i+1;j<=n;j++) | |
| { | |
| cout<<"? "<<i<<" "<<j<<endl; | |
| long long int tmp; | |
| cin>>tmp; | |
| ans=max(ans,tmp); | |
| } | |
| cout<<"! "<<ans<<endl; | |
| return 0; | |
| } |
- 20点解法（本番中の回答）
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(int argc, char *argv[]) | |
| { | |
| int n; | |
| cin>>n; | |
| long long int ans=0; | |
| int num; | |
| for(int i=2;i<=n;i++) | |
| { | |
| cout<<"? "<<1<<" "<<i<<endl; | |
| long long int tmp; | |
| cin>>tmp; | |
| if(tmp>ans) | |
| { | |
| ans=tmp; | |
| num=i; | |
| } | |
| } | |
| for(int i=1;i<=n;i++) | |
| { | |
| if(i==num) | |
| continue; | |
| cout<<"? "<<num<<" "<<i<<endl; | |
| long long int tmp; | |
| cin>>tmp; | |
| ans=max(ans,tmp); | |
| } | |
| cout<<"! "<<ans<<endl; | |
| return 0; | |
| } |
- 満点解法（本番後の解き直し）