2012-01-01から1年間の記事一覧
自分の実力がどれくらい向上しているのか自分でわからないので2011年5月から2012年12月16日までのコンテストについて時系列順に振り返ってみる。「参加人数」は0より大きい点数を取った人数を参加人数として扱い、「上位何%か」のところには(自分の順位)÷(参…
前回の記事「JavaScriptでデータ構造を実装したい！ (基本編)」ではJavaScriptでデータ構造を実装するために必要な知識をまとめたので、今回は実際にJavaScriptでスタック・キュー・ヒープを実装してみます。まずはスタック・キューの実装ですがJavaScriptの…
前回の記事「JavaScriptで競技プログラミングを始めよう！」ではJavaScriptで競技プログラミングするために必要な知識やデバッグの方法をまとめました。しかし、プログラミングコンテストでより難しい問題を解くときには使い勝手の良いスタック・キュー・優…
これは，Competitive Programming Advent Calendar Div2012の17日目の記事です．はじめに競技プログラミングといえばC++, Javaなどの言語を使う人が圧倒的に多かったのですが、最近は会津オンラインジャッジやAtCoderなどでC#, D言語, Ruby, Python, PHPなど…
問題A:GPA計算N文字の文字列rが与えられ,r[i]が評価を表しています。評価'A', 'B', 'C, 'D', 'F'の5種類があり、それぞれ4,3,2,1,0点です。評価を点数に換算して平均を求めます。評価は'E'でなく'F'となっているので気をつけましょう。また誤差は1e-9まで許…
AtCoder Regular Contest #002問題A:うるう年うるう年かどうか判定する問題です。うるう年の規則については問題文に記述されているのでそれを見てプログラムを書くとよいでしょう。 #include <iostream> using namespace std; bool is_leap(int y){ return ((y % 400 =</iostream>…
AtCoder Regular Contest #001問題A:センター採点N文字の文字列で一番出現回数が多いものと一番出現回数が少ないものを出力します。文字は'1', '2', '3', '4'の4種類しかありません。max,minを使っても良いですが, max_element, min_elementを使うとちょっと…
模擬国内予選2012がありました。3問解いて42位でした。本番は4問解けるように頑張りたいと思います。最初の20分くらい繋がらなくて問題文が見られないというアクシデントがありました。 問題B,Cはもう少し早く解けないとまずいなあ、と思いますが3問とも一発…
問題文 N*Nの行列で行の中で最大で、列の中で最小のものを求める問題です。 そのような要素がないときは0を出力します。 #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; typedef pair<int,int> P; int main(){ int n; while( cin >> n , n ){ // m[y]</int,int></algorithm></map></vector></iostream>…
問題文 整数v, dが与えられます。 v個のノードがあり番号が1..vまで付けられています。ノードiとノードjについて|(f(i)-f(j)) mod 1001| 異なる集合の数を求めます。Union-Findを使うと良さそうな問題でした。 #include <iostream> #include <algorithm> using namespace std; con</algorithm></iostream>…
問題文 史跡と史跡の間に灯篭を100m間隔でおき、すべての史跡がつながるようにしたとき、必要最小限の灯篭の数を求める問題です。灯篭の数をコストと考え、史跡と史跡の間に灯篭をおくとき((史跡と史跡の距離)-100)/100が必要なコスト(灯篭の数)となります。…
問題文 1から9の整数a,b,c,dと演算子+,-,*を使って10になる式を探して出力する問題です。 4つの数字の並び替えが4!=24通り 3種類の演算子を3箇所につかうので3*3*3=27通り括弧のつけかたは( (a+b)+(c+d))と(((a+b)+c)+d)と*1+d)の3通りを試しましたが通りま…
3/13(火)-3/15(木)の3日間行われた立命館プログラミング合宿に参加しました。 レベルが高い人たちがたくさんいていい刺激になりました。たくさんの人とお話できて楽しかったです！1日目@Respect2Dさんと@Darseinさんとチームotaks2Dとして参加しました。 私…
問題文 x,y,zがそれぞれ何回で1に戻ってくるか計算し、その回数をa,b,cとするとa,b,cの最小公倍数が答えになるようです。long int(32bit)ではオーバーフローするので注意が必要です。 #include <iostream> using namespace std; typedef long long int ll; ll gcd(ll a</iostream>…
問題文 覆面算の問題です。Xの部分に0-9のどれかの数字が入るので10通り調べるとよいです。数値に変換するとオーバフローするので文字列のまま足し算しましょう。多倍長整数が標準で存在する言語だと楽ができることでしょう。 #include <iostream> #include <string> #include <algorithm></algorithm></string></iostream>…
問題文 入力された整数nに対しnグラムのそば粉を買うときの最小の金額を求める問題です。入力される範囲が[500,5000]と小さく、すべて100の倍数なので初めに計算しておくとよいです。 #include <iostream> #include <algorithm> using namespace std; const int INT_MAX = 1e+7; i</algorithm></iostream>…
問題文 1,2, ... , NのチーズがN個あり、1から順に食べるとき全部のチーズを食べるのに必要な最短経路を求める問題です(Nは9以下)。必ず全てのチーズが食べられることが保証されているようです。またフィールドの幅と高さw,hは1000以下となっています。幅優…
問題文 探索する必要はなくシミュレーションする問題です。 毎回下端に届いたパッケージの記録からpush_down 命令かpush_right 命令をするか判断します。 最終的に上のラインと左のラインが空になったら右のラインに届いた順に出力します。 今回は文字列でデ…
問題文 n以下で最大の双子素数を求める問題です。エラトステネスのふるいであらかじめ素数を求めておきましょう。 #include <iostream> using namespace std; const int MAX = 100001; char p[MAX] = {0}; int main(){ for(int i=2 ; i < MAX ; i++ ) p[i] = 1; for(in</iostream>…
問題文 AN個の戦闘機とBN個の敵弾があり、それぞれの戦闘機について距離が4*R以内にある敵弾を数える問題でした(距離は戦闘機の中心座標から敵弾の中心座標までの距離で計算)。AN,BN 各戦闘機について自分のいる区画とその周囲8区画だけ調べるようにすると調…
問題文 A = {a[1] , a[2] , ... a[n] }について 回数が|A|/2より多く出現する数字を出力する問題です。(|A|は要素数) #include <iostream> #include <map> using namespace std; int main(){ int n, a; while( cin >> n , n ){ map<int,int> m; for(int i=0 ; i < n ; i++ ){ cin >> </int,int></map></iostream>…
問題文 全探索で解ける問題です。幅優先探索でも深さ優先探索でも解けると思いますが、今回は深さ優先探索で解きました。同じ状態を再び探索しないようにメモしながら探索しました。2枚のカードを取り出したときカードを移動させる処理が少し煩わしいと感じ…
問題文 [1,n]のうちa*i+b*jで表せない数が何個あるか数える問題です。入力a,b,nは10^6以下の整数でi,jは非負整数です。動的計画法で解ける問題でした。dp[x] := 整数xをa*i+b*jで表すことができるかどうか(0 or 1)で計算しました。dp[0]を1で初期化し、iを0…
問題文 DPで解く問題です。ボードが数字であるとき、その数字の後ろに右か下の位置の数字をつなげることができます。dp[y][x]にボードの(x,y)の位置からつくることのできる最大の数字が入るように計算していきます。右下からDPテーブルを埋めて行きましょう…
