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