PythTripletsaとbが互いに素であることから、aとbどちらも偶数になることは無い。また、aもbも奇数と仮定すると、a=2n-1, b=2m-1として、c2=a2+b2=2(2n2+2m2-2n-2m+1)。2(2n2+2m2-2n-2m+1)が平方数であるためには、(2n2+2m2-2n-2m+1)が素因数2を含まなければ…

CarelessSecretary vector<int> letter; for ( int i=0; i</int>

Islands #include <iostream> #include <string> #include <vector> using namespace std; class Islands { public: int beachLength( vector <string> kingdom ); }; int Islands::beachLength( vector <string> kingdom ) { int h = (int)kingdom.size(); int w = (int)kingdom[0].length(); int l = </string></string></vector></string></iostream>…

VacationTime #include <iostream> #include <vector> #include <numeric> using namespace std; class VacationTime { public: int bestSchedule( int N, int K, vector <int> workingDays ); }; int VacationTime::bestSchedule( int N, int K, vector <int> workingDays ) { vector<int> day( N ); f</int></int></int></numeric></vector></iostream>…

Easy (250) 277.63 Medium (500) 0 適当に貪欲に書いてみたけどSystem落ち。 Hard (1000) 0 Challenge 0 結果 1490 → 1516黄色に戻れて良かった。

Sequence of pointsM1.x = 2A0.x - M0.x M2.x = 2A1.x - M1.x = 2A1.x - 2A0.x + M0.x : Mn.x = 2(An-1.x - An-2.x + …… + A0.x) - M0.x M2n.x = 2(An-1.x - An-2.x + …… + A0.x) - Mn.x + M0.x = M0.xy座標も同様。 import sys A = [map(int,x.split()) for…

F1 Champions point = [25, 18, 15, 12, 10, 8, 6, 4, 2, 1]+[0]*50 t = input() score = {} for i in range(t): n = input() for j in range(n): name = raw_input() if name not in score: score[name] = [0]*51+[name] score[name][0] += point[j] score[…

Ring road全ての都市を行き来できるときは、一周できる。与えられた辺の方向別にコストを足して小さい方が答え。 n = input() road = [map(int,raw_input().split()) for i in range(n)] c1 = c2 = 0 p = 1 pr = 0 for i in range(n): for r in road: if r !…

忘れてた。

MatrixShiftings #include <string> #include <vector> using namespace std; class MatrixShiftings { public: int minimumShifts( vector <string> matrix, int value ); }; int MatrixShiftings::minimumShifts( vector <string> matrix, int value ) { int N = (int)matrix.size(); int M</string></string></vector></string>…

FriendTourManglisiの全員を辿るのではなく、Manaoの友人をのみを辿る。friends[0]の長さが36文字以内なのでMasaoの友人は高々15人。探索の結果をメモしておけば全探索が間に合う。d本のエッジを持つノードでそれぞれのエッジに進んだときに完遂する確率が分…

SubAnagramsn=|X|として、O(n3)ならば間に合う。動的計画法。numi,jをX[0..j]からX[i..j]を切り出したときのX[0..j]の最大分割数、tをX[t..i-1]がX[i..j]の部分グラフとなる最小のtとすると、numi,j = mint≦k≦i-1(numk,i-1+1)。 #include <string> #include <vector> #includ</vector></string>…

Badgersn匹のアナグマを飼えるかどうかを、0≦n≦Nについて調べる。飼うアナグマは餌の少ないものを貪欲に選ぶ。 #include <vector> #include <algorithm> #include <numeric> using namespace std; class Badgers { public: int feedMost( vector <int> hunger, vector <int> greed, int totalFood )</int></int></numeric></algorithm></vector>…

-25点 ＼(＾o＾)／結果 1705 → 1490青に戻った。もうだめだorz教訓： 点数低い人のコード見る前に、上位陣のコード見て解法を確認 250はそんなに難しくない

RabbitIncreasingわからなかったので、あちこちのブログなどを参考に。剰余で計算していると、ドナドナされる番数が２才以上の番数よりも多ければ〜という比較と、偶奇の判定ができない。１年目以外は２才以上の番は子供を産むので、２才以上の番を消して、…

RabbitJumping小さいジャンプでは位置の偶奇は変わらず、穴を飛び越えることはできない。穴で分けられた各区間の偶数と奇数の位置をそれぞれノードとして、ある区間の偶数（奇数）からある区間の奇数（偶数）の位置に大きいジャンプができる場合に、コスト１…

RabbitStepping全探索でも間に合う。が、こんな計算をする必要は無いらしい。Practiceのwriterの解答が美しすぎる。 #include <iostream> #include <string> #include <vector> using namespace std; class RabbitStepping { int countbit( int n ); public: double getExpected( strin</vector></string></iostream>…

0点 ＼(＾o＾)／結果 1852 → 1705

RabbitVoting #include <string> #include <vector> #include <algorithm> using namespace std; class RabbitVoting { public: string getWinner( vector <string> names, vector <string> votes ); }; string RabbitVoting::getWinner( vector <string> names, vector <string> votes ) { int n = (int)names.size(); v</string></string></string></string></algorithm></vector></string>…

Problem C ポロック予想動的計画法。和がnになる正四面体数の最小個数をAnとし、n以下の正四面体数の集合をT(n)とすると、 An = mint∈T(n)(An-t+1)。 奇数のみの場合も同様。 #include <iostream> using namespace std; int main() { const int N = 1000000; static in</iostream>…

Problem B 迷図と命ず幅優先探索。こういう入力の時は文字列のまま持っておくと楽らしい。 #include <iostream> #include <vector> #include <string> using namespace std; int main() { const int dirx[4] = { 1, 0, -1, 0 }; const int diry[4] = { 0, 1, 0, -1 }; while ( true ) {</string></vector></iostream>…

Problem A 角角画伯，かく悩みき問題とジャッジデータは↓ 国内予選問題 | ACM-ICPC: ACM International Collegiate Programming Contest Asia Regional Contest 2010 in Tokyo各タイルの位置を覚えておけば良い。 #include <iostream> #include <vector> #include <algorithm> using names</algorithm></vector></iostream>…

Problem E 最強の呪文動的計画法。各ノードiについてそれぞれの長さlの呪文で最強のものを覚えておく。そのような呪文をSi,lとすると、 Si,l = mins∈{t|yt=i}(Sxs,l-|labs|+labs) が成り立つ。と、 id:pes_magic が言っていた。最強の呪文が存在しない２つめ…

Problem D ぐらぐら問題文の通りに計算するだけ。だが、面倒くさい。 #include <iostream> #include <vector> #include <string> using namespace std; int main() { while ( true ) { // 入力 int w, h; cin >> w >> h; if ( w == 0 && h == 0 ) break; vector<string> elev( h ); for ( int i</string></string></vector></iostream>…

RouteIntersection頂点数が高々50なので、実際に動く次元の数も高々50。 #include <string> #include <vector> #include <map> #include <set> using namespace std; class RouteIntersection { public: string isValid( int N, vector <int> coords, string moves ); }; string RouteInters</int></set></map></vector></string>…

PalindromesCount #include <string> using namespace std; class PalindromesCount { string reverse( string w ); public: int count( string A, string B ); }; string PalindromesCount::reverse( string w ) { string r; for ( int i=w.length()-1; i>=0; i-- )</string>…

朝起きたら、すでに終わっていた。TCO中で通常のSRMが少ない上に寝坊で最近全然参加できていない。

TreesCountダイクストラ法で頂点vの距離を確定するときに、確定済みの頂点からvへ向かう辺のうち１本を残し他を取り除くことを考える。uとvを結ぶ辺の長さをeとして、dist[u]+e=dist[v]となる辺から残す１本を選ぶ。 #include <string> #include <vector> using namespace st</vector></string>…

SquaresCovering動的計画法。2nの配列にビットが立っている点を覆う最小コストを格納。頂点を２つ選べば正方形の置き方が決まる。正方形を置く順番は任意なので、１つは最左の点を選ぶ。 #include <vector> using namespace std; class SquaresCovering { int countb</vector>…