Problem - E - Codeforces 首先我們知道這一般來說是很常見的最短路水題。但問題是 N = 1e7，顯然不給 logN 或足夠常數讓你乖乖玩 SSSP，所以我們考慮轉移邊的性質。首先我們考慮有哪些轉移的組合。一般之所以不能由左往右刷 dp 表是因為這題有反向邊，也許…

Problem - C - Codeforces 哎呀，我寫的真是亂七八糟，但思維倒是很直覺的。注意到 N 只有奇數，所以考慮如果有 N - 2 的解，如何擴展到 N 的解。顯然就是外面多一層「囗」型的筐，接著把 N = 3 和 N = 5 拿出來觀察一下就會知道，( N + 1 ) / 2 是偶數的時…

Problem - B - Codeforces We will simply go as far as we can each time, so we will sweep from left to right, that from right to left, ... until there are no more left. void solve(){ int N; cin >> N; vi A( N ); for( int i = 0; i < N; ++i ) c…

Problem - C - Codeforces First, it is easy to observe that the largest value in the initial input is definitely part of the answer. So we will continually take out the largest element from the set, and remove each pair of gcds created by t…

Problem - D - Codeforces I thought this was quite difficult, despite the technique required was not that advanced. The key is to come up with the dp form: dp[ i ][ j ][ k ] : maximal length of non-decreasing subsequence of A concatenated k…

D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder Finally found an easy problem to start familiarising with parallel binary search ( I thought it is called holistic binary search ). pekempey.hatenablog.com The link above really helped, …

Problem - D - Codeforces 本來以為開頭提的持久化只是唬人的，但最後我還是用了 ( ? )。考慮到總共最多只會改變 Q = 1e5 個行，意味著最多只需紀錄 1e5 * 1e3 個位元。這是 512 MB 能勉強容下的。那麼就用持久化的思想，只有被改變的新創，否則統一指到池裡…

Problem - C - Codeforces 網路上找到了這張圖。以前學過這個定理。 滿足畢氏定理 a^2 + b^2 = c^2 的 a, b, c 必然滿足且各自唯一對應到 a = 2 * m * n, b = m^2 - n^2, c = m^2 + n^2 整數解 ( a, b, c ) 必然滿足一組整數的 ( m, n ) 且 m ≥ n ( 為什麼呢…

Problem - B - Codeforces 需要想那麼一下下。就會發現其實答案在輸入的邊上，且僅限於自身不是 bakery但連接的是 bakery的節點。取最小就行了。 void solve(){ int N, M, K; cin >> N >> M >> K; if( K == 0 ){ cout << -1 << endl; return; } vector< trip…

Problem - A - Codeforces 這題真的很簡單，我一分鐘就傳了。但因為太有紀念意義了。 我竟然漏看 grey也算，pretest全過，然後被 hack了，太智障了。 void solve(){ int N, M; cin >> N >> M; for( int i = 0; i < N; ++i ) for( int j = 0; j < M; ++j ){ s…

這題是需要想一下的構造題。本來想放棄亂寫 hash 臨時判斷，本地建答案，但突然想遞迴構造看看。 一開始我們有正確的 "ABC" 如果把 A, B, 和 C 當成各自不同的 pattern, 也就是說令 A = 某個 'A', 'B', 'C' 組成的亂七八糟的字串，B, C 亦同，並保證一些性質…

本來以為很困難，最後幾分鐘突然靈感來。 假設由左到右有若干連續的人往右看，接著若干連續一排人往左看，那麼，哭哭的次數是固定的。假設左邊的人數為 L, 右邊的人數為 R, 考慮其中任何一個人，不失一般性取向右看的其中一人，不管他待到右邊的所有人都不見…

蠻有趣的一道題。首先要觀察當 N ≥ 3 的時候，其實是先進行一次 N - 2 的子問題，取走最下面的盤子，然後再反著做一次 N - 2 的子問題，經過這三個步驟之後轉換成 N - 1 的子問題，遞迴下去，直到 N ≤ 2 直接解決。因此令 f( N ) 為 N 個環的步驟數，會有 但…

沒有什麼玄機的 DP，注意要 long long。 void solve(){ int N, M; cin >> N >> M; vvi C( 3, vi( 3 ) ); for( int i = 0; i < 3; ++i ) for( int j = 0; j < 3; ++j ) cin >> C[ i ][ j ]; vvi G( N, vi( M ) ); vvl dp( N, vl( M ) ); for( int i = 0; i < …

最大最小值問題十之八九是二分搜。能剪的次數和最短紙的最長長度，顯然成單調關係，因此可以用二分搜處理。注意最短長度的上界是原先的最短長度，還有要開 long long。 bool ok( const vi &L, const int K, int x ){ ll cnt = 0; for( int i = 0; i < L.size…

因為沒有題目沒有名字，所以我決定給他亂取XDD 幸好 double 沒出問題。 void solve(){ double a, b; cin >> a >> b; int ans = 0; while( a > 1 ) ++ans, a /= 2; while( b > 1 ) ++ans, b /= 2; cout << ans << endl; }

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder またも面白い問題。 トポロジカルソートに注意しすぎた。でも N の小ささを見れば大抵 bit DP だとわかる。 dp( S ) : number of valid topological sorted array for S and the restrictions given int…

D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder シンプルでいい問題。 左下の塊上一つの行を右に沿って枚挙するだけ。答えはその塊の右上のセルからその行に沿って右に行く途中加算する 始点からそこに着く方法数 * …

D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder A real nice trick problem. Since it is only asks whether in some contiguous range one particular character appeared more than half of the length, we are to realize that …

D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder The key is to observe that only staying in one city will maximize the profit, because if staying in two is better, we will still arrange all time on the higher-price city. We wil…

Problem - B - Codeforces I thought this was a little difficult for pB. Observe and we will find that we want to know whether there exist at least two pairs of ( a, b ) and ( a', b' ), where both a indicates y value on x1, b indicates y val…

D: 画像処理高橋君 - AtCoder Beginner Contest 039 | AtCoder Greedy で出来るだけ多く置いてみる。最後に一致するかどうかをみてみる。 const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 }; const int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 }; const int MAXH…

D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder 最初はパッとしなっかったけど、よく考えると、年について、クエリと辺をソートすると Union Find の問題になる。 Union Find 系の特徴はやはりこういう者だなと思った。 破壊を逆か…

D: 三角形の分類 - AtCoder Beginner Contest 033 | AtCoder This was quite interesting a problem, despite the meticulousness in double precision required. First it is clear that it is impossible to simple enumerate each complete triangle, so …

typedef long long ll; typedef pair< int, int > pii; typedef vector< int > vi; typedef int T_frac; struct frac{ // actually I think T_frac = ll will overflow T_frac u, d; frac( T_frac _u, T_frac _d ){ assert( _d != 0 ); int g = __gcd( _u, _…

D: 食塩水 - AtCoder Beginner Contest 034 | AtCoder If it is possible to make p%, it will also be possible to make p - 1%. With this property, we know that we can try binary search on the percentage. For a fixed percentage x, we can calcula…

C: 経路 - AtCoder Beginner Contest 034 | AtCoder 前はDPにこだわりすぎてとけなかった。でもよく考えると実は H + W - 2 の選択から H - 1 ( あるいは W - 1 ) 個を選ぶだけの事。factorial と mod_inv で終わり。 const int MOD = 1e9 + 7; int int_pow(…

D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder Since there are only 9 s, each |s| within range [ 1, 3 ], we can enumerate in 3^9. Then check whether it is valid with O( N ). Total ( 3^9 * N ). const int MAXK = 9 + 1; const int MAXN…

D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder Find the length before getting into the cycle, and the length of the cycle. Then get K in mod len_cycle, O( N ). const int MAXN = 1e5 + 2; int N, A; string K; int B[ MAXN ]; void sol…

Problem - C - Codeforces I really enjoyed this problem, for it did not require much code, and the solution is actually simple despite the fact that it needs some creativity( seems like being able to solve ABC before 70 min will have placed…