問題文 正整数w, h(1 解のW, Hはともに150以下であることが保証されているので1以上150以下でH ペアの比較はC++ならpairを使うと最初から比較が辞書式順序になっているので楽です。 #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; typedef p</algorithm></map></vector></iostream>…

問題文 模擬国内予選2012問題Bとよく似た問題でコンテストの提出履歴が与えられた時にICPCルールで順位付けをしてチーム番号を順位の高い方から出力します。C++なら比較関数を用意してソートするとよいです。この問題では順位が同一のときには、それらのチー…

問題文 括弧の始まり('[')が来たときに再帰呼び出しをしてその括弧の始まりに対応する括弧の終わり(']')が来た時にその選挙区で必要な最小の得票数を計算してその結果を返せばよいです。 第 1 段階の有権者数で必要な最小の得票数は有権者の過半数の票なので…

問題文 1から m まで(1 素数の個数が最大の経路を求め, その個数と最後に通った素数を出力します。ある整数が素数かどうかO(1)で判定できるようにエラトステネスの篩等で最初に素数を列挙しておきます。次に螺旋状に数字を書きます。バグりやすいので気をつ…

問題文 一つの杭と紐に注目したときに風船が動ける空間は球になっています。(正確にはzn個の杭と紐につながった風船が動ける空間はそれぞれの杭と紐について注目した時に動ける空間の共通部分となっていて、その形は凸になっています。(球は凸集合で、凸集合…

CODEVS2.1決勝詳細7/21(日)にCODEVS2.1の決勝を観戦しに東京に行きました。 体力的にも金銭的にもあまり余裕がなくて自宅でニコ生観戦する予定でしたが、予選成績がSILVER(30位以内)の人にも交通費が出るということで会場に行くことにしました。CODEVS TOTO…

合同練習会3のC++のコードを問題ABCDEFGまで書きました。ぜひ参考にしてください。解法については、練習会に参加した人は解説をもらっているはずなので適当に省いています。いけあさんが問題Gまでまとめているのでぜひこちらも参考にしてください。(コードは…

問題文(ACM-ICPC Live Archive) 解法BFS(幅優先探索)です。最短距離更新のときにキューに入れるのと経路数の更新をして、最短距離と等しいときは経路数の加算をしています。コード(C++) #include <iostream> #include <queue> using namespace std; const int dx[4] = {0,1,0,</queue></iostream>…

問題文(ACM-ICPC Live Archive) 解法DFS(深さ優先探索)です。12個の数字の合計が3の倍数にならないときや直線4つの数字が3の倍数にならないときに枝刈りできます。数字が全部異なるため回転・対称のものは全部で12通りあるので、重複して数え上げて最後に12…

問題文(ACM-ICPC Live Archive) もとのこの問題は小数点以下2桁出力していますが、練習会では出力形式が小数点以下4桁の出力に変更されています。解法DP(動的計画法)です。dp[i][j] := i番目の区間のj番目のレーンにたどり着く最短距離 となるように計算しま…

問題文(POJ 3087) 練習会では入力形式が少し変更されているので上記のオンラインジャッジで正解するには入力部分のコードを少し書きなおす必要があります。(POJではテストケースの番号+解を出力する)解法問題文のとおりに実装しましょう。またいままで訪れた…

問題文(TJU 3098) 練習会では入力形式が複数テストケースに変更されているので上記のオンラインジャッジで正解するには入力部分のコードを少し書きなおす必要があります。解法全探索しましょう。C++ならmax_elementを使うと少しコードが短くなります。 コー…

問題文(COJ 2282) 解法解説に書いてあるので省略。コード #include <iostream> #include <vector> #include <map> #include <queue> #include <algorithm> using namespace std; typedef pair<int,int> P; const int INF = 1e+8; const int dx[4] = {0,0,-1,1}; const int dy[4] = {-1,1,0,0}; int w, h, n; // </int,int></algorithm></queue></map></vector></iostream>…

問題文(BNU Online Judge) 解法グラフを作成してdp[現在の頂点][直前の頂点] := 最小時間 となるようにダイクストラ法をします。二点間の距離と角度の計算(内積を使う)ができれば解けるかと思います。スタートとゴールが同じケースや直前に来た道に戻る時に…

自分の実力がどれくらい向上しているのか自分でわからないので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>…