はじめに
- 本記事の内容は筆者自身の解釈による解法であり，必ずしも最も効率の良い解法であるとは限らない点をご容赦ください
- コンテストページ
目次
A. Horizon
B. Integer Division
C. Knight Fork
D. Prime Sum Game
A. Horizon
| 正解者数/提出者数 | 7196/7378 |
|---|
問題文
地上 $x$ メートルの高さから見える水平線は $x \ (12800000+x)$ メートル先にあるとするとき，
地上 $H$ メートルの高さから見える水平線が何メートル先にあるか求めてください．
入力
$H$
- $1 \leq H \leq 10^5$
- $H$ は整数である
解法
入力 $H$ に対して $H \ (12800000+H)$ を出力します．
出力桁数に注意．
コード
#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(){
double h; cin >> h;
cout << fixed << std::setprecision(15) << sqrt(h*(12800000.0+h)) << endl;
}
B. Integer Division
| 正解者数/提出者数 | 6658/7241 |
|---|
問題文
$-10^{18}$ 以上 $10^{18}$ 以下の整数 $X$ が与えられるので， $\lfloor \frac{X}{10} \rfloor$ を出力してください．
ただし，実数 $x$ に対して，「$x$ 以下の整数の中で最大の整数」を $\lfloor x \rfloor$ と表します．
入力
$X$
- $-10^{18} \leq X \leq 10^{18}$
- 入力は全て整数である．
解法
次のように場合分けして考えます．
( 1 ) $X$ が10で割り切れる場合
$\frac{X}{10}$ が答えになります．
( 2 ) $X$ が10で割り切れない場合
- $X$ が負数の場合は $\frac{X}{10} - 1$
- $X$ が正数の場合は $\frac{X}{10}$
が答えになります．
コード
#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 x; cin >> x;
if(x%10==0) cout << x/10 << endl;
else{
if(x<0) cout << x/10-1 << endl;
else cout << x/10 << endl;
}
}
C. Knight Fork
| 正解者数/提出者数 | 5557/6070 |
|---|
問題文
$xy$ 平面上の $2$ つ格子点 $(x_1,y_1),(x_2,y_2)$ からの距離がともに $\sqrt 5$ である格子点は存在しますか？
入力
$x_1 \quad y_1 \quad x_2 \quad y_2$
- $-10^9 \leq x_1 \leq 10^9$
- $-10^9 \leq y_1 \leq 10^9$
- $-10^9 \leq x_2 \leq 10^9$
- $-10^9 \leq x_2 \leq 10^9$
- $(x_1,y_1) \neq (x_2,y_2)$
解法
問題ページの図を見ると，ある格子点についてその格子点からの距離が $\sqrt 5$ である格子点は高々8つしか存在しないことがわかります．
よって， $2$ つ格子点 $(x_1,y_1),(x_2,y_2)$ について各格子点からの距離が $\sqrt 5$ である格子点を計算し，それらを総当たりで比較して一致する点があれば "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 x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
vector<pair<ll,ll>> xy1;
vector<pair<ll,ll>> xy2;
xy1 = {make_pair(x1+2,y1+1),make_pair(x1+1,y1+2),make_pair(x1+2,y1-1),make_pair(x1+1,y1-2),
make_pair(x1-2,y1+1),make_pair(x1-1,y1+2),make_pair(x1-2,y1-1),make_pair(x1-1,y1-2)};
xy2 = {make_pair(x2+2,y2+1),make_pair(x2+1,y2+2),make_pair(x2+2,y2-1),make_pair(x2+1,y2-2),
make_pair(x2-2,y2+1),make_pair(x2-1,y2+2),make_pair(x2-2,y2-1),make_pair(x2-1,y2-2)};
rep(i,8){
rep(j,8){
if(xy1[i].first==xy2[j].first && xy1[i].second==xy2[j].second){
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
}
D. Prime Sum Game
| 正解者数/提出者数 | 5167/5529 |
|---|
問題文
高橋君と青木君が次のようなゲームをします．
- まず，高橋君が $A$ 以上 $B$ 以下の好きな整数を選び，青木君に伝える
- 次に，青木君が $C$ 以上 $D$ 以下の好きな整数を選ぶ
- 二人の選んだ整数の和が素数なら青木君の勝ち，そうでなければ高橋君の勝ち
二人が最適な戦略を取るとき，どちらが勝ちますか？
入力
$A \quad B \quad C \quad D$
- $1 \leq A \leq B \leq 100$
- $1 \leq C \leq D \leq 100$
- 入力に含まれる値は全て整数である
解法
二人がともに最適な戦略を取るとき， $A$ 以上 $B$ 以下の整数の中で $C$ 以上 $D$ 以下のどの数を足しても素数にならないような整数が存在する場合，その整数を選択することで高橋君の勝利が確定します．逆に，それ以外の場合は青木君の勝利が確定します．
以上のことから， $A \leq i \leq B$ を満たす $i$ について $C \leq j \leq D$ を満たす $j$ をそれぞれ選んで $i + j$ が素数かどうかを判定し，ある $i$ についてどの $j$ を選択しても $i + j$ が素数にならないような $i$ が存在する場合は "Takahashi"，それ以外の場合は "Aoki" が答えになります．
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}
int main(){
int a,b,c,d; cin >> a >> b >> c >> d;
for(int i = a; i<=b; i++){
bool f=true;
for(int j=c; j<=d; j++){
if(IsPrime(i+j)) f = false;
}
if(f){
cout << "Takahashi" << endl;
return 0;
}
}
cout << "Aoki" << endl;
}