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>…

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

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

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>…

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

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>…

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

Problem - D - Codeforces題意： 給一棵樹，有點權和邊權。定義 f( v, u ) 為真，若 u 為 v 的子樹裡的節點，且 dis( u, v ) ≤ 邊權[ u ]。對樹上所有節點 x，求 SIGMA( f( x, y ) | ALL y )。資料規模： 節點數 1 ≤ n ≤ 2e5 點權 1 ≤ a[ i ]≤ 1e9 邊權 1 ≤ …

Problem - C - Codeforces題意： 給一堆區間，求一個陣列，使得所有區間的最小 mex 最大。資料規模： 所求陣列長度 n, 區間數 m, 1 ≤ n, m ≤ 1e5 時限 2000 ms 記憶體 256 MB解法： 考慮最短區間，長度就是最大最小 mex。因為只要由左而右，小到大填數字，並…

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

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>…

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>…

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>…

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

Problem - D - Codeforces題意： 給一排兔子，用三階段的獲益描述。每個兔子都要恰選一次，而各自得到的獲益為其第 ( 左邊已被選 + 右邊已被選 ) + 1 階段的獲益。求最大可能總獲益。資料規模： 1 ≤ n ≤ 3000 0 ≤ ai, bi, ci ≤ 1e5 時限 2000 ms 記憶體 256 …

Problem - E - Codeforces題意： 給首領的編號，以及公司裡所有人各自的上級數量( 所有上級 )。求至少有多少人是謊報的。資料規模： 1 ≤ n ≤ 2e5, 1 ≤ s ≤ n 0 ≤ ai ≤ n - 1 時限 1000 ms 記憶體 256 MB解法： 首先檢查首領對不對，不對就直接改他。 接著看…

Problem - D - Codeforces題意： 給船的數量，船的長度，以及已嘗試射過多少位置，以及射的位置分布。地圖是一維的，而船的分佈未知。求至少還要再射多少位置，以及是哪些，才能保證至少射到一個船。資料規模： 1 ≤ n ≤ 2e5, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1解…

Problem - C - Codeforces題意： 給很多車，用價格和油箱容量描述。給加油站，用位置描述。過加油站時油箱會免費加滿油。起點 0 終點 S，求最便宜的車，可以不超過 T 分鐘到達終點。對每一單位距離都有兩種移動方式，用一單位的油兩分鐘過，或用兩單位的油一…

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>…

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>

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

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>…

http://yukicoder.me/problems/no/341 UTF-8 文字の比較問題なんですが C++ ではかなり面倒なようです。 なぜか RE するコードも載せたので、また時間あったらちゃんと見てみます。 #include <bits/stdc++.h> using namespace std; signed main(){ wstring_convert< codecvt</bits/stdc++.h>…

No.353 ヘイトプラス - yukicoder コードに '+' を一切使わずに A + B を解きたい。'-' を使えばいいと。面白かったわ www .

#131792 No.445 得点 - yukicoder なんで EPS つけないと最後のケースが落ちると分かるんだろう... 知りたいのはそのケースの作り方だ ._.

Problem - A - Codeforces題意： 一個方陣，初始所有值為 0，塞 1 進去，1 彼此不相鄰，且最後方陣必須上下、左右分別成對稱。給 1 的數量，求至少要邊長多少的方陣才能塞下。資料規模： 1 的個數 1 ≤ X ≤ 100解法： 先注意到因為必須對稱，奇數邊長的方陣一…

Problem - 559B - Codeforces題意： 對字串定義一個比較函數： 若 A == B 則 f( A, B ) = 1 若他們的長度相同，且長度為偶數，那麼分成兩半 A[ 0 .. size / 2 ), A[ size / 2, size ) 後，左右兩半對調，若對調後的 f( A', B ) = 1，那麼 f( A, B ) = 1。資…

Problem - 566F - Codeforces題意： 給一個嚴格遞增序列。求子序列最長長度，子序列滿足所有相鄰元素對，後一個元素可以被前一個整除。資料規模： 序列長度 1 ≤ N ≤ 1e6 元素大小 1 ≤ A[ i ] ≤ 1e6 時限 1000 ms 記憶體 256 MB解法： 注意到 [ 1, N ] 的數的…

Problem - F - Codeforces前言： Codeforces Round #379 (Div. 2) F. Anton and School - pekempeyのブログ pekempeyさんの記事読んでやっとわかった。題意： 給相同長度的 B 序列和 C 序列。求是否存在一個 A 序列，滿足 不存在則輸出 -1，否則輸出滿足的任…

Problem - B - Codeforces題意： 給一個圖，邊用四個值表示，( x, y, Cxy, Cyx )，代表 x 至 y 長度是 Cxy，y 至 x 長度是 Cyx。求是否存在一個正環，若存在則輸出最小環的長度。資料規模： 節點數 1 ≤ N ≤ 300 邊數 0 ≤ M ≤ N * ( N - 1 ) / 2 權值 -1e4 ≤ …