問題文 正整数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[現在の頂点][直前の頂点] := 最小時間 となるようにダイクストラ法をします。二点間の距離と角度の計算(内積を使う)ができれば解けるかと思います。スタートとゴールが同じケースや直前に来た道に戻る時に…