contest_20190209's Issues
06_gas_stationのgenerator実装
05_treeのtester解作成
06_gas_stationの想定解実装
一撃
問題文
射撃をします。
手前(F)と奥(B)にそれぞれN個の的が並んであり、あなたはそれぞれの的を撃ち抜くことでF_i, B_i点の点数が得られます。
あなたはとても射撃が上手なので、手前のi番目の的について奥の[i-K, i+K]の任意の的1つと同時に撃ち抜くことができます。
1発だけ打つとき得られる点数の最大値を出力せよ。
入力
N K
F_1 F_2 ... F_N
B_1 B_2 ... B_N
1 <= N <= 100000
0 <= K <= 100000
1 <= F_i <= 100000
1 <= B_i <= 100000
出力
max_score
サンプル
4 1
1 3 4 5
4 2 1 1
7
手前の2番めと奥の1番目の的を同時に撃ち抜くことで3+4点を獲得することができます。
05_treeの想定解実装
04_counting_shortest_pathの例を増やしてほしい
問題文に無向グラフとありますが、有向だと勘違いするとWAになるような例があったほうが親切かなと思いました。
1->3->2->4みたいな感じです。
各問題の配点を決める
下記の配点は順当でしょうか。
No. | 問題 | 配点 |
---|---|---|
1 | B式A+B | 100 |
2 | 集合写真 | 200 |
3 | 線香 | 300 |
4 | 最短経路 | 400 |
6 | ガソリンスタンド | 500 |
5 | 木 | 600 |
7 | 三角形 | 700 |
8 | 射的 | 800 |
07_path_on_triangleのgenerator実装
蛇状に折り返す文字列のmod5
このコンテストのハッシュタグは#yfkpo
である。
集合写真を撮影する際、K*Y人のコンテスタントは1行あたりK人の長方形に整列し、各人の位置に応じてハッシュタグの文字のポーズを行う。
最も左上の人を(y,x) = (1,1)として、奇数行目は右方向に、偶数行目は左方向に順番に'y', 'f', 'k', 'p', 'o'を割り当てていく。行を跨いでも割り当てる文字はリセットされない、つまりジグザグ状の道の上に'y', 'f', 'k', 'p', 'o'を割り当てる。
あなたはY行目X列目に立っている。行うべきポーズのアルファベット('y', 'f', 'k', 'p', 'o'のいずれか)を出力せよ。
入力
K
Y X
1 <= Y <= 100
1 <= X <= K <= 100
出力
サンプル
サンプル1
6
4 2
k
K=6の場合のY=4, X=2は'k'である。
yfkpoy
fyopkf
kpoyfk
pkfyop
サンプル2
2
3 2
y
K=2の場合のY=3, X=2は'k'である。
yf
pk
oy
08_one_shotのtester解作成
07_path_on_triangleの想定解実装
線香
問題文
燃える速度の異なるN本の線香に一斉に火をつけたところ、線香1が最初に燃え尽きた。
火をつける前の線香iの長さはS_iであり、線香1が燃え尽きた瞬間の線香i長さはT_iであった。
線香1の「単位時間あたりに燃える長さ」を1として、線香iの「単位時間あたりに燃える長さ」を既約分数で出力せよ。ただし分母が1になる場合は n 1
の形で出力せよ。
入力
N
S_1 S_2 ... S_N
T_1 T_2 ... T_N
2 <= N <= 100
1 <= S_1 <= 10000
T_1 = 0
i >= 2について1 <= T_i < S_i <= 10000
出力
各i(1<=i<=N)について分子_i 分母_i
の組を出力せよ
1 1
n_2 d_2
...
n_N d_N
サンプル
5
24 24 23 14 52
0 12 18 6 16
1 1
1 2
5 24
1 3
3 2
本番環境ですべての解をテストする
本番環境がどこかわかっていませんが(HackerRank?)、そこで想定解(想定誤答)を実行した際、想定通りのステータスになることを確認する
重ならない
一筆書きABC
問題文
正三角形ABCが与えられます。
マス(i, j)からは下記の図の隣接6マスに移動可能です。
(i-1, j-1) (i-1, j )
\ /
(i , j-1) <- (i , j ) -> (i , j+1)
/ \
(i+1, j ) (i+1, j+1)
同じマスを2回以上通らないようにA(0,0)->B(N-1, 0)->C(N-1, N-1)を移動するとき、最小のコストを求めよ。
※A,B,Cの3マスについて、コストが0であることが保証される。
入力
N
c_(0,0)
c_(1,0) c_(1,1)
...
c_(N-1,0) ... c(N-1,N-1)
制約
1 <= N <= 10^3
1 <= c <= 10
出力
文字列を一行で出力せよ。
末尾は改行せよ。
サンプル
sample 1
3
0
4 1
0 2 0
6
同じマスを2回通過せずにABCの順に結ぶ経路は下記の1通りであり、コストは4+2=6となります。
(0,0)->(1,0)->(2,0)->(2,1)->(2,2)
sample 2
5
0
9 1
9 1 9
1 5 1 1
0 1 1 9 0
12
06_gas_stationのtester解作成
04_counting_shortest_pathsのtester解作成
ある点から全ての点への距離の合計を求める
問題文
N頂点の0を根とした無向木が与えられる。各辺の長さは1である。
各頂点について、全ての頂点への距離の合計を出力せよ。
入力
N
p_1
p_2
...
p_n-1
ノード数Nに続いて、各頂点の親ノードが与えられる。
各iについてp_i < i
出力
d_0
d_1
...
d_N-1
各クエリの頂点からの距離の合計を各行で答えよ。
サンプル
サンプル1
3
0
1
3
2
3
入力は0-1-2
に対応する。
ノード0から各ノードへの距離の合計は1 + 2 = 3。
ノード1から各ノードへの距離の合計は1 + 1 = 2。
ノード2から各ノードへの距離の合計は2 + 1 = 3。
01_b_calcのtester解作成
07_path_on_triangleのtester解作成
08_one_shotの想定解実装
2次元座標で距離d以下の辺のみを使ったダイクストラの経路復元
問題文
N箇所のガソリンスタンドの座標が与えられます。ガソリンスタンド1からスタートして、ガソリンスタンドNに到着する経路を出力してください。
ただし、あなたの車は燃料を満タンに積んでも距離Dちょうどまでしか移動することができないため、距離Dより離れたガソリンスタンド間は直接移動することができません。
言い換えるとdistance(i,j) <= D
を満たすi,j間のみ移動が可能です。
また、同じガソリンスタンドを複数回使用することはできません。
※入力について、条件を満たす経路がただ1つだけ存在することが保証されます。
入力
N D
Y_1 X_1
Y_2 X_2
...
Y_N X_N
2 <= N <= 1000
0 <= D <= 100
0 <= Y <= 100000
0 <= Y <= 100000
Y,Xは非負整数。
サンプル
サンプル1
3 1
0 0
1 0
1 1
1
2
3
サンプル2
7 3
5 5
2 2
4 1
2 5
5 6
10 10
0 0
1
4
2
7
02_group_photoのtester解作成
03_incense_stickのtester解作成
04_counting_shortest_pathの出力が大きくなりうる。
制約がM <= 10^4の範囲内では、私が以前指摘した入力生成を用いることで、C++などの言語ではオーバーフローする入力を作ることができる。
次のうちのどちらかを検討してほしい
- 制約を変更し、M <= 10^3にする
- 答えの数値に制限を設け、これを問題文で明示する。
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.