2011-01-01から1ヶ月間の記事一覧
英文読解が大変。 英語版Wikipediaに助けられました。 dfsで全探索する。 計算量はO(2^y) #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int MAX_V=30; int V; char g[MAX_V][MAX_V]; int memo[MAX_V]; int a,b,y; int ans; void dfs(int used,</cstring></algorithm></iostream>…
全ての家を通るパイプを建設するのに必要な長さの最小値を求める程度の問題。 クラスカル法→貪欲に辺を消していく。 UnionFind木は蟻本参考にしました。 計算量はおそらくO(E^2)実装(C++/UnionFind木省略) #include <iostream> #include <vector> #include <algorithm> #include <set> using na</set></algorithm></vector></iostream>…
XMLの構文解析をする問題。 構文解析をしたら条件を満たす一番深い所にあるパネルを求めるだけで完了する。 最初に入力を-1,-1,10001,10001{実入力} のように加工することで、 条件分岐は不要になる。実装(C++) #include <cstdio> #include <vector> #include <iostream> #include <string> usi</string></iostream></vector></cstdio>…
二分木の交点(and)と結合(or)を問う問題。 実装してて楽しかった。Sはstringの代わりに使っているクラス。 実装(C++) #include <iostream> #include <vector> #include <deque> using namespace std; struct tree{ vector<tree> l,r; }; typedef deque<char> S; istream &operator>>(istream &is,S</char></tree></deque></vector></iostream>…
構文解析問題。 「10分で書ける、お手軽パーサー」を参考に書きました。実装(C++) #include <cstdio> #include <cmath> #include <cstring> #include <climits> #include <algorithm> #include <vector> #include <set> #include <iostream> using namespace std; typedef set<int> SET; SET S[5],U;//0:A 1:B 2:C 3:D 4:E typedef pair<SET,const char*></set,const></int></iostream></set></vector></algorithm></climits></cstring></cmath></cstdio>…
Easy 慎重に解いた。 同じ変数を重複して宣言するという馬鹿なミスに10分ぐらい悩まされた。 Passed Systme Test(125.01) Medium greedyでは駄目らしい OpenedHard 方針が立たない。 Unopened Challenge Partは眺めていただけ合計125.01点で391位 レートは13…
本番では最小の幅を求めて失敗した問題。 5重ループで解いてみた。 実装(VB.NET) Imports Microsoft.VisualBasic Imports System Imports System.Collections Imports System.Text Public Class Painting Dim Map(50,50) As Byte Dim Test(50,50) As Byte Di…
Riffle Shuffleの仕様を読み取り実装する問題。英文が読みとれればそれを実装するだけ。 dequeを使うと実装が楽な気がする。 実装(C++) #include <cstdio> #include <deque> using namespace std; int R(int n,int c,int *D){ deque<int> A,B; int count=0; for(int i=0;i<(n)/2;</int></deque></cstdio>…
少女が全ての本を棚に片づけるのにかかる最小の時間を求める問題。最初はC++で優先度つきキューを用いて解答したけど、速度/メモリが微妙だったので DPに書きなおした。 珍しくC言語で実装。実装(C) #include<stdio.h> #include<stdlib.h> #include<string.h> int C[2][2][3][3]={{{{0,1,2</string.h></stdlib.h></stdio.h>…
久々にレート上昇。A 問題文の意味を把握するのに5分かかってしまった。 反時計回りでの距離と時計回りでの距離の小さいほうを出力。 Accepted(484点)B 問題文が長かったのでとばしてCに行くC とりあえず深さ優先探索で解く。 DPすれば間にあうかなとか馬鹿…
PC甲子園本戦では解けなかった問題。あるマスにある金額を持って止まった時の期待値をDPで求めていく。 メモ化探索のメモのミスで4回ぐらいWAになってしまった実装(C++) #include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long double ld; #defin</cstring></cmath></cstdio>…
二回連続で0点Easy 無駄に時間をかけた上に、考えかたをまちがっていてチャレンジされました。 Challenge Succeed Medium 確率DP… OpenedHard 方針が立たない。 OpenedChallenge PartでEasyを落とされる。 自分は何も出来ず。合計0点 レート:1312(-94)確実…
一問も解けなかった死にたいEasy 途中で勘違いして死亡 Challenge Succeed Medium DPかなぁとか思っていたけど単純に実装してもTLEになるらしい。 OpenedHard 方針が立たない。 Opened Challenge PartでEasyを落とされる。 自分は何もせず。合計0点で220位 …
Codeforcesのサーバーの内部実装の変更に伴い、テスト目的で開催された。レートには影響されない。 全部典型問題と言うことだが、Cは解けなかった。A テストケースを見て問題文の意味を把握。かなり急いで記述して解答。 Accepted。498点。B 問題文読む。 テ…