急に問題を作ってみたかったから問題を作ったよ！
解いてくれて嬉しいから解説記事を作るよ！
2020/03/23に自作の問題でコンテストを開きました。
Programming problems and Competitions :: HackerRank
Testerもいない激ヤバ不安定な問題に取り組んでいた方々にはとても感謝しています！
ありがとうございます！
全完者がいて、僕、満足！
まだ解いてない方は解いてみてくれると嬉しいです。
Solve Contestっぽいの！ Questions | Contests | HackerRank
こっから解説していきます。
解説の前に
使用するテンプレートはこの辺です。
以降solve関数だけ載せます。
ちなみにsolve()は僕が答えのテストケース生成に使用したコードです。くっそ汚いこともあるから許して。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main() {
solve();
return 0;
}
|
200点 isBigger?
元ネタ: なし
isBigger? | Contestっぽいの！ Question | Contests | HackerRank
取りうる値の幅が広いのが問題点です。
$a$,$b$は明らかにstringで持つべきです。
ここで、$a$,$b$について、$a < b$が成り立つ場合について考えていきます。
a,bの符号が一致していない場合
$b$が正,$a$が負ならYesです。そうで無い場合はNoになるでしょう。
$a$,$b$の符号が一致しているかどうかは$a$,$b$の先頭の文字を見れば良いです。
一致している場合は下に移ります。
a,bの桁数が一致していない場合。
a,bが両方とも正でbの方が桁数が多いならYesです。
両方とも負ならbの方が桁数多い場合Noです。
桁数が一致している場合はもう前から1文字ずつ比較していくしかありません。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
void solve() {
string a,b;
cin >> a >> b;
bool isRev = false;
if (a[0]=='-' && b[0] != '-') {
cout << "Yes" << endl;
return;
}
if (a[0]!='-' && b[0] == '-') {
cout << "No" << endl;
return;
}
if(a[0]=='-' && b[0] == '-') isRev = true;
if (a.size() < b.size()) {
cout << (isRev ? "No" : "Yes") << endl;
return;
}
if (a.size() > b.size()) {
cout << (isRev ? "Yes" : "No") << endl;
return;
}
REP(i,a.size()) {
if(a[i]!=b[i]) {
if (a[i] < b[i]) {
cout << (isRev ? "No" : "Yes") << endl;
return;
}
if (a[i] > b[i]) {
cout << (isRev ? "Yes" : "No") << endl;
return;
}
}
}
cout << "No" << endl;
}
|
(tunehiraさんの提出見たらPythonで楽々突破されてた。悔しい。)
200点 Tower of Heaven
Tower of Heaven | Contestっぽいの！ Question | Contests | HackerRank
元ネタ: Tower of Heaven (天国の塔) - Official Site | Askiisoft
制約が非常に弱いので割と何でも解けると思います。
試練として消える文字をsetに格納し、１階ごとに行われる名前の出力に対し、その文字はsetに入っているか？を確認すれば良いと思います。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void solve() {
string S;
int N;
cin >> S >> N;
set<char> used;
REP(i,N) {
char c;
cin >> c;
used.insert(c);
for(const auto &it: S) if(used.count(it)==0) cout << it;
cout << endl;
}
}
|
200点 Rank Up!
Rank Up! | Contestっぽいの！ Question | Contests | HackerRank
元ネタ: なし
サンプルが分かりにくいのでもう少しまともな値で考えてみます。
N = 9999ならX = 1です。
N = 9990 なら X = 10 です。
N = 999 なら X = 1です。
ここで、値nに対する、問題の答えを$x_n$とします
$ x_{10*n} = 10 * x_n $ が成り立ちます。
このことを利用すると、Nの最後の桁が0の場合,一旦それを除いて、あとで答えを10倍すれば良いことが分かります。
これは今気づいた解き方なのでテストケース生成時のコードはもっと汚いです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void solve() {
string N;
cin >> N;
string ans;
bool flg = false;
REPR(i,N.size()-1) {
if (!flg) {
if (N[i] == '0') {
ans.insert(ans.begin(),'0');
continue;
}
int n = N[i] - '0';
ans.insert(ans.begin(),(char)(10-n+'0'));
flg = true;
continue;
}
int n = N[i] - '0';
ans.insert(ans.begin(),(char)(9-n+'0'));
}
cout << ans << endl;
}
|
tunehiraさんのコードが非常に美しくて良いのでこっちをみた方がいいと思います。
1
2
3
4
5
6
7
|
N = int(input())
a = 1
n = N
while n:
a *= 10
n//=10
print(a-N)
|
400点 Absolute victory.
Absolute victory. | Contestっぽいの！ Question | Contests | HackerRank
元ネタ: なし
Union-Findしてくれと言わんばかりの問題です。
実装がとても綺麗なので僕はうしさんのライブラリを使ってます。。。。
素集合データ構造(Union-Find) | Luzhiled’s memo
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void solve() {
int N,F;
cin >> N >> F;
UnionFind uf(N+1);
REP(_,F) {
int a,b;
cin >> a >> b;
uf.unite(a,b);
}
int ans = 1;
REP(i,N+1) chmax(ans,uf.size(i));
cout << ans << endl;
}
|
500点 Deep in Abyss
Deep in Abyss | Contestっぽいの！ Question | Contests | HackerRank
元ネタ: Amazon.co.jp: メイドインアビスを観る | Prime Video
この問題をシャワー浴びているときに思いついたのでこのコンテストが生まれました。
ちなみに問題名はメイドインアビスのOPテーマです。
ぱっと見では難しいので、もっと簡単な問題に分割することを考えます。
- $i$層に残体力$h$で到達した時の危険度の最小値は？
この様にするとDPで解けることが分かります。
遷移式は$dp[<今いる層>][<残体力>] = <取りうる危険度の最小値>$として、
$dp[N][H] = 0$ で初期化します。
後はこの二つの遷移式があることが分かります。
$ dp[i][j] = min(dp[i][j-1] + f_i, dp[i][j] )$
$ dp[i][j] = min(dp[i+1],[j+d_i],dp[i][j]) $
が上げられます。後は境界に注意して解けば$\mathcal{O}_(HN)$ぐらいで解けると思います。
答えは$min(dp[0][1..H])$です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
void solve() {
int H,N,F;
cin >> H >> N >> F;
vector<int> damage(N+1,0),danger(N+1,0);
REP(i,N) cin >> damage[i+1] >> danger[i+1];
if(H==1) {
cout << -1 << endl;
return;
}
vector<vector<int>> dp(N+1,vector<int>(H+1,INF));
dp[N][H] = 0;
REPR(i,N) {
FOR(j,2,H+1) {
chmin(dp[i][j],dp[i][j-1]+danger[i]);
}
FOR(j,2,H+1) {
if(i!=0) chmin(dp[i-1][max(0,j-damage[i])],dp[i][j]);
}
}
int ans = INF;
FOR(i,1,H+1) chmin(ans,dp[0][i]);
cout << ((ans < F) ? ans : -1) << endl;
}
|
作問した感想。
楽しかった！(小並感)
でも5問もちゃんとした問題作るのは相当に難しいことなんだなって・・・
後本当に参加してくれてありがとうございました！！！