好不容易湊齊了同校三個人，才在期限前完成報名。今天去南港展覽館比這場，我想我的心態大概是一半一半的，一面有想發揮實力贏的執著，一方面因為要一個人孤軍奮鬥覺得其實來玩玩就行了。幸好開賽後禁止使用手機，某個隊員才沒有玩他的糞game來全力幫我。一…

Problem - D - Codeforces 2 elements with same value should never co-exist since it will be an even number, which will not be a prime number when summed, unless they were both 1. 2 even numbers nor 2 odd numbers can not co-exist as well. So…

Problem - E - Codeforces pekempeyさんの記事が参考になりました。ありがとうございます。 pekempey.hatenablog.com Trie はあまり慣れなかったのでいい練習になった。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; const int MAXK = 1e9 + 9</bits/stdc++.h>…

Dashboard - Round 1A 2016 - Google Code Jam There are two possible ways to form a maximum cycle: 1. Sum up for each pair ( u, v ) that share bidirectional edges, length of chain that starts with u, and v, such like f[ f[ .. f[ v ] ] ] u ->…

Dashboard - Round 1A 2016 - Google Code Jam The constraints were small ( T ≤ 50, N ≤ 50, H ≤ 2500 ) so I stuck and thought it could be solved by some brute force methods. However, if the point is reached, it will very easy. Thinking it cle…

Dashboard - Round 1A 2016 - Google Code Jam It is very intuitive to come up with the greedy strategy where, alphabetically less characters go to the back, otherwise to the front. #include <bits/stdc++.h> using namespace std; int main(){ int T; scanf("%d"</bits/stdc++.h>…

Problem - D - Codeforces It's clear that if the final colour is determined, and some vertex u has decided whether to flip or not, all the other vertices that are of the same component of u will decide itself whether should be flipped or no…

Problem - C - Codeforces Many people were hacked for this problem, for cases where leading zeros exist. Simply find answer for each suffix from smaller length, and it will do fine. P.S. This round was unrated QQ. #include <bits/stdc++.h> using namespace </bits/stdc++.h>…

Test Online Judge 這題各種限制很緊，差點以為這個解法行不通 ( 或許我的解法也不是正解 )。 想著應該是要用篩法先預處理，利用質因數分解後的指數做組合算出答案。但如果傻傻地做，就會MLE，所以只能用 short存答案。這樣不會爆是很顯然的，因為最多只會有…

除了細節稍做改良之外，提供路徑打印模式，有答案便能快速給出路徑。現在配合人腦，勉強能解出5 * 5。 還有些功能正在思考怎麼實作比較好： 像是若知道某些字串存在，但不知道何時何地使用，是否能做合理的剪枝。 也該做某種東西顯示它大略的進度，否則還要…

Problem - C - Codeforces Take any point first, there will be at least one triangle that does not contain any other points inside, which can be formed with it. In order to avoid points inside the triangle, we can simply take any two points …

因為不可能讓程式自己獨立解出答案，改成可以支持各種操作的方式輔助縮減答案範圍，再用人腦解決。 第二次寫就好很多了，語法也比較熟悉。 這個版本支持輸入 $表示空的格子，也能指定遞迴深度，還有事先寫好哪些字是禁用的。利用的剪枝還是比較基礎，對於需…

Brain Word Puzzle - Google Play の Android アプリ WordBrain on the App Store 這是一個文字遊戲，前面的關卡都是一個 4 * 3 的矩陣，每個格子裡有一個字母。會給兩個長度，相加等於 12，第一次操作要選擇一個字母當起點，然後移動到尚未拜訪的周圍八格其…

Dashboard - Qualification Round 2016 - Google Code Jam There are several solutions, and mine is of the easier one. Since the input is fixed, 16 and 32, observing that both of them are even numbers, we will come up to that, given any number…

Dashboard - Qualification Round 2016 - Google Code Jam This can be solved by DP, too. However the greedy approach is easy to come up with and shorter in code. With some observation, it is easy to find that the flips will be made from left …

Dashboard - Qualification Round 2016 - Google Code Jam It just feels like it will definitely finish before 20000 times, if solution exists. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 6; typedef long long ll; ll n; void solve(){ </bits/stdc++.h>…

D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder dp[ u ][ j ] : the number of valid combinations, when now on node u ( not yet colored ), and its father is white / black dp[ u ][ j ] = product( dp[ v ][ 0 ] ) + product( dp[ v ][ 1 ] ) * …

Problem - D - Codeforces 事實上應該有更好的解法，就是先把所有矩形的面積取和，再用BIT之類的結構維護一些東西，計算所有重疊的部分然後減去。但顯然也能直接當作是矩形面積覆蓋問題。因為後者比較有實用性，而且自己不太熟悉，我試著實現了後者。這是一…

Problem - B - Codeforces kmjpさんの解法を参考にしました。 kmjp.hatenablog.jp trainのルートを全部あらかじめpqに入れて、もし一直線で着く方が速いならそれが先に出されて、その場でdisを更新しつつcountを上げる、そうでなければ普通にdijkstraする。 …

Problem - A - Codeforces 一開始以為有二分性質，結果原來只需要暴力。。然後我預處理的部份也寫得太複雜了，其實根本可以更暴力的搞，會很好寫的。 #include <bits/stdc++.h> using namespace std; const int MAXPQ = 1e4 + 4; const int MAXT = 6e6 + 6; typedef long lo</bits/stdc++.h>…

Problem - C - Codeforces 這題需要的是一點直覺，或說是靈感。要發現其實只要遞迴構造左上右上左下都相同的，而右下正負相反，初始是n = 0時為+。 #include <bits/stdc++.h> using namespace std; const int MAXK = 9 + 1; int a[ 1 << MAXK ][ 1 << MAXK ]; int main(){ i</bits/stdc++.h>…

Problem - 297A - Codeforces 顯然1的數量最多只會變多一次，而且是當且僅當原本1的數量是奇數。排除掉那些情況後觀察一下就會發現怎樣都可以使a變成b的。 #include <bits/stdc++.h> using namespace std; const int MAXS = 1e3 + 3; string a, b; int countOne( const stri</bits/stdc++.h>…

Problem - C - Codeforces dp[ i ][ j ][ k ] : boat is on the original side, j people 50 pounds are on the goal, k people 100 pounds are on the goal Then we will be able to perform PFS to find the shortest path, but since all the weights for…

Problem - D - Codeforces First we will have to take away apparently wrong cases, where dis[ i ][ i ] != 0 or dis[ i ][ j ] == 0 for i != j, or if dis[ i ][ j ] != dis[ j ][ i ]. We will find that we are willing to make a tree, so the short…

Problem - 25C - Codeforces 先做完一次MSSP之後，對於每個動態操作可以直接詢問每個兩端，是否用了這條邊之後會更好。 注意題目是說額外新增路，所以是不一定要取的。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; const int MAXK = 300 + 3;</bits/stdc++.h>…

Problem - B - Codeforces 如果順著做，逐一破壞。。嗯，看到逐一破壞就可以開始想反著觀察就是逐一增加了。 因為問題是Multiple Source Shortest Path，所以可以馬上想到Floyd Warshall演算法了。 想起以前學長和我提過，為什麼三層迴圈的中繼點要在最外圈…

Problem - A - Codeforces 二回べつべつに区間操作するのは自明。まずどの操作が何回使われるかを統計して終えてから操作毎に区間addをすればいい。 Range add と Single query しかないので BITの方がかなり楽。 追記：いや、普通にarrayの上でいもすすれば…

Problem - B - Codeforces Dijkstraみたいな感じでやればいいね。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e5 + 5; int n, k; char w[ 2 ][ MAXN ]; struct State{ int t, x, lv; State( int _t = -1, int _x = -1, in</bits/stdc++.h>…

Problem - A - Codeforces f( x ) = k * x + b f^n( 1 ) ≤ f^a( t ) となるような最小な aを求める。 始めは matrix fast power で二分探査しようと頑張ってみたがオーバーフローが出るみたいで失敗した。 ちゃんと考えると、単調増加関数なので両方に f^( -…

wakatake-topics.com 久しぶりにいい映画に感動されたQQ いつか忘れたらまたもう一度見たいな。 明日また沢山CFR virtualして頑張ろOrz