Entries from 2016-12-01 to 1 month
Problem - D - Codeforces題意： 有一個 N * N 的矩陣，裡面各自有 0 ~ 1e9 之間的整數，且對角線所有數值必為 0。你可以做詢問，用直列的編號們描述，對方會回答每個行分別對這些直列編號求的最小值。試用 20 次以內的詢問，得出所有行不含對角線的 0，分別…
No.242 ビンゴゲーム - yukicoder題意： 在 5 * 5 的矩陣玩賓果 ( 縱橫斜連線 )，每個格子都不重複存在一個介於 1 ~ 99 之間的一個整數。求矩陣裡的格子裡的數字都完全隨機，叫出的號碼也都完全隨機的情況下，喊到第 N 個數時，期望有多少連線。資料規模： 1…
No.210 探し物はどこですか？ - yukicoder題意： 有若干個房間，我們想找到一個藏在某處的寶物，而每個房間有寶物的機率為 P / 1000，如果該房間確實有寶物，則每次檢查這個房間會找到寶物的機率為 Q / 100。求最佳檢查順序下，能找到寶物的最小期望檢查次數…
No.412 花火大会 - yukicoder題意： 有三個人分別要 R[ 0 ], R[ 1 ], R[ 2 ] 以上面積的一塊布料。現在有若干個布料，求有多少種帶布料的方法，能滿足三個人的需要。資料規模： 布料數 1≤N≤30 布料大小 1≤Ei≤100 時限 2000 ms 記憶體 512 MB解法： 想省去討…
No.102 トランプを奪え - yukicoder題意： 四種花色堆四疊，每疊張數 1 至 13 張，輪流操作玩一場遊戲。一次操作需選擇一疊，並抽走 1 至 3 張，納入自己的手牌。若取得了該疊最後一張，就能奪走對手的手牌，使對手手排只剩原本的一半，向下取整。張數多的贏…
No.320 眠れない夜に - yukicoderかなりフィボナッチ数列の勉強になったので、ちょっとノートをします。pekempey さんの記事を参考にしました。ある項目に 1 少なく数えるのは、その項目から と負のフィボナッチ数列を並列して進ませる事と同じで、縦の総和…
No.416 旅行会社 - yukicoder題意： 給一個圖，和破壞邊的順序 ( 不一定會將所有橋破壞 )。對於所有大於 0 的節點，求哪一次破壞後無法從 0 達到。若一開始就不能到達，輸出 0，若破壞完依然能到達，輸出 -1。資料規模： 節點數 2≤N≤1e5 初始橋的數量 1≤M≤2e…
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, …
D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder題意： 給相同節點數的兩個圖，對於每個點，求有多少點和它在兩個圖上都屬於相同的連通分量。資料規模： 節點數 2≦N≦2e5 兩個圖分別邊數 1≦K,L≦1e5 保證同一個圖不存在重邊 時限 2000 ms 記…
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 -…
Problem - D - Codeforces題意： 給每個人的重量和權值。再給每對朋友的關係。x 和 y 屬於同個朋友圈，若存在一個序列 a[ 0 ], a[ 1 ], .. a[ i ]，滿足所有相鄰的人都是朋友。對於每個朋友圈，可以選一個人，或選所有的人，或都不選，邀請到派對。但是派對…
Problem - C - Codeforces題意： 給一個圖，每個節點都有一個連向另一個點的有向邊。求最小的 t，且 t ≥ 1，使得從每個節點 x 出發沿著有向邊走 t 次後達到的 y，從 y 出發沿著有向邊走 t 次也達到 x。若無法達成輸出 -1。資料規模： 節點數 1 ≤ N ≤ 100解法…
Problem - B - Codeforces題意： 給一個數列 A，和一個數 X。求數列中有多少無序對 ( i, j )，使得 A[ i ] XOR A[ j ] = X。資料規模： 1 ≤ n ≤ 1e5, 0 ≤ x ≤ 1e5 1 ≤ a[ i ] ≤ 1e5解法： 只要枚舉 i，就知道要求的另一個數是 X XOR A[ i ]。所以累加 X XOR …
Problem - A - Codeforces題意： 求 1378 ^ N 的最後一位數字資料規模： 0 ≤ N ≤ 1e9解法： 當 N = 0，是 1。 否則會循環，如 8, 4, 2, 6, 8, 4, 2, 6, ...時間 / 空間複雜度： O( 1 ) int N; void init(){ cin >> N; } void solve(){ // 1, 8, 4, 2, 6, 8, …
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 基地台座標 …
D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder題意： 給一個字串，每次可選取非兩端的任意字元使其消失，但前提是消失後不能有任意兩個相鄰字元相同。兩個人輪流做，先不能做的輸，求誰贏。資料規模： 3 ≤ | S | ≤ 1e5解法： 考慮最終狀態的…
No.75 回数の期待値の問題 - yukicoder 古寺いろはのサブミ見て勉強になった。 漸化式が状態を互いに参照しまわりそうで DAG になれそうにない時は連立方程式に書き換えてとけばいいことですが、もっと簡単な方法で近似値が求められる。その方法とはただ愚直…
D: シャッフル席替え - AtCoder Regular Contest 003 | AtCoder ARC#003D from nullmineral www.slideshare.net かなりわかりやすいスライドですが、覚えておきたいものをメモ： Hoeffdings Inequality ● X1, X2, …, Xn を独立な Bernoulli 確率変数とする ●…
