yukicoder

問題 問題はこちら 問題文↓ N個の数字が与えられるので、これをK個のグループに振り分ける グループごとに平均を計算し, それらをもとに 最大の平均 - 最小の平均 を計算し、 最後に小数点以下を切り上げその値を「平均の差」と呼ぶ。 平均の差を最も大きくするようなグループ分けをしたとき、平均の差はいくつになるか答えよ。 解法 難しいことがごちゃごちゃ書いているが、 結局は{{最大の要素},{...},{...},{...},{最小の要素}}と分ければ必ず平均の差は最大の要素-最小の要素となり、 これが答えとなる #include <bits/stdc++.h> using namespace …

問題 問題はこちら 問題文↓ シーザ暗号の拡張版を思いつきました i文字目の文字をi回右にずらすという操作 すなわちヴィジュネル暗号みたいなことをしてください 解法 ASCIIコードに任せましょう 'A'-65=0 'B'-65=1 ... 'Z'-65=25のようになるので、それを全ての文字について行うだけです #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #…

問題 問題はこちら 問題内容↓ 最大L個のブロックが入る箱がある ブロックの塊があるからそれらの塊がいくつ入るかを調べてください 解法 ソートして小さいものから詰めましょう #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (…

yukicoder という有志作成の問題を解くコンテストに参加した。 今回は4時間の短時間 heuristic コンテストで、作問は E869120 さん。 問題 https://yukicoder.me/problems/no/5020 N (=45) 枚のカードの表裏に数字が書かれている。 2 枚のカードを選ぶと、表裏の数字のそれぞれを 2枚の平均に変化させる。 50 回以内の操作で 0 枚目のカードの表裏の値の両方をできるだけ 5 x 10^17 に近づけたい。 結果 39,532,303 点で 27 / 84 位とまずまず 解法 適当な貪欲法 (スコアが高くなるように 0 と何回か交換…

公式解説ではクエリを全て受け取ってから前処理をしていますが、オンラインで解くことができます。 問題のリンク 問題概要 文字列が $N$ 個与えられるので、以下のクエリを $Q$ 回処理 クエリ1 : 文字列 $x$ の末尾に英小文字 $c$を加える クエリ2 : $i=1,2,...,N$ に対して $S_{i}, S_{x}$ の最長共通接頭辞の長さを求め、それらの総和を答える。 クエリを先に受け取るときの解き方(ほぼ公式解説) 文字列の頭の部分が一緒といえば Trie木 です(?)。 Trie木についてはこれとかこれとかをみてみましょう。 今回は通常の Trie木 のノードごとにそのノード…

問題のリンク 解説が存在しなかったので、取り急ぎ雑ですが作りました。 問題概要 ヒヨコがオスメスそれぞれ $N$ 匹ずつ並んでいる。 オス同士、メス同士が区別できないとき、並べ方は $\binom{2N}{N}$ 通りあるが、このうち、オスとメスの匹数の差が $K$ 匹となる連続したヒヨコの区間を選ぶことができる並べ方は何通りか。 置き換え $P=(P_{1},P_{2},...,P_{2N})$ は、各要素が $+1$ $-1$ のどちらかであり、同数含んでいる。 長さ $2N$ の整数列 $S=(S_{1},S_{2},...,S_{2N})$ が $S_{i}=\sum_{j=1}^{i…

yukicoder.me まずは二つのコードを AC N,Q = map(int,input().split()) switch = [0]*(N) ans = 0 for i in range(Q): L,R = map(int,input().split()) for j in range(L-1,R): if switch[j] == 0: switch[j] = 1 ans += 1 else: switch[j] = 0 ans -= 1 print(ans) TLE N,Q = map(int,input().split()) switch = [0]*(N) for i in r…