はじめに
- 本記事の内容は筆者自身の解釈による解法であり，必ずしも最も効率の良い解法であるとは限らない点をご容赦ください
- コンテストページ
目次
A. Exponential or Quadratic
B. Pizza
C. digitnum
D. AND and SUM
A. Exponential or Quadratic
| 正解者数/提出者数 | 7350/7762 |
|---|
問題文
$2^n > n^2$ ですか？
入力
$n$
- $n$ は $1$ 以上 $10^9$ 以下の整数
解法
シンプルにif文で比較して答えを出力
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
ll n; cin >> n;
if(pow(2,n) > n*n) cout << "Yes" << endl;
else cout << "No" << endl;
}
B. Pizza
| 正解者数/提出者数 | 5539/5797 |
|---|
問題文
ある円について，長さ $N$ の数列 $A$ を用いて次の手順で切れ込みを入れていきます．
- 最初に、円の中心から $12$ 時の方向に切れ込みをひとつ入れます．
- 次に、以下の操作を $N$ 回繰り返す．$i$ 回目の操作では以下を行います．
- まず、円を時計回りに $A_i$ 度回転させる
- 次に、円の中心から $12$ 時の方向に切れ込みをひとつ入れる。
このとき、最も大きな円の中心角が何度であるか求めてください．
入力
$N$
$A_1 ,A_2 \dots, A_N$
- 入力は全て整数
- $1 ≦ N ≦ 359$
- $1 ≦ A_i ≦ 359$
- 同じ場所に複数回切れ込みが入ることはない
解法
円の $12$ 時の方向を $0$ 度( $360$ 度)として，時計回りの方向に度数が増えていくと考えて，入力 $A_i$ がそれぞれ $0$ ~ $359$ 度のどの位置に切れ込みを入れることに相当するかをリストに記録していきます．
その後，リストを昇順に並び替えて，隣り合う切れ込みの間の中心角の角度を計算し，その中で最も大きい中心角が答えになります．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
int n; cin >> n;
vector<int> a(n);
rep(i,n) cin >> a[i];
vector<int> kireme; // 切れ込みを入れた角度(0~359)
kireme.push_back(0); // 最初に12時方向に切れ込みを入れる
int c = 0;
rep(i,n){
c += a[i];
if(c >= 360) c -= 360;
kireme.push_back(c);
}
sort(kireme.begin(), kireme.end());
int ans = 0;
rep(i,n){
int d = kireme[i+1] - kireme[i];
if(d > ans) ans = d;
}
int d = 360 - kireme[n];
if(d > ans) ans = d;
cout << ans << endl;
}
C. digitnum
| 正解者数/提出者数 | 3648/4637 |
|---|
問題文
整数 $N$ が与えられます．
$f(x) = (x$以下の正整数で，$x$と桁数が同じものの数)とするとき，
$f(1)+f(2)+⋯+f(N)$ を $998244353$ で割った余りを求めてください．
入力
$N$
- $N$ は整数
- $1 \leq N < 10^{18}$
解法
具体例として $N = 238$ の場合について考えてみます．
ここで，
$f(1)+f(2)+⋯+f(238)$
$= \lbrace f(1)+f(2)+⋯+f(9)\rbrace + \lbrace f(10)+f(11)+⋯+f(99)\rbrace + \lbrace f(100)+f(101)+⋯+f(238)\rbrace$
というように， 桁数が同じもの同士で区切って考えると，それぞれ次のように求まります．
$f(1)+f(2)+⋯+f(9) = 1 + 2 + ⋯ + 9 = \frac{9 (9 + 1)}{2} = 45$
$f(10)+f(11)+⋯+f(99) = 1 + 2 + ⋯ + 90 = \frac{90 (90 + 1)}{2} = 4095$
$f(1)+f(2)+⋯+f(9) = 1 + 2 + ⋯ + 139 = \frac{139 (139 + 1)}{2} = 9730$
以上より，最終的な答えは
$f(1)+f(2)+⋯+f(238) = 45 + 4095 + 9730 = 13870$
と求まります．
このように桁数ごとに区切って計算していくことで答えを求めることが可能です．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
ll n; cin >> n;
ll d = 998244353;
ll k = 10;
ll ans = 0;
while(true){
if(n < k){
ans += ((n - k/10 + 1)%d) * ((n - k/10 + 2)%d) / 2;
ans %= d;
break;
}
ans += ((k - k/10)%d) * ((k - k/10 + 1)%d) / 2;
ans %= d;
k *= 10;
}
cout << ans << endl;
}
D. AND and SUM
| 正解者数/提出者数 | 2615/3185 |
|---|
問題文
$T$ 個のテストケースについて、以下の問題を解いてください．
非負整数 $a,s$ が与えられます。以下の条件を両方とも満たす非負整数の組 $(x,y)$ は存在しますか
- $x \ AND \ y = a$
- $x + y = s$
入力
$T$
$a_1,s_1,\dots,a_T,s_T$
- $1 \leq T \leq 10^5$
- $0 \leq a,s < 2^{60}$
- 入力は全て整数
解法
( 1 ) $x \ AND \ y = a$
( 2 ) $x + y = s$
全ての数を2進数として考えます．
( 1 ) より， $a$ が $1$ である桁は $x,y$ どちらも $1$ にしなければならず， $a$ が $0$ である桁は $x,y$ どちらも $0$ か片方だけ $1$ にしなければなりません．
これより， $a$ が $1$ である桁と同じ桁の $x,y$ をどちらも $1$ に確定すると，
( 3 ) $s = x + y = ( a + x' ) + ( a + y' )$ （ $+$ は $XOR$ と等価 ）
と表せます．
ここで， $x',y'$ は次の条件を満たすことがわかります．
A : ( 3 ) の変換より， $a$ が $1$ である桁は $x',y'$ も $0$
B : $x',y'$ は $x,y$ から $a$ が $0$ である桁のみを抜き出したものであるため， $x',y'$ 共に同じ桁が $1$ になることはない
( 3 )を整理すると，
$s - 2a = x' + y'$
となり， $s - 2a = s'$ とすると
$s' = x' + y'$
と表せます．
次に， $s'$ について場合分けして考えてみます．
１） $s' < 0$ のとき
答えは明らかに "No" になります．
２） $s' \geq 0$ のとき
・ $s'$ が $0$ の桁は， $x',y'$ ともに $0$ （ $x'$ と $y'$ の $XOR$ をとったものが $s'$ であるため）
・ $s'$ が $1$ で $a$ が $0$ の桁は， $x',y'$ の片方が $1$ （( 1 )より， $x',y'$ の両方を $1$ にすることはできないため）
・ $s'$ が $1$ で $a$ が $1$ の桁が存在する場合は答えは"No"（条件Aより， $s'$ を $1$ にすることはできないため）
以上より，最終的な答えは
「$s - 2a \geq 0$」かつ「$(s - 2a) \ AND \ a = 0$ （$s - 2a$ と $a$ が共に $1$ である桁が存在しない）」なら "Yes" ，
それ以外なら "No"
となります．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
ll t; cin >> t;
while(t--){ // t個のテストケースを処理
ll a,s; cin >> a >> s;
if((s - 2 * a >= 0) && (((s - 2 * a) & a) == 0)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}