ゆるふわ競技プログラミングオンサイト at FORCIA

#3 writer料は初任給に含まれます　解説

コンテストページ

Div. 1: https://www.hackerrank.com/yfkpo3-1

Div. 2: https://www.hackerrank.com/yfkpo3-2

問題一覧 (Div 1)

問題一覧 (Div 2)

Yurufuwa Division

writer: tempura0224

問題概要

・レーティングが X 未満ならDiv. 2、X 以上ならDiv. 1 に参加する。

・レーティングが A の人はどちらに参加する？

​

考察

・XとAを受け取って AがX未満なら2, そうでないなら1を出力すればよい

・ということでPythonで書くとこう

　　X, A = map(int,input().split())

　　if A < X : print(2)

　　else : print(1)

​

​

​

統計

・AC率(AC数/提出数)

　　57/64 (89%)

・FA

　　全体 :bayashiko(0:55)

　　オンサイト :bayashiko(0:55)

Coupons

writer: Noimin

問題概要

・割引金額が決まっているクーポンを N 枚持っている

・P 円のピザは最安何円で買える？

・使えるクーポンは高々1枚で，払う金額が負になるクーポンは使えない

​

考察

・N 枚のクーポンを1枚ずつ見ていけばよい

・割引額 c_i が P 円を超えるクーポンは無視

・P円以下の場合は P - c_i で実際に払う金額を求め，最小値を取る

・すべてのクーポンについて c_i > P が成り立つ場合に注意 (答えは P 円になる)

実装例 (Python)

n, p = map(int, input().split())

c = tuple(map(int, input().split()))

ans = p

for ci in c:

if ci <= p:

ans = min(p-ci, ans)

print(ans)

​

統計

・AC率(AC数/提出数)

　　44/69 (64%)

・FA

　　全体 : otamay (3:07)

　　オンサイト : bayashiko (3:23)

New Comers

writer: tempura0224

問題概要

・第1回〜第3回の参加者名簿が与えられる

・第3回が初参加な人は何人いる？

・各回の参加者の人数<=50000

​

想定TLE解

・第3回の参加者を1人1人見ていって、第1回にも第2回にも参加していなければ

　初参加

・「第3回の参加者それぞれについて、第1回、第2回の参加者を順に見て

　同じ名前の参加者がいたらだめ」というコードを書くと、

　最悪ケースで1人調べるごとに10万人と比較しないといけないのでTLE

​

想定解

・setを使いましょう。

　- 要素の挿入、削除、検索などが高速にできるデータ構造

・第1回、第2回参加者のsetを用意して、第3回の参加者がどちらのsetにも入って

　いなければ初参加。

・これでO(NlogN)とかO(N)とかになって間に合う。

実装例

A, B, C = map(int,input().split())

First = set(input().split())

Second = set(input().split())

Third = list(input().split())

ans = 0

for p in Third :

　if p not in First and p not in Second : ans += 1

print(ans)

​

統計

・AC率(AC数/提出数)

　　Div. 1　　91/103 (88%)　　

・FA

　　Div. 1

　　全体 :kotamanegi(1:06)

　　オンサイト :n_fuppy(1:14)

​

　Div. 2　　45/50 (90%)　　　　　

​

　Div. 2

　全体 :otamay(5:22)

　オンサイト :CKPCKP(6:23)

​

Books Rotation

writer: Noimin

問題概要

・H×W の行列が与えられる

・次の操作を何回でもできる: ある列を選び，その列の各要素を1個下に移動させる。ただし一番下の要素は一番上に移動させる

​

​

・各行に同じ数字が揃うようにできるか？

​

考察 1

・以降，解説の都合上 0-indexed で考えます

・各列 H 回操作をすれば元に戻る

​

​

・0列目以外のすべての列について，(H-1) 回以下の操作で 0列目と同じになるか？ を試せばよい

​

​

​

考察 2

・x 回操作をすると元々 i 行目にいた要素は (i+x) % h 行目に動く

・つまり， i 行 j 列の値を (i+x) % h 行 0 列の値と比較すればチェックできる

​

​

・ 操作する列 ((W-1)列のどれか) と操作回数(最大 (H-1) 回) を決めたとき，　　　「0列目と同じになるか？」の判定が O(H) なので，全体では O(H^2 W)

・ H,W <= 100 なので間に合う

1 列目を操作

実装例 (Python)

(入力略)

yes = True

for j in range(1, w): # 何列目を操作するか

is_same = False

for x in range(h): # 何回操作するか

is_same = True

for i in range(h): # 0列目と揃っているかどうかのチェック

if a[(i+x)%h][0] != a[i][j]: is_same = False

if is_same: break

if not is_same: yes = False

print(“Yes” if yes else “No”)

統計

・AC率(AC数/提出数)

　　43/59 (73%)

・FA

　　全体 : otamay(10:40)

　　オンサイト : shiro53(14:17)

Median Permutation

writer: Noimin

問題概要

次の3条件を満たす数列の数を 10^9+7 で割った余りを答える。

・要素数は N

・1 から N までの数が1回ずつ使われる

・奇数番目の要素はそれまでの要素すべての中央値になっている

条件を満たす数列の例: N = 5 における 5, 1, 4, 2, 3

考察 1

・奇数番目の要素については，後ろの要素になればなるほど条件が厳しい

→ 後ろから埋めることを考えてみよう！

例: N = 5 のとき

​

i = 5 の要素は数列全体の中央値でなければならない

→ 3 しか入らない

i = 4 の要素は偶数番目なのでなんでもよい

考察 2

例: N = 5 のとき

​

i = 2 の要素は偶数番目なのでなんでもよい

​

i = 1 の要素は i = 1 の中央値でなければならない

→まだ使っていない 5 を入れる

i = 3 の要素は i = 1, 2, 3 の中央値でなければならない

→ まだ使っていない 1, 4, 5 の中央値である 4 が入る

考察 3

・ i 番目の要素を選ぶときの選択肢の数

・ i が奇数 → 1 個 (今残っている数が何かで決まる)

・ i が偶数 → i 個 (今残っている数のうちなんでもよい)

・したがって求めるべき数列の数は

・ N が奇数 → (N-1) × (N-3) × … × 4 × 2 = (N-1)!!

・ N が偶数 → N × (N-2) × … × 4 × 2 = N!!

統計

・AC率(AC数/提出数)

　　Div. 1　　83/94 (88%)　　

・FA

　　Div. 1

　　全体 : e869120(3:28)

　　オンサイト : e869120(3:28)

​

　Div. 2　　24/28 (86%)　　　　　

​

　Div. 2

　全体 : y_homma46(26:37)

　オンサイト : CKPCKP(29:59)

​

Bananas Multiplier

writer: Noimin

問題概要

・N 頂点の木 (Bananas Multiplier) が与えられる

・各辺は重みがついていて，その辺を通るとバナナの数がその重み倍に増える

・頂点 m_t にバナナを x_t 本置き，頂点 p_t で回収するとき，回収できるバナナの本数を 10^9+7 で割った余りは？

​

m_t = 3, p_t = 2, x_t = 2 の

場合

考察1 (Easy)

・要するに，x_t × (m_t から p_t に向かうパスに含まれる辺の重みの積) を計算したい

・m_t から p_t に向かうパスは BFS (or DFS) で求められる

・頂点数もクエリ数も 10^3 以下なので間に合う

​

考察2 (Hard)

・頂点数・クエリ数はともに 10^5 以下なので，BFS (or DFS) では TLE

・クエリのたびに BFS (DFS) を回さずに済む方法はないか？

・頂点m_t, p_t に対して，m_t と p_t をともに子孫としてもち，かつ　　根から最も遠いノード v_t を求めることができる

・

・ Lowest Common Ancestor (LCA) という

・ダブリングなどを使えば前処理 O(N log N) ・クエリ O(log N) で求めることができる

考察3 (Hard)

・LCA が分かれば，各頂点について「根からその頂点にたどり着くまでに通る辺の重みの積」をあらかじめ求めておくことで

x_t × (m_t から p_t に向かうパスに含まれる辺の重みの積) を

x_t × として

求めることができる

(根から m_t までの重みの積) × (根から p_t までの重みの積)

(根から v_t までの重みの積)²

考察4 (Hard)

・時間計算量は，

・各頂点についてそこまでの重みの積を求める前計算で O(N)

・LCA を求めるための前計算で O(N log N)

・1つのクエリの計算で O(log N)

なので，全体で O(N log N + Q log N)

​

統計

・AC率(AC数/提出数)

　　Div. 1　(hard)　78/128 (61%)

　　　　　 (easy)　80/120 (67%)

・FA

　　Div. 1

　　全体 : hitonanode(9:19)

　　オンサイト : e869120(12:49)

​

　Div. 2　(hard)　10/28 (36%)

　　　　 (easy)　27/48 (56%)　　　　　

　Div. 2

　全体 : otamay(27:44)

　オンサイト : shiro53(50:52)

​

Banana Game

writer: tempura0224

問題概要

N個の袋に激辛バナナと普通のバナナが入っている。

2人でゲームをする。以下の操作を交互に行う。

・N個の袋から1つを選んでその中から好きな本数のバナナを取り出して食べる。

　ただし激辛バナナは 1 本まで

操作ができなくなった方が負け。勝つのは先手？後手？

​

考察1

・見るからにNimっぽいルール(というか激辛バナナがなければNimと完全に同じ

　ルール)

・ということで Grundy 数を求めてみる

・Grundy数...その局面から移動できる局面のGrundy数の集合をGとしたとき、

　Gに含まれない最小の非負整数

​

​

考察2

実際に計算してみるとこんな感じ

規則性を見つけると

・青色部分(普通>=激辛)では

　Grundy数 = 辛 + 普

・白色部分(普通<激辛)では

　Grundy数 = 2 * 普 + (0,1 繰り返し)

考察3

・前のページの式が一般に正しいことは帰納法などで証明できるので、無事　

　Grundy数を求めることができた

・各袋のGrundy数のxorを求めて0なら後手の勝ち、非0なら先手の勝ち

統計

・AC率(AC数/提出数)

　　50/132 (38%)

・FA

　　全体 :sugarrr(19:39)

　　オンサイト :e869120(21:17)

Sweets Distribution

writer: tempura0224

問題概要(easy)

・N個のお菓子が1列に並んでいる。

・matsu, prd, tempura, Noimin が食べたときの美味しさは、順にAi, Bi, Ci, Di

・左から1〜i番目をmatsu, 左からi+1〜j番目をprd, 左からj+1〜k番目をtempura, 　左からk+1〜N番目をNoimin が食べたときの美味しさの合計をf(i,j,k)と表す

・f(i,j,k)の最大値は？

考察1

・matsu, prd, tempura, Noimin を順に人1, 2, 3, 4と呼ぶことにします。

・DPできるよ！

・具体的には dp[i][j] = 1〜i 番目までのお菓子について、i番目を人jが食べると

　したときの美味しさの合計のmax

・求めるものはdp[n][4]

考察2

・遷移はこんな感じ

　　dp[i+1][1] = dp[i][1] + A[i+1]

　　dp[i+1][2] = max(dp[i][2], dp[i][1]) + B[i+1]

　　dp[i+1][3] = max(dp[i][3], dp[i][2]) + C[i+1]

　　dp[i+1][4] = max(dp[i][4], dp[i][3]) + D[i+1]

​

問題概要(hard)

・easy に swap クエリを足したもの

・Q回以下のクエリを処理する。

　 l 番目と r 番目のお菓子の場所を入れ替えて、f(i,j,k) の max を求める

考察1

・Q は最大 20000 なので、毎回easyと同じDPをしていると間に合わない。

　各クエリに高速に答える必要がある。

​

​

考察2

・セグ木に乗るよ！！！！

・Segment Tree の各ノードに

　a[i][j] = そのノードの左端のお菓子を人i、右端を人j が食べるときの美味しさの

　和の最大値(1<=i<=j<=4)

　を載せる

考察3

・ノードとノードのマージは

　　a[i][j] = max( max(i<=k<=j) (al[i][k]+ar[k][j]) , max(i<=k<j) (al[i][k]+ar[k+1][j]) )

　みたいな感じでできる。

・l 番目と r 番目の交換は 1 点更新を 2 回と思えばいい。

考察4

・結局更新も答えを求めるのも O(logN * K ) でできる(Kはノードのマージ1回の

　計算量、だいたい30くらい)

・よって、全体の計算量は O(N*K + Q*K*logN)

・最初のセグ木の構築はO(N*K)でやりましょう(O(N*K*logN)だと間に合わない

　可能性が高いです。)

​

統計

・AC率(AC数/提出数)

　　Div. 1　(hard)　18/54 (33%)

　　　　　 (easy)　71/97 (73%)

・FA

　　Div. 1 (hard)

　　全体 :noshi91(29:04)

　　オンサイト :e869120(35:51)

​

　Div. 2　(hard)　--/-- (-- % )

　　　　 (easy)　8/14 (57%)　　　　　

　Div. 2 (easy)

　全体 :CKPCKP(57:32)

　オンサイト : CKPCKP(57:32)

​

Yet Another Cake Distribution

writer : tempura0224

問題概要

・ケーキを4人で切り分ける

・上、下、左、右 みたいな感じで分けたい。

・切り分け方は何通り？

解説書くの飽きた

( 02 / 29 04 : 24 )

この絵から察してください。

統計

・AC率(AC数/提出数)

　　3/5 (60%)

・FA

　　全体 :Nyaan(78:39)

　　オンサイト : --- (--:--)

Digit Sum Multiple

writer: tempura0224

問題概要

・以下の条件をすべてみたす正の整数Nを見つけろ。

　1. どの桁も0でない。

　2. 各桁の和をS(N)とするとNはS(N)で割り切れる。

　3. ちょうどM桁である。

​

考察1

S(N)を決めて桁和がS(N)になるM桁の整数を探すことにしよう

S(N)をいくつにするのが簡単か？

・素数？

・合成数？

考察2

結論からいうと 2べきにするのが簡単だと思います。

理由：

例えば、10000 = 10^4 の倍数は 2^4 の倍数である。

つまり、下4桁さえ16の倍数に調整してしまえば、それ以外はいくつにしても絶対16の倍数になってくれる。

​

考察3

よって、2^x が M より少し大きめになるくらいのxを取り、

(残りのM-x桁は和が2^xになるように適当に調整)(下x桁はx桁の2^xの倍数)

でM桁の整数をつくればOK

​

残る問題はx桁でどの桁も0でないような2^xの倍数が見つかるかどうか

​

考察4

あります！！！

11211111212122112は

k=1〜17について、下k桁が2^k の倍数であるような整数

2^17 = 131072 > 100000 なので今回の制約ではこれで十分(実は任意のnについてn桁でどの桁も1または2である2^nの倍数が存在することが証明できます)

まとめ

結局以下のように構成すればOK

M<=2 → 適当に埋め込み(下の方法だとちょっとバグるので)

それ以外→2^x が M より少し大きめになるくらいのxを取り、

(残りのM-x桁で和が2^xになるように調整)(11211111212122112の下x桁)

​

統計

・AC率(AC数/提出数)

　　13/49 (27%)

・FA

　　全体 :yosupo(25:12)

　　オンサイト :e869120(55:20)

🏅表彰🏅