Yuki
No.389 ロジックパズルの組み合わせ - yukicoder題意： 在一排 M 個格子上放黑色點，依序為 H[ 0 ], H[ 1 ] .. H[ N ] 個連續的黑色點，且兩兩以至少一個的連續白色點區隔。求模 1e9 + 7 後的方案數。資料規模： 1 ≤ M 0 ≤ H[ i ] SIGMA{ H } ≤ M 保證若有一…
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 的最終樣貌資料規模…
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, …
No.34 砂漠の行商人 - yukicoder最悪の場合は通る砂漠のレベルが全部最高である 9のとき。この場合は遠回りはいらないのでマンハッタン距離を考えて、体力は精々 N * 2 * 9 で十分だと分くる。 int N, V, Sx, Sy, Gx, Gy; vvi LV; void init(){ cin >> N >> …
No.241 出席番号(1) - yukicoder題意： 每個人有 [ 0, N - 1 ] 的整數中獨特的一個編號，且都有一個不喜歡的座位號碼。現在要將 [ 0, N - 1 ] 的整數分配給他們做為座位號碼。求一組方案，使得每個人都不坐在自己討厭的座位號碼上。資料規模： 人數 1≤N≤50 …
Problem - E - Codeforces題意： 在一個圓桌上吃飯，有兩種飯，希望每連續三個人，都一定有一個人吃不一樣的東西。每個人都有一個唯一對應的伴侶，而伴侶之間也規定不能吃一樣的東西。求合法分配的結果。若無法分配，輸出 -1。資料規模： 情侶對數 1 ≤ n ≤ 1…
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 -…
No.37 遊園地のアトラクション - yukicoder題意： 有若干個遊樂設施，用排隊時間和娛樂程度描述。初始有 T 單位的時間，同一個設施每玩一次，娛樂程度便會減半並向下取整。求在時間內能造成的最大的娛樂值。資料規模： 初始時間 1≤T≤10000 娛樂設施數目 1≤N≤…
No.202 1円玉投げ - yukicoder題意： 丟半徑 10 的銅板。每次丟完後，若剛好這個硬幣落在另一個已在地上的硬幣，換句話說重疊，就立刻取回這個硬幣，否則留在原地。求最終有多少硬幣在地上。資料規模： 銅板數 1 ≤ N ≤ 1e5 銅板圓心座標 0 ≤ X[ i ], Y[ i ] …
No.96 圏外です。 - yukicoder題意： 兩個人各拿著一台無線電要通話，無線電之間最遠可通話距離為 1 km，基地台之間則是 10 km，無線電與基地台之間則是 1 km。在兩人可通話的前提下求最大可能的歐幾里德距離。資料規模： 基地台數量 0≤N≤120000 基地台座標 …
No.75 回数の期待値の問題 - yukicoder 古寺いろはのサブミ見て勉強になった。 漸化式が状態を互いに参照しまわりそうで DAG になれそうにない時は連立方程式に書き換えてとけばいいことですが、もっと簡単な方法で近似値が求められる。その方法とはただ愚直…
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.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 とする。それが関数の右部分を平らかにする、な…
キモい.... 説明するのにもキモい... 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，從後面掃回來…
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 の使い方は知らないな...、…
