2011-03-01から1ヶ月間の記事一覧
主にプログラミング関連での新年度の目標を決めることにする。 一度でもTopCoderのSRMのレートが1800以上になる AOJでslovedが500問以上になるようにする PKUで200問以上 Eulerで150問以上 ICPC国内予選を突破 達成出来ると良いな…
昨日のSRM501 Div1のMediumをVBで書いてみたのですがTLEを回避出来ません。 ほぼ同じ内容のC++のコードだと最大ケースでも500msかからないというのに…。 配列のアクセスの速度とかが原因だとは思うけど酷い。 計算量がギリギリの問題はC++で解くべきかもしれ…
id:JAPLJさん回。見事に死亡。 提出コードはhttp://www.topcoder.com/stat?c=room_stats&rd=14430&rm=307619から。 Easy DPで解こうとして混乱して最終的にGreedyで解いて出してしまった。 Passed System Test(100.47pts)Medium DPということは分かったけど…
SRM359が存在しなかった。 また死亡。 結果 Easy(250) 243.77 Medium(500) Failed System Test Hard(1000) Compiled Easy 実装するだけ Imports Microsoft.VisualBasic Imports System Imports System.Collections Imports System.Collections.Generic Impor…
結果 Easy(250) 243.98 Medium(500) Compiled Hard(1000) Compiled Easy 実装するだけ Imports Microsoft.VisualBasic Imports System Imports System.Collections Imports System.Collections.Generic Imports System.Text Imports System.Math Imports Wei…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2012&lang=jp 考え方 x + y^2 + z^3 = e x + y + z = m の時のmの最小値を求める問題だが、z=t(定数)とすると x + y^2 = e - t^3 の時の、x + yの最小値を求める問題となり、 x>=0なら…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2011&lang=jp UnionFindを使って解いてしまいWAった。 考え方 各人が持ちうるマップを求めていく。実装(C++) #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <cctype> #include <ctime> </ctime></cctype></climits></cstdlib></cstring></cmath></cstdio>…
Hackのおかげで二桁順位。 オレンジコーダー復帰。 A 対称性から3^(n-1)になると思い実装。 提出。 Accepted(488点) B ". ","? ","! "で区切ってみる。 後は貪欲にメッセージを埋めていく。 Accepted(908点) C 解けなかった。 メモ:a/rev(a)=rev(b)/bD TLE…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2005&lang=jp パイプは両方向に対して建築が可能だと思いこんでいて何度もWAを出してしまった。考え方 中継点iから2つの路線に分岐したと考える。 すると、求める解ansは、全点対最短距…
時間があったので参加させていただきました。結果 Easy(250) Failed System Test Medium(500) 448.40 Hard(1000) 472.27 Easy id:atetubouさんの解法が凄いシンプルで良いと思う。 Failed System TestしたのはInStrの第一引数が1スタートであることを考慮し…
考え方 全ての支払い方を調べる。 「出した硬貨と同じ種類の硬貨が釣り銭として戻ってくるような払いかた」を避けるために、同じ枚数になる支払い方がある場合は合計金額が最も小さい物を選ぶ必要がある。 実装(C++) int value; int v[4]={500,100,50,10}; i…
考え方 前回押されたボタンとその回数を記憶する。 前回押されたボタンが'0'の時は何もしないようにする。 実装(C++) #include<iostream> #include<string> using namespace std; string btn[10]={"",".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; typedef pair<int,int></int,int></string></iostream>…
考え方 普通に指示通りに実装すれば答えを求めることが出来る。 が、それでは面白くないので蟻本を参考にBITを用いて書いてみた。(3/24追加) 実装(C++) #include <algorithm> #include <vector> #include <cstdio> using namespace std; struct BIT{ private: vector<int> bit;int size; publ</int></cstdio></vector></algorithm>…
AOJ用のテンプレート #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <cctype> #include <ctime> #include <cassert> #include <cwchar> #include <cstdarg> #include <cwctype> #include <queue> #include <stack> #include <algorithm> #include <list> #include </list></algorithm></stack></queue></cwctype></cstdarg></cwchar></cassert></ctime></cctype></climits></cstdlib></cstring></cmath></cstdio>
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2003&lang=jp A列車で行こうは名作。 考え方 新線の始点をA、終点をBとする。 新線と既存路線の交点をAに近い順に並び替える。 このとき他社路線なら高さを反転する。 Aの高さはAに一番…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2002&lang=jp 考え方 全ての物質が長方形であると仮定して、その全ての順番について、与えられた図と一致するものがあるか確認する。 一致するものが無ければSUSPICIOUSで、一致するも…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2001&lang=jp 考え方 入力を高さの大きい順に並び替え、入力通りに交換していく。 実装(Java) import java.util.*; public class Main{ public static void main(String[] args) { Scan…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2000&lang=jp 考え方 与えられる数値が対して大く無いので、シミュレートするだけで間に合う。 実装(Java) import java.util.*; public class Main{ public static void main(String[] …
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2243 考え方 最初に右足を置く場合と左足を置く場合があることに注意しつつ、 足の置き方が不正になる場合を数える。 実装(C++) #include <cstring> #include <cstdio> char in[100001]; #define x(ch) (</cstdio></cstring>…
Bを上手く書くことが出来なかった。 id:JAPLJさんが#1に続いて1位。凄過ぎる。 A 大きい素数(この問題では1を含む)を順に引いていく。 Accepted B 構文解析? 解けなかった。 C 実装してみる。 Accepted D 再帰を用いて構文解析する。 dostringなんて知らな…
死亡した。 C以降が難しかった回 提出コードはStandings - Codeforces Beta Round #62 - Codeforcesから A 実装するだけ。 ミスしたと思いこんでしまったために再提出してしまい得点が大きく下がってしまった。 Accepted(366点) B 二部探索。 あらかじめ作っ…
500回記念回。T-Shirt欲しかった。 提出コードはTopCoder Statistics - Room Statisticsから Easy 英文読解問題。 英文が読めればシミュレートすれば終了。 Passed System Test(92.80点)Medium Easyで時間を使い果たした。 OpenedHard Unopened Challenge Pa…
レン可愛いよ。 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2153 考え方 リンとレンの位置でBFSする。 片方だけが先にゴールに到着するようなことは無いということに注意する。 実装(C++) #include <cstdio> #include <cstring> #include <queue> #include <algorithm></algorithm></queue></cstring></cstdio>…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2151&lang=jp 考え方 現在居る宿屋と残りの所持金でBFSする。実装(C++) bool accessed[101][101]; typedef pair<int,int> Q; typedef pair<int,Q> P; int solve(Graph &G){ priority_queue<P,vector<P>,greater<P> > qu</p></p,vector<p></int,q></int,int>…
問題文の読解が少し難しかった。 でもそれなりに早く解けていて嬉しい。 得点:245.80/250 実装(VB.NET) Imports Microsoft.VisualBasic Imports System Imports System.Collections Imports System.Collections.Generic Imports System.Text Imports System…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2199&lang=jp 考え方 k番目の要素以降による二乗和はk番目以前の二乗和に対し独立なので、メモ化再起を行なう。 計算量はO(NM) 実装(C++) #include <algorithm> #include <vector> #include <iostream> #include <cstring> usi</cstring></iostream></vector></algorithm>…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2149&lang=jp 考え方 問題文に書かれている通りに実装する。実装(C++) #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <cctype> #include <ctime> #include <cassert> #include <cwchar> #include <cstdarg> #inclu</cstdarg></cwchar></cassert></ctime></cctype></climits></cstdlib></cstring></cmath></cstdio>…
あらかじめ用意しておいたGCDが正常に動かなかったため作り直してしまい時間がかかってしまった。 ライブラリが正常に動くかのチェックはちゃんとしないとだめだね。 得点:237.86/250 実装(VB.NET) Imports Microsoft.VisualBasic Imports System Imports S…
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2218 問題概要 略 考え方 Wikipediaに書いてあることを参考に実装する。 トランプをあらかじめソートしておくと楽に判定出来る。 実装(C++) #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #</cstdlib></cstring></cmath></cstdio>…
3/18現在のもの。 No C C++ Java 0100 pldw 260Hikaru 311nise_nabe 4250101 pldw 91Hikaru 169nise_nabe 2100102 pldw 174rankalee 327nise_nabe 3600103 pldw 111k_operafan 235nise_nabe 3020104 pldw 185k_operafan 312nise_nabe 4000105 pldw 240d17202…