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

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

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

No.176 2種類の切手 - yukicoder先に T ≥ lcm( A, B ) させるように余る lcm( A, B ) * k を最大の整数 k で取る。 すると最悪の場合、T = 1e9, max( A, B ) = min( A, B ) = 1e4.5 となる。 しかしここで max( A, B ) を枚挙しても間に合う。 O( sqrt( T ) …

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

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 つけないと最後のケースが落ちると分かるんだろう... 知りたいのはそのケースの作り方だ ._.