0w1

Yuki

Yuki 514 宝探し3 ( Ad hoc, Interactive )

No.514 宝探し3 - yukicoder題意: 在一個 1e9 * 1e9 的平面上,有個座標藏著寶藏。你每次可以問一個點和寶藏的曼哈頓距離是多少。請在兩次以內的詢問找到寶藏位置。解法: 問 ( 0, 0 ) 得距離 A,接著問 ( 0, A ) 得距離 B,那麼寶藏一定在 ( B / 2, A - B…

Yuki 470 Inverse S+T Problem ( 2SAT, Dummy Constraints )

No.470 Inverse S+T Problem - yukicoder題意: 給定 N 個長度為三的字串,求一種分割,使得每個字串被分為兩個非空子字串,且不存在重複的字串。制約: N ≤ 1e5 sigma: { 'a'~'z', 'A'~'Z' }解法: 注意到當 N > | sigma | 時,一定無解,所以 N 可以視作 ≤…

Yuki 230 Splarraay スプラレェーイ ( bitset )

No.230 Splarraay スプラレェーイ - yukicoder題意: 初始時有一個長度為 N 的陣列。現在 a, b 兩人玩遊戲,有 Q 個操作依序被進行,第 i 個操作可以用 ( x[ i ], l[ i ], r[ i ] ) 描述: x = 0 : 令 ca 為 arr[ l, r ] 中 a 塗色數,cb 為 arr[ l, r ] 中 b 塗色…

Yuki 162 8020運動 ( DP )

No.162 8020運動 - yukicoder題意: 你上下各有一排 14 個連續的牙齒。 你現在 A 歲,你想知道你在 80 歲時,期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法: 考慮動態規劃: dp[ i ][ j ][ k ] : 經過 i …

Yuki 361 門松ゲーム2 ( SG, Game Theory )

No.361 門松ゲーム2 - yukicoder題意: 一開始有一個長度 L 單位的棒子。輪流操作,操作要選擇一個棒子,砍成三個不同長度的棒子,令這三個棒子的長度為 L1, L2, L3,則必須滿足: max( L1, L2, L3 ) - min( L1, L2, L3 ) ≤ D 先不能操作的人輸,問誰贏。制…

Yuki 421 しろくろチョコレート ( Greedy, Maximum Bipartite Matching )

No.421 しろくろチョコレート - yukicoder題意: 有一個 N * M 的黑白交接的棋盤巧克力。有些已經被吃掉了,用 '.' 表示。你每吃一片 1 * 2 的巧克力會得到幸福值 100,每吃不相鄰的一塊黑色和一塊白色會得到幸福值 10,隨便吃一塊會得到幸福值 1,問最大幸…

Yuki 409 ダイエット ( Decision Monotonous, DP )

No.409 ダイエット - yukicoder題意: 有 N 天,第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位,你想減肥,所以每天你可以選擇吃或不吃。如果吃了,你的體重就會增加吃掉的重量並歸零壓力值,否則你會減去 A 單位的重量但同時增加一個單…

Yuki 377 背景パターン ( Burnside Lemma, Math )

No.377 背景パターン - yukicoder題意: H * W 格子的壁紙,每個格子有 K 種顏色中一種。這個壁紙由無窮左到無窮右不重疊貼滿,無窮下方至無窮下方也一樣。問牆壁的圖案有多少種,對 1e9 + 7 取模。兩個牆壁的圖案相同若且唯若同時存在相同一個 H * W 的圖案…

Yuki 489 株に挑戦 ( Sliding Window )

No.489 株に挑戦 - yukicoder題意: 買賣股票,買跟麥只做一次。必須滿足買的日期 i 和賣的日期 j 有 j - i 制約: 2 ≤ N ≤ 1e5 1 ≤ D 1 ≤ K ≤ 1e6 1 ≤ xi ≤ 1e6解法: 努力寫了一次線段樹,但 python 也很給力的 TLE 了。 經典的滑動視窗: window[ i ]: i …

Yuki 497 入れ子の箱 ( DP )

No.497 入れ子の箱 - yukicoder題意: 給 N 個箱子,用三維各自的長度描述。一個箱子 i 容得下另一個箱子 j 若且唯若 X[ i ] > X[ j ] and Y[ i ] > Y[ j ] and Z[ i ] > Z[ j ]。問最多可以形成多少幾層的箱子。制約: 1≤N≤1000 1≤Xi,Yi,Zi解法: 依最小的…

Yuki 502 階乗を計算するだけ ( Offline )

No.502 階乗を計算するだけ - yukicoder題意: 給 n,求 X: X = n! mod (1e9+7)制約: 0 ≤ n ≤ 1e18解法: 首先 n ≥ 1e9 + 7 時,X 顯然為 0。 本地建表,將 1e7 的倍數都填上去,那麼計算量便是至多 1e7。 MOD = int( 1e9 + 7 ) ''' Used for offline prep…

Yuki 496 ワープクリスタル (給料日前編) ( DP )

No.496 ワープクリスタル (給料日前編) - yukicoder題意: 你有 N 顆一次性的魔法石頭,第 i 顆可以幫你在 X 軸上 + X[ i ],Y 軸上 + Y[ i ],但花費魔力 C[ i ]。你現在在 ( 0, 0 ),你的目的地是 ( Gx, Gy )。另外一種移動方式是向上或向右一格,花費 F。…

Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )

No.491 10^9+1と回文 - yukicoder題意: 給 N,問有幾個數字不超過 N,是 1e9 + 1 的倍數,並且是迴文。制約: N ≤ 1e18解法: 怒猜超過 1e9 之後不會有迴文了。( 求證明 ) 所以要求的其實是 1e9 以下的迴文數。 因為是迴文,所以只要枚舉左半邊,也就是大約…

Yuki 243 出席番号(2) ( DP, Inclusion Exclusion )

No.243 出席番号(2) - yukicoder題意: 有 N 位可分別的學生,現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數,對 1e9 + 7 取模。資料規模: 生徒の数Nが最初の行で与えられる。1≤N≤500…

Yuki 242 ビンゴゲーム ( Expectation, Math )

No.242 ビンゴゲーム - yukicoder題意: 在 5 * 5 的矩陣玩賓果 ( 縱橫斜連線 ),每個格子都不重複存在一個介於 1 ~ 99 之間的一個整數。求矩陣裡的格子裡的數字都完全隨機,叫出的號碼也都完全隨機的情況下,喊到第 N 個數時,期望有多少連線。資料規模: 1…

Yuki 210 探し物はどこですか? ( Expectation, Priority Queue )

No.210 探し物はどこですか? - yukicoder題意: 有若干個房間,我們想找到一個藏在某處的寶物,而每個房間有寶物的機率為 P / 1000,如果該房間確實有寶物,則每次檢查這個房間會找到寶物的機率為 Q / 100。求最佳檢查順序下,能找到寶物的最小期望檢查次數…

Yuki 412 花火大会 ( DP )

No.412 花火大会 - yukicoder題意: 有三個人分別要 R[ 0 ], R[ 1 ], R[ 2 ] 以上面積的一塊布料。現在有若干個布料,求有多少種帶布料的方法,能滿足三個人的需要。資料規模: 布料數 1≤N≤30 布料大小 1≤Ei≤100 時限 2000 ms 記憶體 512 MB解法: 想省去討…

Yuki 320 眠れない夜に ( Math, Fibonacci )

No.320 眠れない夜に - yukicoderかなりフィボナッチ数列の勉強になったので、ちょっとノートをします。pekempey さんの記事を参考にしました。ある項目に 1 少なく数えるのは、その項目から と負のフィボナッチ数列を並列して進ませる事と同じで、縦の総和…

Yuki 416 旅行会社 ( Union Find, Smaller to Larger, Time Reverse )

No.416 旅行会社 - yukicoder題意: 給一個圖,和破壞邊的順序 ( 不一定會將所有橋破壞 )。對於所有大於 0 的節點,求哪一次破壞後無法從 0 達到。若一開始就不能到達,輸出 0,若破壞完依然能到達,輸出 -1。資料規模: 節點數 2≤N≤1e5 初始橋的數量 1≤M≤2e…

Yuki 389 ロジックパズルの組み合わせ ( Combinatorics, Math )

No.389 ロジックパズルの組み合わせ - yukicoder題意: 在一排 M 個格子上放黑色點,依序為 H[ 0 ], H[ 1 ] .. H[ N ] 個連續的黑色點,且兩兩以至少一個的連續白色點區隔。求模 1e9 + 7 後的方案數。資料規模: 1 ≤ M 0 ≤ H[ i ] SIGMA{ H } ≤ M 保證若有一…

Yuki 318 学学学学学 ( Ad hoc / Segment Tree )

No.318 学学学学学 - yukicoder題意: 給一個數列 A。現在要產生另一個數列 B。產生的步驟為: for each integer t in 1 to 1e9: __for each integer x in leftmostPositionInA( t ) to rightmostPositionInA( t ): ____B[ x ] = t 求 B 的最終樣貌資料規模…

Yuki 403 2^2^2 ( Fast Multiplication, Math, Little Fermat's Theorem )

No.403 2^2^2 - yukicoder自分が pow() の中に普段書いてる res = 1 は間違ってるみたですね。0^n = 0, for all n > 0 ですから。 const int MOD7 = ( int ) 1e9 + 7; ll A, B, C; void init(){ scanf( "%lld^%lld^%lld", &A, &B, &C ); } ll ll_pow( ll v, …

Yuki 34 砂漠の行商人 ( Dummy Constraints )

No.34 砂漠の行商人 - yukicoder最悪の場合は通る砂漠のレベルが全部最高である 9のとき。この場合は遠回りはいらないのでマンハッタン距離を考えて、体力は精々 N * 2 * 9 で十分だと分くる。 int N, V, Sx, Sy, Gx, Gy; vvi LV; void init(){ cin >> N >> …

Yuki 241 出席番号(1) ( Random )

No.241 出席番号(1) - yukicoder題意: 每個人有 [ 0, N - 1 ] 的整數中獨特的一個編號,且都有一個不喜歡的座位號碼。現在要將 [ 0, N - 1 ] 的整數分配給他們做為座位號碼。求一組方案,使得每個人都不坐在自己討厭的座位號碼上。資料規模: 人數 1≤N≤50 …

CFR 742 E. Arpa’s overnight party and Mehrdad’s silent entering ( Bicoloring / Random )

Problem - E - Codeforces題意: 在一個圓桌上吃飯,有兩種飯,希望每連續三個人,都一定有一個人吃不一樣的東西。每個人都有一個唯一對應的伴侶,而伴侶之間也規定不能吃一樣的東西。求合法分配的結果。若無法分配,輸出 -1。資料規模: 情侶對數 1 ≤ n ≤ 1…

Yuki 413 +5,000,000pts ( Double precision, Hack )

http://yukicoder.me/problems/no/413double って勝手に近い方に丸めちゃうんですね... 例えば a.99999.. だと、整数にキャストする際 a + 1 になるようだ void solve(){ for( int i = ( int ) 1e8; i < ( int ) 1e8 + 1e5; ++i ) cout << 1LL * i * i + i -…

Yuki 37 遊園地のアトラクション ( DP )

No.37 遊園地のアトラクション - yukicoder題意: 有若干個遊樂設施,用排隊時間和娛樂程度描述。初始有 T 單位的時間,同一個設施每玩一次,娛樂程度便會減半並向下取整。求在時間內能造成的最大的娛樂值。資料規模: 初始時間 1≤T≤10000 娛樂設施數目 1≤N≤…

Yuki 202 1円玉投げ ( Bucket )

No.202 1円玉投げ - yukicoder題意: 丟半徑 10 的銅板。每次丟完後,若剛好這個硬幣落在另一個已在地上的硬幣,換句話說重疊,就立刻取回這個硬幣,否則留在原地。求最終有多少硬幣在地上。資料規模: 銅板數 1 ≤ N ≤ 1e5 銅板圓心座標 0 ≤ X[ i ], Y[ i ] …

Yuki 96 圏外です。( Union Find, Bucket, Furthest Pair, Convex Hull )

No.96 圏外です。 - yukicoder題意: 兩個人各拿著一台無線電要通話,無線電之間最遠可通話距離為 1 km,基地台之間則是 10 km,無線電與基地台之間則是 1 km。在兩人可通話的前提下求最大可能的歐幾里德距離。資料規模: 基地台數量 0≤N≤120000 基地台座標 …

Yuki 75 回数の期待値の問題 ( DP, Gauss Seidel )

No.75 回数の期待値の問題 - yukicoder 古寺いろはのサブミ見て勉強になった。 漸化式が状態を互いに参照しまわりそうで DAG になれそうにない時は連立方程式に書き換えてとけばいいことですが、もっと簡単な方法で近似値が求められる。その方法とはただ愚直…

Yuki 152 貯金箱の消失 ( Triangle, Math )

No.152 貯金箱の消失 - yukicoder 直角三角形の辺はそれぞれ x * x + y * y, x * x - y * y, 2 * x * y と表せる。 総和をとると、2 * x * x + 2 * x * y ≤ L が問題の核心だと分かる。 ここで x, y を枚挙。 #include <bits/stdc++.h> using namespace std; signed main(){</bits/stdc++.h>…

Yuki 87 Advent Calendar Problem ( Periodic )

No.87 Advent Calendar Problem - yukicoder 閏年じゃない場合は 365 日で、365 % 7 = 1 日だけ、前の年の同じ日に対応する曜日がずれる ( 増える )。閏年だと 2 日ずれ、循環する周期を探す意味で計算してみると、その周期は 400 年だと分かる。 #include <bits/stdc++.h> </bits/stdc++.h>…

Yuki 351 市松スライドパズル ( Time Reverse )

No.351 市松スライドパズル - yukicoder 最後の盤面から最初の位置を辿ればいい。その最初の位置を知れば、対応する色も当然に一意に定まる。 #include <bits/stdc++.h> using namespace std; const string msg[] = { "white", "black" }; signed main(){ int H, W; cin >> </bits/stdc++.h>…

Yuki 171 スワップ文字列(Med) ( DP )

No.171 スワップ文字列(Med) - yukicoder 排列の公式使って S.size() ! / PI{ cnt[ i ] ! | 'A' ≤ i ≤ 'Z' } と行きたいんですが、MOD が素数でないため、割り算はキツイ ですが組み合わせの公式で書き換えれば C( S.size(), cnt[ 'A' ] ) * C( S.size() - c…

Yuki 53 悪の漸化式 ( 特性方程式, 精度, Math )

No.53 悪の漸化式 - yukicoder 高校数学は忘れないでおきましょう yukicoder No.53 - 悪の漸化式(writer担当) - ゲームにっき(仮)別館(仮) #include <bits/stdc++.h> using namespace std; signed main(){ int N; cin >> N; cout << fixed << setprecision( 10 ) << 4</bits/stdc++.h>…

Yuki 313 π ( Hash )

No.313 π - yukicoder 間違ってる位置を知らなくていいので、愚直に 0 ~ 9 それぞれの登場回数を比較すればいい。 しかし素数を base にして hash すると間違ってる位置がわかる。 kmjp.hatenablog.jp 素数は 10 以上のだけを使うのに注意。 #include <bits/stdc++.h> using</bits/stdc++.h>…

Yuki 160 最短経路のうち辞書順最小 ( Dijkstra )

No.160 最短経路のうち辞書順最小 - yukicoder なんか前にも書いたような感じがするな.. でもちょっとだけ考えた 経路のリカバリーは終点から一つ前のノードを辿るから、始点と終点を裏返して、同じ距離でたどり着ける場合はその一つ前のノードが小さい方で…

Yuki 355 数当てゲーム(2) ( Hit & Blow )

No.355 数当てゲーム(2) - yukicoder 可能性のある候補だけを残す全探査。 Hit & Blow と呼ぶらしい ( ? ) #include <bits/stdc++.h> using namespace std; signed main(){ set< tuple< int, int, int, int > > cand; for( int i = 0; i < 10; ++i ) for( int j = 0; j < 10</bits/stdc++.h>…

Yuki 179 塗り分け ( Ad hoc )

No.179 塗り分け - yukicoder 平行移動するベクトルを枚挙し、チェックするだけ。 最大計算量はおよそ 100^2 * 50^2 少なくとも一つマスを塗るという制限に気をつけましょう。 #include <bits/stdc++.h> using namespace std; const string msg[] = { "NO", "YES" }; int in</bits/stdc++.h>…

Yuki 85 TVザッピング(1) ( Ad hoc )

No.85 TVザッピング(1) - yukicoder 証明が面白い。チェスをイメージしましょう。 kmjp.hatenablog.jp #include <bits/stdc++.h> using namespace std; const string msg[] = { "NO", "YES" }; signed main(){ int N, M, C; cin >> N >> M >> C; if( not ( N >= M ) ) swap(</bits/stdc++.h>…

Yuki 198 キャンディー・ボックス2 ( Ternary Search )

No.198 キャンディー・ボックス2 - yukicoder 自分の普段の書き方がバグりまくって解説を見た。 mmxsrup.hatenablog.com 注意すべきことは自分の ok() の返す値は gol がある上限を超えると不可能として INF とする。それが関数の右部分を平らかにする、な…

Yuki 78 クジ付きアイスバー ( Ad hoc, Periodic )

キモい.... 説明するのにもキモい... c : 今もってるあたり数 b : 今まで買った数 e : 今まで食べた数 そこからリピートする部分を探して、バグ出さずに頑張っていじれば... #include <bits/stdc++.h> using namespace std; signed main(){ int N, K; cin >> N >> K; string</bits/stdc++.h>…

Yuki 58 イカサマなサイコロ ( DP or Monte Carlo )

No.58 イカサマなサイコロ - yukicoder 制限が小さいゆえMonte Carlo で適当にやってもおk。 DP: #include <bits/stdc++.h> using namespace std; signed main(){ int N, K; cin >> N >> K; vector< vector< double > > dpn( N + 1, vector< double >( N * 6 + 1 ) ); dpn[ </bits/stdc++.h>…

Yuki 157 2つの空洞 ( 0-1 BFS )

No.157 2つの空洞 - yukicoder 0-1 BFS (いらないけど #include <bits/stdc++.h> using namespace std; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; int in_range( int h, int w, int x, int y ){ return 0 <= x and x < h and 0 <= y and y < w</bits/stdc++.h>…

Yuki 164 ちっちゃくないよ!!( std::stoll )

No.164 ちっちゃくないよ!! - yukicoder 進法の変換練習ね。 stoll( const string &str, size_t size, int base = 10 ) leading 0 あっても構わんよ #include <bits/stdc++.h> using namespace std; signed main(){ int N; cin >> N; vector< string > A( N ); for( int i</bits/stdc++.h>…

Yuki 6 使いものにならないハッシュ ( Deque )

No.6 使いものにならないハッシュ - yukicoder題意: 給 L, R,代表所求區間 [ L, R ] 中,如程式碼中的 get_hash() 函數,最長區間 [ l, r ] 滿足 get_hash( i | l ≤ i ≤ r ) 皆相異,其最大可能的 l。資料規模: L, R ≤ 2e5解法: 用 deque,從後面掃回來…

Yuki 374 コイン ( Game Theory )

No.374 コイン - yukicoder もし先手が置けたら中心に置き、後手がどう置けば先手はその対称する位置にもおく。すると先手は必ず勝つと示せる。 #include <bits/stdc++.h> using namespace std; const string msg[] = { "K", "S" }; signed main(){ unsigned int A, B; cin </bits/stdc++.h>…

Yuki 442 和と積 ( __int128 )

No.442 和と積 - yukicoder __int128 超便利。 #include <bits/stdc++.h> using namespace std; signed main(){ long long A, B; cin >> A >> B; __int128 a = A + B; __int128 b = A; b = b * B; long long ans = __gcd( a, b ); cout << ans << endl; return 0; }</bits/stdc++.h>

Yuki 81 すべて足すだけの簡単なお仕事です。( __int128 )

No.81 すべて足すだけの簡単なお仕事です。 - yukicoder __int128 のいい練習になった、普通に面倒な問題。 最大 11 + 10 桁あるから __int128 を使わざるを得ません。 まずは 10^10 を掛ければ色々と簡単になります。__float128 の使い方は知らないな...、…

Yuki 131 マンハッタン距離 ( Binary Search )

No.131 マンハッタン距離 - yukicoder よくわかんないけど、とにかく二分探査! #include <bits/stdc++.h> using namespace std; signed main(){ int x, y, d; cin >> x >> y >> d; x = min( x, d ); y = min( y, d ); if( not ( x >= y ) ) swap( x, y ); int a = -1; int </bits/stdc++.h>…