秘密の本棚

気になることをなんでも書きます

AtCoder Beginner Contest 108

AtCoder プログラミング

AtCoder Beginner Contest 108 - AtCoder

A - Pair

問題

A - Pair

考察

1以上K以下の偶数と奇数の選び方の個数を求める。偶数の個数はK/2で、奇数の個数は(K+1)/2で求まるので、その積を返す。

コード

int main(){
  ll k;
  cin >> k;
  ll even = k/2;
  ll odd = (k+1)/2;
  cout << even*odd << endl;
  return 0;
}

B - Ruined Square

問題

B - Ruined Square

考察

xy平面上の2点P_1,P_2の座標が与えられ、反時計回りに正方形を構成するように残り2つの頂点を定めるときの頂点の座標を求める。
\vec{P_1P_2}に着目し、残りの頂点の座標はこのベクトルを反時計回りに90°回転させて足していけば求まる。

コード

typedef pair<ll, ll> P;

P rotate(P s, P t){
  P p;
  p.first = s.second-t.second+t.first;
  p.second = t.second-s.first+t.first;
  return p;
}

int main(){
  P p1, p2, p3, p4;
  cin >> p1.first >> p1.second >> p2.first >> p2.second;
  p3 = rotate(p1,p2);
  p4 = rotate(p2,p3);
  cout << p3.first << " " << p3.second << " " << p4.first << " " << p4.second << endl;
  return 0;
}

C - Triangular Relationship

問題

C - Triangular Relationship

考察

1以上N以下の整数a,b,cに関して、a+b,b+c,c+aがすべてKの倍数となるようなa,b,cの組み合わせの個数を求める。
aを固定すると、b,cが満たすべき条件は「b,cはともにKで割って(K-a)\%K余り、かつb+cはKで割り切れる」となる。結局、これは2\times(K-a)がKで割り切れるという条件のもとで、b,cを1以上N以下の、Kで割って(K-a)\%K余る整数の中から選ぶと考えることができる。aがKの倍数であるかどうかで場合分けして求めればよい。a-Kは負になることがあるので、剰余の計算をするときは十分大きいKの倍数を足しておかないと計算が違ってしまうので注意が必要。

コード

int main(){
  ll n,k;
  cin >> n >> k;
  ll ans = 0;
  for(ll a = 1; a<= n; a++){
    if(2*(k-a+n*k)%k!=0) continue;
    ll bc = (a%k==0) ? n/k : (n+(k-a+n*k)%k)/k;
    ans += bc*bc;
  }
  cout << ans << endl;
  return 0;
}

D - All Your Paths are Different Lengths

問題

D - All Your Paths are Different Lengths

考察

整数Lに対し、20以下の自然数Nを定めて頂点1から頂点Nまでのパスの長さが0以上L-1以下のすべての整数をとるようなグラフを1つ求める。
まずLがL=2^{x}とかける場合は簡単で、N=x+1としてi=1,2,\cdots,N-1について頂点iと頂点i+1の間に長さ2^{i-1}の辺と長さ0の辺を加えることで実現できる。
次にLがこの形で表せないとき、N=\log_2(L)+1として同じように辺を加えると2^{N-1}-1以下の長さのパスができるが、ここで「最大のパスの長さがL以上にならないようにパスを加えていく」ことを考える。
現時点で最大のパスの長さをmaxとおくと、max+1以上L-1以下のパスをつくるためには長さmax+1の辺を、この辺を通るすべてのパスの長さがL-1以下となるように頂点yと頂点Nの間に加えればよい。このyはy=\log_2(L-max-1)+1と計算でき、この操作を行うことでmaxは2^{y-1}増加する。

コード

struct edge{ll from, to, weight;};

int main(){
  ll L;
  cin >> L;
  ll N = floor(log2(L))+1;
  vector<edge> E;
  for(ll i = 1; i <= N-1; i++){
    edge e;
    e.from = i, e.to = i+1, e.weight = 1<<(i-1);
    E.push_back(e);
    e.weight = 0;
    E.push_back(e);
  }
  ll max = (1<<(N-1)) - 1;
  while(max!=L-1){
    edge e;
    e.from = floor(log2(L-max-1))+1, e.to = N; e.weight = max+1;
    E.push_back(e);
    max += 1<<(e.from-1);
  }
  cout << N << " " << E.size() << endl;
  for(auto e: E){
    cout << e.from << " " << e.to << " " << e.weight << endl;
  }
  return 0;
}

雑感

今回は不参加で、後日解いてみましたがDはキツかったです。Nが20以下という制約も結構厳しいと思いました。最近2回はD問題が難しすぎます。