AtCoder ABC168【ABCD=AC】 - おはやし日記

こんにちは。ABC168でした。

今回は48分でDまで解けました！しかもWA無し！

Eはまだ無理ですね、見当もつかない。

A

提出

AC

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int N;
  cin>>N;
  N %= 10;
  switch(N){
    case 2:
    case 4:
    case 5:
    case 7:
    case 9: cout<<"hon\n"; break;
    case 0:
    case 1:
    case 6:
    case 8: cout<<"pon\n"; break;
    case 3: cout<<"bon\n"; break;
  }
  return 0;
}

入力したNを、10での余りをとって1桁目だけにして分岐

if文だとめんどいのでswitch文で書きました。

B

提出

AC

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int K;
  cin>>K;
  string S;
  cin>>S;
  if(S.size()>K){
    for(int i=0; i<K; i++)cout<<S[i];
    cout<<"..."<<endl;
  }else{
    cout<<S<<endl;
  }
}

文字数の条件で分岐して、指定された通りに出力。

C

ミソは、時針の角度が、分の値によって微妙に進んでいることですね

2本の針がなす角度を $\theta$ として、求める長さ $C$ は余弦定理から

$$ C^{2} = A^{2} + B^{2} - 2AB \cos \theta $$

として求められます。

提出

AC提出からちょっとコメント手直し

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

int main(){
  cout<<fixed<<setprecision(10);
  double A,B;
  double H,M;
  cin>>A>>B>>H>>M;

  double h, m; //0時0分から時計回りの角度（ラジアン）
  
  m=2*M_PI*M/60; //分針の角度

  H += M/60; //分によって時を調整。30分だったら0.5時。そんな感じに進める
  h = 2*M_PI*H/12; //時針の角度

  double theta = min(abs(h-m), 2*M_PI-abs(h-m)); //針のなす角度。小さい方を取る

  //この2行で余弦定理を計算
  double c = A*A + B*B - 2*A*B*cos(theta);
  c = sqrt(c);

  cout<<c<<endl;
}

$\cos \theta = \cos (2\pi - \theta)$ なので途中で針のなす角度の「小さい方を取る」のはいらん操作でしたね。まあええわ

追記 : メイン関数冒頭のcout<<fixed<<setprecision(10);で小数点以下10桁まで吐き出すようにしてます。

D

方針 : 図を書いてみたら、

1から行ける部屋 $i$ には1への道しるべを置く
そうすることで $i$ にたどり着いたあと最短で1に行ける（基本発想）
例えば入力例2では最初に 5,6 の部屋に道しるべto1 を置く
5,6の部屋から行ける部屋 $j$ にはそれぞれ5,6への道しるべを置く
そうすることで $j$ にたどり着いたあと最短で1に行ける（5,6からは1への最短が示されているので）
入力例2では、2->6と行ける。また3->5と行ける。4は、5,6のどちらにもつながってるので、とりあえずどちらかへの道しるべがあればいい

こんな感じで「幅優先探索」をすると、「1に最短で道1本で行ける部屋」「1に最短で道2本で行ける部屋」……がわかり、どの部屋でも「1に最短で道n本で行ける部屋」として分類できる。

出力としてNoはあり得ない。

1から、階層を降りていくイメージ

入力例2では

地上階 … 部屋1
地下1階 … 部屋5,6
地下2階 … 部屋2,3,4

というイメージで、どの部屋にも1つ上の階層に上がる道しるべを置けば良い。

深さ優先探索をしてしまうとその名の通り深くまで潜ってしまう。例えば部屋が山手線みたいに輪っかになってたら、と考えると良いと思う。

提出

AC

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

/* vector */
using vi = vector<int>;
using vvi = vector<vi>;
#define pb push_back

int main(){
  int N,M;
  cin>>N>>M;

  vvi cango(N);//それぞれの部屋からいける部屋のリスト
  int a,b;
  for(int i=0; i<M; i++){
    cin>>a>>b;
    a--;b--;
    cango[a].pb(b);
    cango[b].pb(a);
  }

  vi sirube(N, -1);//それぞれの置く道しるべ -1は無記入で初期化
  sirube[0] = 0;//最初の部屋にはなんかかいとけ <- 別に-1のままで良かったのでは

  queue<int> unchecked;//調査したい部屋を入れるキュー
  unchecked.push(0); //初期は部屋1（添字は0）の調査

  while(!unchecked.empty()){
    int current = unchecked.front();
    unchecked.pop();

    for(int next: cango[current]){
      //行ける部屋を調べてみる
      if(sirube[next]==-1){
        //道しるべなし
        sirube[next] = current+1;//道しるべは1始まりに注意
        
        unchecked.push(next);
      }
      //道しるべがあったらその部屋は無視する
    }
  }

  cout<<"Yes\n";
  for(int i=1; i<N; i++){
    cout<<sirube[i]<<endl;
  }
}

おしまい

グラフ問題が解けてえらい！

Eについてはちゃんと勉強しておこうと思います。おしまい。