2021-02-06

Atcoder Biginner Contest 190 (ABC190)振り返り

A問題
B問題
C問題
D問題
感想

Atcoder Biginner Contest 190に参加しました。

A問題

　場合分けする。飴が多いほうが勝ち、飴の数が同じなら後手が勝ち。
まとめると高橋君が先手(C=0)かつ高橋君の飴が多い(A>B)のとき高橋君の勝ち。または高橋君が後手(C=1)かつ高橋君の飴の数が青木君以上(A>=B)のとき高橋君が勝ち。それ以外では青木君が勝ち。

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if(C==0 && A>B)cout << "Takahashi" << endl;
  else if(C==1 && A>=B)cout << "Takahashi" << endl;
  else cout << "Aoki" << endl;
}

B問題

B - Magic 3

　 $S>X_i$ かつ $Y_i>D$ となる $i$ が存在するか全探索する。

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

int main() {
  int N, S, D;
  cin >> N >> S >> D;
  vector<int>X(N);
  vector<int>Y(N);
  for(int i=0; i<N; i++)cin >> X[i] >> Y[i];
  
  for(int i=0; i<N; i++){
    if(X[i]<S && Y[i]>D){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
}

C問題

C - Bowls and Dishes

　皿 $C_i$ か皿 $D_i$ かを選ぶのでbit全探索をすれば良さそう。Kが16以下なので高々2¹⁶~6×10⁴であり、N, M, Kについてもループするので計算量は $O(2^ K (N + M + K))$ 程度となる。最大でも10⁷に満たないので時間は余裕。
　

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

int main() {
  int N, S, D;
  cin >> N >> S >> D;
  vector<int>X(N);
  vector<int>Y(N);
  for(int i=0; i<N; i++)cin >> X[i] >> Y[i];
  
  for(int i=0; i<N; i++){
    if(X[i]<S && Y[i]>D){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
}

D問題

D - Staircase Sequences

　この問題は2Nの約数を求める問題に言い換えることができる(by 公式解説)。
　ただ、直感的には次のような別解のほうが分かりやすいと思う。

　まず簡単のために、正の数(1以上)の範囲について考える。項数iの等差数列は、階段部分と長方形部分に分けることができる。逆にNから階段部分を除いた部分がiで割り切れるならば一辺がiの長方形が存在するため、この数列が存在する。 f:id:rxive:20210206185415p:plain

　次に負の数を含めた整数全体について考える。正の数の範囲で考えたそれぞれの数列に対して、増加分を相殺するような適切な範囲を含めることで必ず1つだけ対応する数列が存在している。つまり求める全体の数列の個数は正の範囲に限定した場合のちょうど2倍存在する。

f:id:rxive:20210206191230p:plain

以上をまとめると

$(N-i(i+1)/2) \% i=0$ を満たすiの個数を数えて2倍したものが求める答えである。

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

int main() {
  long long N;
  cin >> N;
  long long count =0;
  for(long long i=1; i*(i+1)/2<=N; i++){
    if((N-i*(i+1)/2)%i==0)count ++;
  }
  
  cout << count*2 << endl;
}

感想

　最近のA問題の中で一番難しいA。普通のB。初めてbit全探索を実装できたC(時間がかかった)。制約を見て計算量 $O(\sqrt{N})$ くらいになるはずだから、から逆算したD。ふいんきしか分からなかったE。　bit全探索できたことが一番成長した。　

2021-01-30

Atcoder Biginner Contest 189 (ABC189)振り返り

Atcoder Atcoder Biginner Contest 競技プログラミング

A問題
B問題
C問題
D問題
感想

Atcoder Biginner Contest 189に参加しました。

atcoder.jp

A問題

A - Slot

　 $C_1, C_2, C_3$ が等しいかどうかを確認する。

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

int main() {
  string S;
  cin >> S;
  if(S[0]==S[1] && S[0]==S[2])cout << "Won" << endl;
  else cout << "Lost" << endl;
}

B問題

B - Alcoholic

　飲んだアルコール量は $V_i \times \frac{P_i}{100}$ で計算できるのでこれが $X$ を始めて超える $i$ を探す。ただし、少数の計算は誤差を含む(コンピュータ内部では2進数で計算を行っているため0.01を正確に表せない)ので整数値同士を比較する。

　解答方針：初めて $V_i \times P_i > 100 \times X$ となる $i$ 、なければ-1を出力する。

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int>V(N);
  vector<int>P(N);
  for(int i=0; i<N; i++)cin >> V[i] >> P[i];
  
  int ans =-1;
  int Alc=0;
  for(int i=0; i<N; i++){
    Alc += V[i]*P[i];
    if(Alc>X*100){
      ans = i+1;
      break;
    }
  }
  cout << ans << endl;
}

C問題

C - Mandarin Orange

　まず全探索できるか考える。
　 $1\le l \le r \le N$ を満たすように $l$ と $r$ を全探索するには

  for(int l=1; l<=N; l++){
    for(int r=l; r<=N; r++){
      //適切な操作
    }
  }

のように二重ループで書くことができる。この時の計算量は[tex: O(N²)]で高々10⁸の計算量で、かつ簡単な操作なのでc++では十分に間に合うので全探索での実装を行う。
　次に $x$ について考えると、 $l \le i \le r$ を満たすすべての $i$ に対して $x \le A_i$ であるから、 $x=min({A_i}) (ただしl \le i \le r)$ である。この[te: x]に対して区間の長さ $r-l+1$ をかけたものが食べるみかんの個数となり、これの最大値を求める。

　解答方針： $x\times (r-l+1)=min({A_i})\times (r-l+1) (ただしl \le i \le r)$ の最大値を全探索により求める。

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

int main() {
  int N;
  cin >> N;
  vector<int>A(N);
  for(int i=0; i<N; i++)cin >> A[i];
  
  int ans=0;
  for(int l=0; l<N; l++){
    int x=A[l];
    for(int r=l; r<N; r++){
      x=min(x, A[r]);
      ans=max(x*(r-l+1), ans);
    }
  }
  
  cout << ans << endl;
}

D問題

D - Logical Expression

　最後がANDかORかでxがTrueかFalseかが変わりそう。

$S_N="AND"$ のとき $x_N = y_N = "True"$
$S_N="OR"$ のとき $x_N="True"$ ならば $y_N$ はなんでもいい
$x_N = "False"$ ならば $y_N = "True"$

　ここで $y_i="True"$ となる $x_0, ..., x_i$ の選び方の個数を $C(x_0, ... x_i)$ とすると、上の条件を考えて

$S_i="AND"$ のとき $C(x_0, ... x_i) = C(x_0, ..., x_{i-1})$
$S_i="OR"$ のとき $C(x_0, ..., x_i) = 2^ i+ C(x_0, ..., x_{i-1})$
ただし $C(x_0)=1$

となる。これをi=Nから0まで計算すればよい。

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

int main() {
  int N;
  cin >> N;
  vector<string>S(N);
  for(int i=0; i<N; i++)cin >> S[i];
  long long n=pow(2, N);
  
  long long ans=0;
  for(int i=0; i<N; i++){
    if(S[N-i-1]=="OR")ans+=n;
    n/=2;
  }
  ans++;
  
  cout << ans << endl;
  
}

感想

　A言われた通りにやる。B言われた通りにやる。C、計算量10⁸が間に合わないと思った。実際には余裕。D、後ろから見ていくところまでは思いついたが、解けず。EFは何をしていいか分からなかった。
　安定してDまで解けるようになりたい。解く速度を上げないと考察に時間が取れなくて厳しいので問題を解きまくっていこうかと思いました。3週連続ABCがあるので頑張ります。　

2021-01-11

Atcoder Biginner Contest 188 (ABC188)振り返り

Atcoder Atcoder Biginner Contest 競技プログラミング

A問題
B問題
C問題
D問題
感想

Atcoder Biginner Contest 188に参加しました。

atcoder.jp

A問題

atcoder.jp

　XとYのうち小さい数に3を足すと大きい数より大きくなるかどうかつまり、min(X, Y)+3>max(X, Y)となるかどうかを判別する。

　XとYの差が3未満と言い換えることができるのでabs(X-Y)<3としてもよい

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

int main() {
  int X, Y;
  cin >> X >> Y;

  if(min(X, Y)+3>max(X, Y))cout << "Yes" << endl;
  else cout << "No" << endl;
}

B問題

B - Orthogonality

問題文中にある通りに計算する。計算量O(N)で明らかに間に合う。

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

int main() {
  int N;
  cin >> N;
  vector<int>A(N);
  vector<int>B(N);
  for(int i=0; i<N; i++)cin >>A[i];
  for(int i=0; i<N; i++)cin >> B[i];
  
  int ans=0;
  for(int i=0; i<N; i++){
    ans+=A[i]*B[i];
  }
  
  if(ans==0)cout << "Yes" << endl;
  else cout << "No" << endl;
}

C問題

C - ABC Tournament

　決勝戦ではトーナメントの前半で最もレートが高い選手と後半で最もレートが高い選手が戦う。この二人のうちレートが低いほうが準優勝者である。よってそれぞれのレートと番号を求めればよい。

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

int main() {
  int N;
  cin >> N;
  int n=pow(2, N); //n=2^Nとする
  vector<int>A(n);
  for(int i=0; i<n; i++)cin >> A[i];
  int A1=0;  //トーナメント前半最高レート
  int A2=0;  //トーナメント後半最高レート
  int i1=0;  //前半最高レートの人の番号
  int i2=0;  //後半最高レートの人の番号
  
  for(int i=0; i<n/2; i++){
  //前半[0, n/2)での最高レートと番号をもとめる
    if(A1<A[i]){
      A1=A[i];
      i1=i;
    }
  }
  
  for(int i=n/2; i<n; i++){
  //後半[n/2, n)での最高レートと番号をもとめる
    if(A2<A[i]){
      A2=A[i];
      i2=i;
    }
  }

  //準優勝者の番号を出力して終了
  if(A1<A2)cout << i1+1 << endl;
  else cout << i2+1 << endl;
}

D問題

D - Snuke Prime
　ある日の使用サービスの合計料金と定額料金のうち安いほうを支払う。imos法(累積和)を用いて料金を計算すればよい。ただし日数が最大で10⁹であり一日ずつ計算すると間に合わないため、変化のない部分はまとめて計算する(座標圧縮というらしい)。

　例を参考に考えてみよう。

N=2 C=6
a[0]=1 b[0]=2 c[0]=4  //サービス0を1日目から2日目までの2日間利用
a[1]=2 b[1]=2 c[1]=4  //サービス1を2日目から2日目までの1日間利用

answer=10

　b[i]-a[i]では利用日数にならないので正しい日数が得られるようにa[i]から1引いて考える。(b[i]に1足すでもよい)
　利用料金はa[i]-1日目の終わりに+c[i]増えて、b[i]日目の終わりにに-c[i]増えるとすればaとbを区別せずにまとめることができる。 (imos法) 　実際にまとめた後にソートしてみると次のようになる。

N=2 C=6
a[0]-1= 0  c[0]= 4  //0日目終了時点の料金は0+4=4
a[1]-1= 1  c[1]= 4  //1日目終了時点の料金は4+4=8
  b[0]= 2 -c[0]= -4 //2日目終了時点の料金は8-4=4
  b[1]= 2 -c[1]= -4 //2日目終了時点の料金は8-4=0

　ここで定額料は6であることに注意すれば、
0~1日目料金4×1=4
1~2日目料金6×1=6
2日目以降0
　であるため和をとって答えは10になる。

　以上をまとめると次のようになる。
　1. a[i]をa[i]-1とする
　2. すべてのb[i]について-c[i]として(a[i]-1, c[i])と(b[i], c[i])をまとめてソートする。
　3. 料金変動があった日ごとに min(個別料金の和, 定額料金)×次の変動日までの日数 を計算して和をとる

では実際にやってみる。

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

int main() {
  int N, C;
  cin >> N >> C;
  vector<long long>a(N);
  vector<long long>b(N);
  vector<long long>c(N);
  
  for(int i=0; i<N; i++)cin >> a[i] >> b[i] >> c[i];
  vector<pair<long long, long long>>ABC(N*2);
  //a[i]とb[i]をまとめて一つにする。ソートしやすいようにpairを用いている
  
  for(int i=0; i<N; i++){
    ABC[i]=make_pair(a[i]-1, c[i]);  //a[i]-1日目の終わりにc[i]増加
    ABC[N+i]=make_pair(b[i], -c[i]);  //b[i]日目の終わりに-c[i]増加
  }
  
  sort(ABC.begin(), ABC.end());  //変化があった日付順になった
  
  long long Q=0;  //ある日利用したサービスの個別料金の和
  long long ans=0;  //答え、つまり支払う金額の和
  
  for(int i=0; i<N*2; i++){
    Q+=ABC.at(i).second;  //変動後の個別料金の和
    if(i<N*2-1){
      ans+=min(Q, C)*(ABC.at(i+1).first-ABC.at(i).first);
  //min(個別料金の和, 定額料金)×次の料金変動日までの日数
    }
  }
  
  
  cout << ans << endl;
}

感想

A~Cまでは簡単な印象。Dは日数が多いのでいかに計算量を減らすかを考えた。問題をみてすぐにimos法を考えたが座標圧縮と日数の調整に手間取った。EはDFSっぽいと思ったが、うまく計算量を落とすところまで頭が回らず解説を見てなんとなく理解。Fはわからない。　　

2021-01-03

Atcoder Biginner Contest 187 (ABC187)振り返り

Atcoder Atcoder Biginner Contest 競技プログラミング

A問題
B問題
C問題
D問題
感想

お久しぶりです。2021年あけましておめでとうございます。
私用で忙しかったためしばらく更新が遅れていました。無理のない程度に再開していきたいと思います。

Atcoder Biginner Contest 187に参加しました。 atcoder.jp

A問題

A - Large Digits
　10進法での各桁の和を求めます。
　Aを10で割った余り(A%10)を求めた後、Aを10で割って(A/10)一の位を除きます。
これを繰り返せして和をとれば(A)が分かり、Bについても同様にしてS(B)を求めて大きいほうを出力します。

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

int main() {
  int A, B;
  cin >> A >> B;
  int S_A=0;  int S_B=0;
//はじめS(A)=0, S(B)=0としておきます

  for(int i=0; i<3; i++){
    S_A+=A%10;  S_B+=B%10;
    A/=10;  B/=10;
/*A, Bの一の位をS(A), S(B)に足して, A,Bは10で割ります。
  桁数以上だけ繰り返します。*/
  }
  cout  << max(S_A, S_B)  << endl;
}

　一般に整数AをN進数で表したいときはNで割った余り(A%N)をメモしておきAを商に置き換えること(A/=N)を繰り返せば、下から順に各桁の数を求めることができます。計算量は $O( log_N(A)$ )程度でしょう。

B問題

B - Gentle Pairs
　素直に実装するとO(N²)で、Nは最大でも3000程度なので十分間に合います。
　さて、傾きの求め方は(yの増加量)/(xの増加量)ですので $-1 \le \frac{Y_j - Y_i}{X_j - X_i} \le 1$ を満たす(i, j)の個数をカウントすればよいことになります。
　ところで、分数に変数が含まれて分母が0になる可能性がある場合には分母を払っておくと実装が容易になることが多いですが、不等号を含むこの問題で分母を払うためには $X_j - X_i$ の符号で場合分けする必要があります(負の数をかけると大小関係が逆転するため)。幸いにも範囲が-1~1なので絶対値をとることで容易に解決します。つまり、 $|\frac{Y_j - Y_i}{X_j - X_i}| \le 1$ とまとめることができるので絶対値をつけたまま分母を払って以下のようになります。

$|Y_j - Y_i| \le |X_j - X_i|$

一次関数のグラフの傾きが-1以上1以下になるには「X方向の変化の大きさよりもY方向の変化の大きさが小さければよい」という直感的に理解しやすい式になりました。

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

int main() {
  int N;
  cin >> N;
  vector<int>X(N);
  vector<int>Y(N);
  for(int i=0; i<N; i++)cin >> X[i] >> Y[i];
  
  int ans=0;
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
//i<jなのでj=i+1からスタート
      if(abs(Y[j]-Y[i])<=abs(X[j]-X[i]))ans++;
 //条件にあてはまる個数をカウント
    }
  }
  
  cout << ans << endl;
}

C問題

C - 1-SAT
文字列 $S_i$ と'i'+ $S_i$ が両方存在すれば、それが不満な文字列である。最大でN=2*10⁵なのでお互いの文字列の組み合わせをすべて調べるとO(N²)となり間に合わない。
　set を使うと効率よく調べることができる(らしい)。setって何でしょうか。要検索です。ところでsetを知らない私はソートして順に調べました。
　方針としては!から始まる文字列配列S[i]と英小文字から始まる文字列配列S[j]をそれぞれソートした状態で用意しておき、S[i]>S[j]ならばj++;S[i]<S[j]ならばi++;とすればN回の要素の比較で済むため計算量はソートのO(NlogN)で間に合うはずだというもの。実装で2回ミスをした程度には煩雑なコードになってしまった。

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

int main() {
  int N;
  cin >> N;
  vector<string>S(N);
  for(int i=0; i<N; i++)cin >> S[i];
  sort(S.begin(), S.end());
  int count =0;
  for(int i=0; i<N; i++){
    if(S[i][0]=='!'){
      count ++;
      S[i]=S[i].substr(1);
    }
  }
  /*'!'スタートのものの個数を数えて
  比較しやすいように!は取り除いておく*/
  
  string ans="satisfiable";
  int j=count;
  for(int i=0; i<count; i++){
    if(j>=N)break;
    while(S[i]>S[j]){
      //S[i]>S[j]ならばj++;して次のものと比較
      j++;
      if(j>=N)break;
    }
    if(S[i]==S[j]){
      //一致したらそれが不満な文字列
      ans=S[i];
      break;
    }
  }
  cout << ans << endl;
}

D問題

D - Choose Me

高橋氏が演説した場合としなかった場合を比較してみる。
演説しなかった場合→演説した場合
青木氏　 $A_i$ → $0$ 　(変化 $-A_i$ )
高橋氏　 $0$ → $A_i + B_i$ 　(変化 $A_i + B_i$ )
　高橋氏は演説をすることで青木氏との差を $2A_i + B_i$ だけ縮めることができる。よって $2A_i + B_i$ が大きい順に町で演説を行えばよいことが分かる。

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

int main() {
  int N;
  cin >> N;
  vector<long long>A(N);
  vector<long long>B(N);
  vector<long long>C(N);
  long long sa =0;
  for(int i=0; i<N; i++){
    cin >> A[i] >> B[i];
    C[i]=A[i]*2+B[i];
    sa-=A[i];
//C[i]=2A[i]+B[i]とする。またあらかじめ青木氏の得票数の和をを引いておく
  }
  
  sort(C.begin(), C.end());
  reverse(C.begin(), C.end());
  //C[i]を大きい順に並べ替える
  for(int i=0; i<N; i++){
    sa+=C[i];
    if(sa>0){
      cout << i+1 << endl;
      break;
    }
  } 
//高橋氏の得票が上回ったら終了
}

感想

EF問題が分からない。グラフアルゴリズムの勉強しないといけないなーとか思ってはいるけれど、探索系をやりたい。
C問題でつまづいたのがとても痛手。個人的にはDのほうがずいぶん簡単だったがこれは知識不足。レート変化はほぼなかったから、2021年は可もなく不可もない(どちらかといえば不可な)滑り出しでした。　　

2020-12-30

整数の性質

数学競技プログラミング

　本記事は整数についての個人的なメモまとめです。厳密性より自分へのわかりやすさを優先しています。

0. 整数
- 整数とは
1. 倍数
2. 約数
3. 素数
4. 合同式(mod)
- 合同とは
- ・フェルマーの小定理

0. 整数

整数とは

..., -3, -2, -1, 0, 1, 2, 3, ...　といった数のこと。整数全体の集合はZで表す。
・-1, -2, -3, ...を負の整数という
・1, 2, 3, ...を正の整数という
・0, 1, 2, 3, ...を非負整数という
・自然数とは正の整数または非負整数のこと。(0を含むかどうかは定義によって変わるため、以後この記事では自然数という表現を使わないことにする)

以下では特に断りのない限り正の整数に限定して説明する。

1. 倍数

・倍数とは

　ある数aを整数倍したもの、つまりa, 2a, 3a, ...のことをaの倍数という。
　またaの倍数はaで割り切れる整数である。
例1　2の倍数　{2, 4, 6, 8, 10, ...}
例2　7の倍数　{7, 14, 21, 28, ...} 　

・最小公倍数

　aの倍数かつbの倍数となるものをaとbの公倍数といい、公倍数の中で最も小さいものをaとbの最小公倍数という。
例1　2と3の公倍数は{6, 12, 18, 24, ...}　最小公倍数は6　
例2　4と6の公倍数は{12, 24, 36, 48, ...}　最小公倍数は12　

・nの倍数の条件

・2の倍数……下一桁が2で割り切れる
・3の倍数……すべての桁の和が3で割り切れる
・4の倍数……下二桁が4で割り切れる
・5の倍数……下一桁が0または5
・6の倍数……2の倍数、3の倍数の両方の条件を満たす
・7の倍数……数を3桁ごとに区切り符号を変えながら順番に足したときの和が7で割り切れる
・8の倍数……下三桁が8で割り切れる
・9の倍数……すべての桁の和が9で割り切れる

簡単な説明・2の倍数……10は2で割り切れるので・3の倍数……10ⁿ≡1 (mod 3)なので・4の倍数……100は4で割り切れるので・5の倍数……10は5で割り切れるので・6の倍数……2と3の公倍数、明らか・8の倍数……1000は8で割り切れるので・9の倍数……10ⁿ≡1 (mod 9)なので

コメント　7の倍数、使う機会なさそう

2. 約数

・約数とは

　ある整数を割り切ることのできる整数のこと。例　10の約数は{1, 2, 5, 10}

・最大公約数

　整数a, bをともに割り切ることのできる整数を公約数といい、最も大きな公約数を最大公約数という。aとbの最大公約数が1(公約数が1のみ)のとき、aとbは互いに素であるという。例　24と32の公約数は{1, 2, 4, 8}　最大公約数は 8

・ユークリッドの互除法

　最大公約数を求める有名アルゴリズム。計算量は $O(log(min(a, b)))$ a, b(a>b)の最大公約数を求めるには割り算の余り(a%b)でbを割り、そのあまりでa%bを割り……をあまりがゼロになるまで繰り返す。

aとbの最大公約数G,としてa=AG, b=BG (AとBは互いに素), 商q, 余りr(0≦r<b)としたとき $a = qb + r$ となるから
$AG = qBG + r$ すなわち
$r = (A-qB)G$ であるからrはGの倍数である。

AとBが互いに素であるからBと(A-qB)も互いに素である。よってbとrの最大公約数はGである。
一方で0≦r<bであるから余りは明らかに単調減少するため0に収束し、その時の割る数がGとなる。

3. 素数

・素数とは

　素数とは1と自分自身以外の約数を持たない整数
　2, 3, 5, 7, 11, 13, ...
　なお、2以上の素数でない数は合成数という。

・素数判定

　√Nまでの数で割り切れなければNは素数。

　面積Nの長方形をイメージしてみよう。
　長辺と短辺があるから短辺は√N以下の長さになるし、最大でも正方形のとき√Nだから√Nまで調べて割り切れなければそれは素数だ。
　約数をすべて知りたいときも√Nまででよい。短辺が分かれば長辺もわかるから。

・エラトステネスの篩

　n以下の素数を見つけるアルゴリズム。計算量は $O(nlog(logn))$
　素数判定を何度も行うなら、あらかじめ全て求めておく。

　2~Nまでの数に対して小さいほうから順に
1. 素数リストに移動 2. 倍数を削除
を繰り返し、√Nまで判定した時点で残ったものをすべて素数リストに移動する。

・素因数分解

　合成数を素数の掛け算に分解する。

4. 合同式(mod)

合同とは

　大雑把に言えば「整数nで割った余りが等しい」
　123≡3 (mod 12), 24≡3 (mod 7)

　合同式の性質として
　・足し算, 123+5≡3+5≡8 (mod 12)
　・引き算, 24-3≡3-3≡0 (mod 7)
　・掛け算(累乗含む), 123²≡15129≡3³≡9 (mod 12)
が普通の整数と同様に扱える。
ただし合同式の割り算は一般には成り立たないため逆数に相当する逆元を用いる(らしい)。
逆元を求めるにはフェルマーの小定理か拡張ユークリッドの互除法を用いる。

「1000000007 で割ったあまり」の求め方を総特集！〜逆元から離散対数まで〜 - Qiita

・フェルマーの小定理

aとpが互いに素のとき
a^p-1≡1 (mod p)
逆元を求めるときに使える。

2020-11-29

Atcoder Regular Contest 109 (ARC109)振り返り

Atcoder Regular Contest 競技プログラミング Atcoder

A問題
B問題
C問題
感想

Atcoder Regular Contest109に参加しました。 AtCoder Regular Contest 109 - AtCoder

A問題

A - Hands f:id:rxive:20201129025215p:plain 　上の図のように建物Aと建物Bは非対称につながっている。aからbに移動するときには上への移動と下への移動で場合分けすればよい。
　・下方向への移動(a>b)の場合
　建物間の移動には最低1回は廊下を通る必要があるがこの時斜めに移動するのが最短ルート。さらに下の階に移動するにはy分かけて階段で降りるか2x分かけて廊下を使うかのどちらかであり、min(y, 2x)を残りの階数(b-a-1)だけ足せばよい。
　・上方向への移動
　建物AからBへの移動は水平移動のため(b-a)階分の上への移動が必要。こちらもmin(y, 2x)だけ時間がかかるからこの通りに場合分けして出力する。なおa=bのときは上への移動に含まれる(b-a=0となるので)。

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

int main() {
  int a, b, x, y;
  cin >> a >> b >> x >> y;
  if(a>b)cout << x+min(x*2, y)*(a-b-1) << endl;
  else cout << x+min(x*2, y)*(b-a) << endl;
}

B問題

B - log

　長さn+1の丸太をどのように切るかのみを考えればよい。さらに言えば、長い丸太を1本作るよりも短い丸太を多く作るほうがお金の節約になるため、長さ1,2,...の丸太を作るのが最善となる。(n+1の丸太を1とnに切断してもとの長さがnの丸太を切るとき、長さn丸太を切るのとn+1の丸太から切り出した長さn丸太を切るのは変わらない)
　ここで長さ1, 2, 3, ..., kの丸太の長さの和がn+1を超えない最大のkが分かればn+1-kが求める答えとなる(n+1本の丸太のうち短いk本はいらなくなるので)。丸太を切り出せるだけ切り出し続けると以下のようになる。

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

int main() {
  int64_t n, maruta, k;
  cin >>n;
  maruta=n+1; //長さn+1の丸太
  k=0;  //切り出す丸太の長さ
  while(true){
    if(maruta>=k+1){
      k++;
      maruta-=k;
    }
// 丸太から次の長さを切り出せるなら切り出す
    else break;
  }
// 切り出せなくなったら終わり
  cout << n+1-k << endl;
}

このコードでACできるが実行時間が650 msほどかかる。最悪のケースでは1414213560回の計算を繰り返すのでc++でもぎりぎりだったと思われる。そこでkの値をより速く収束させたい。公式解説では二分探索により高速化を図っているがここではkとn+1の関係から大雑把に値を求めてみる。1からkまでの和とn+1の関係から

$\frac{1}{2}k(k+1)\le n+1$

両辺に2をかけてルートをとれば

$k \le \sqrt{k(k+1)}\le \sqrt{2(n+1)}$

であるから、誤差による不都合を避けるために $k=\sqrt{2(n+1)}-1$ くらいから計算を行えば高速化できそうである。

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

int main() {
  int64_t n, maruta, k;
  cin >>n;
  maruta=n+1; //長さn+1の丸太
  //切り出す丸太の長さ
  k =sqrt(n*2)-1; //kにあたりをつけておく
  maruta -=k*(k+1)/2;//kまでの和を引く、以下同じ
  
  while(true){
    if(maruta>=k+1){
      k++;
      maruta-=k;
    }
    else break;
  }
  cout << n+1-k << endl;
}

実行時間は8 msになった。

C問題

C - Large RPS Tournament 　参加者が出す得意な手は周期性を持っていることが明らかである。例えばn=3, k=4, s=RPSのときには参加者1,2,...,16の出す手はR, P, S, R, P, S, R, P, S, ..., Rとなるが、これは参加者分だけs=RPSを繰り返していることが分かる。
　1回戦が終わった後を考えると参加者は半分になり、その得意な手はP, R, S, P, R, S, P, Rである。これはPRSの繰り返しである。このように長さnの文字列が変化しながら繰り返している。一方で参加者は半分に減り続けてk回後に優勝者ただ1人になるため、k回後の文字列の先頭の文字が優勝者の得意な手となるためこれを求めればよい。
　与えられた文字列を2倍にして、次の文字列を求めることを繰り返せばよい。

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

int main() {
  int n, k;
  string s, s1;
  cin >> n >> k >> s;
  
  for(int i=0; i<k; i++){
    s+=s;
/*勝負により文字列が半分になる。
周期性を維持するために長さを2倍にしておく。*/
    for(int j=0; j<n*2; j+=2){
      if(s[j]=='R'&&s[j+1]=='S')s1.push_back('R');
      else if(s[j]=='P'&&s[j+1]=='R')s1.push_back('P');
      else if(s[j]=='S'&&s[j+1]=='P')s1.push_back('S');
      else s1.push_back(s[j+1]);
    }
/*奇数番目が勝ったらその手を、そうでなければ偶数番目の手を
空文字列に追加する。*/
    s=s1;
    s1="";
/*文字列sを更新しs1を空にする*/
  } 
  cout << s[0] << endl; 
}

感想

　緑コーダーになったのでARCにも参加してみました。今回は規則性に気づければ解ける問題だったようでC問題まで解けました。嬉しい。D以降はわかりません。

2020-11-26

Atcoder緑になりました【色変記事】

Atcoder 競技プログラミング雑記

f:id:rxive:20201125222116p:plain
　先日のABCで入緑したので界隈恒例の色変記事を書いていきたいと思います。

初めに
自己紹介
灰色(0~399)の時にやったこと
茶色(400~799)の時にやったこと
今後の目標
参考にさせていただいたサイト

初めに

　私が初めて競プロのコンテストに参加したのは2020年5月30日で、11月22日のABC184にて緑になることができました。
プログラミングはゼロからのスタートでしたが緑になることを目標に半年間続けてきました。目標を達成して区切りがついたということで、緑になるまでにやったことと思ったことをまとめておきたいと思います。

自己紹介

　参考までに競プロを始めた時点でのスペックを書いておきます。

理系大学院生(非情報系)
- 高校数学は数IIIまで学習済み
プログラミング経験なし
- if文for文聞いたことあるな程度。

プログラミングできないので典型的なアルゴリズム問題が苦手で数学的な考察だけで解決できる問題のほうが得意です。

灰色(0~399)の時にやったこと

　まず入出力もできなかったのでAPG4bで勉強しました。2章までやればAB問題くらいまでは解けるとのことだったので2章まで確認した後コンテストに参加しました。その後は以下の内容を行っています。

毎週コンテストに参加する

　参加回数が少ない(14回以下？)とレートが低く出るのでABCが開催される時には必ず参加した。ABC相当の企業コンにも積極的に参加して参加回数を稼ぐと同時にモチベーションを維持するようにした。

文字列や配列、他よく使うものの操作をすぐに確認できるようにした

　解法を考える時間よりもコードの書き方を調べる時間のほうが長かったため、使うたびにメモしたりまとめのブログ等をブックマークしたりした。すべて覚えずに方法があることを知っていればよいというスタンス。

過去問を解く

　Atcoder Problemsで適度な難易度の過去問を解いた。

　特に最後の問題を解くことが一番大事だと思います。毎週末しかコードを書かない状態では不慣れなままコンテストに出続けることになって伸びないし、さらに出会う問題のパターンが限られているため成長しにくいと感じました。難しすぎると何も理解できないので頭を使って解けるか新しい知識がつくようなものがよいし、虚無埋めは面白くなさそうなのでやってません。Training のeasy100問解いたらC問題にも手が出せるようになり、数回後に茶に突入したので間違っていないはず。

茶色(400~799)の時にやったこと

　灰色の時代とあまりかわりません。知識面の拡充と過去問演習を地味に続けていたら少しずつ伸びて緑になったという感じです。最近はABCの3完かたまにプラスでDが解けていた感じです。解けそうだった問題は解説を読んで振り返っています。
　知識面で増えた内容はtupleやabs他、「累積和」と「しゃくとり法」です。緑色になるには~水色になるには~系の記事を参考に少しだけ増えました。標準ライブラリ、便利ですね。累積和、よく使う和はあらかじめ計算してメモして持っておくと便利、なるほどです。実際とても便利でうまく使うと計算量が減ってTLEしにくくなるので何かと組み合わせてよく使います。知っててよかった累積和。一方でしゃくとり法は累積和ほどの使用頻度はない気がします(個人の感想です)。今のところこれくらいしか記憶にありません。気づいていないだけで世界にはしゃくとり法がたくさんあるのかな。

　プログラミングとして勉強していないだけで約数・素数・整数関連の内容はたぶんできると思います。中学・高校数学ができてある程度の考察力があればなんとかなります。できないとC問題以降で苦労しそうな印象が強いです。やりましょう。
　数学と考察ができる代わりに私は文字列が苦手です。文字列の操作はあまり出題しないでほしいなあ。

今後の目標

　緑の次は水色コーダーになれたらよいと思います。1年くらいかかるかもしれませんし、もっと先かあるいは緑のままかもしれませんが目標にしておきます。
　今後勉強する内容として、

動的計画法(DP)
幅優先探索(BFS)
深さ優先探索(DFS)
キューとスタック、グラフ、木

あたりを考えています。ブログの内容も自分なりに初等数学やアルゴリズムに触れられるようにしていきたいという気持ちはあります。やれたらやる。

参考にさせていただいたサイト

　最後になりますがこれまで利用して大変参考になった役に立つサイトの紹介をもって感謝の意を表します。ありがとうございました。