オンラインジャッジ

AOJ 1176 Planning Rolling Blackouts

問題文: Planning Rolling Blackouts | Aizu Online Judge 現在見ている区間の上下左右の端で状態数32^4くらいでメモ化再帰った。 漸化式とかよく分からないのでソースを見てください。 二次元累積和使うと早いヨ! 一番面倒くさいのは、その中でさらに予備電…

AOJ 1175 And Then. How Many Are There?

問題文: And Then. How Many Are There? | Aizu Online Judge 盤面の状態数は2^24である。それでDPすれば良い。ただ、AOJではcharじゃないとメモリオーバーになって死ぬ。 実装はDPよりメモ化再帰の方が効率的なのでそうした。 円と円の当たり判定は、 2つの…

AOJ 1174 Identically Colored Panels Connection

問題文: Identically Colored Panels Connection | Aizu Online Judge 問題文と戦うゲーム。 正しく問題を把握できて、バグを起こさないコーディングができりゃ勝ち! 左上をひたすら変えまくるのを全通り(6^5)調べるだけ。バックトラックでシミュレーション…

AOJ 1173 The Balance of the World

問題文: The Balance of the World | Aizu Online Judge stackにつんでいって確認していって、途中で矛盾が生じたり、最終的スタックが空になってなきゃno。 #include <iostream> #include <stack> #include <vector> using namespace std; int main(){ string str; while(getline(cin</vector></stack></iostream>…

AOJ 1172 Chebyshev’s Theorem

問題文: Chebyshev’s Theorem | Aizu Online Judge 素数やるだけ。エラトステネスとかしておく。 あと累積和作っておくと、(n,2n]に存在する素数が、O(1)で計算できる。正直必要ないけどなんとなく。 #include <iostream> using namespace std; int p[300001]; void in</iostream>…

AOJ 1131 Unit Fraction Partition

問題文: Unit Fraction Partition | Aizu Online Judge 汚いソースなんだよね。それ一番言われてるから。 自明な枝狩りをきちんと実装できるかが問題。 また k*(1/current) がp/qより小さい場合枝狩り。 ↑とくにこのへん あとオーバーフローに対する処理を手…

AOJ 0551 Icicles

問題文: Icicles | Aizu Online Judge なんか昔プライオリティキューを使って解くというのを見たせいでまったく解けなかった。頭悪い。。。 プライオリティキュー忘れて適当にメモ化再帰したら解けたっていう...。 しかもこっちの方が短いし早い気が。再帰だ…

POJ 1068 Parencodings

POJ : 1068 -- Parencodings 日本語: 1068 Parencodings - PKU Wiki* ひとつずつネストへらしながらうんぬん。 #include <iostream> #include <vector> using namespace std; int main(){ int T; cin >> T; while(T--){ int n; cin >> n; vector<int> d; int p = 0 , q; for(int i =</int></vector></iostream>…

AOJ Problem 1235 : Life Line

404 Not Found 問題文は↑を、と言いたいところなのですが僕は読めなかったので、 AOJ : 1235 - Life Line - Respect2Dの日記を参考にさせて頂きました。丁寧な説明本当に助かります。 まあやるだけなわけですが、cと同じ番号のを多めに引いて後で足すって形…

AOJ Problem 2069 : Greedy, Greedy.

404 Not Found 使える通貨の種類が与えられるので、それを使って支払えるものの判定をする。立体数とかどうでもいい。 Cannot pay some amountの判定 使える通貨の種類に"1"が無い。(1が無いと入力に無い素数とか絶対払えない。逆に1があれば何でも払おうと…

AOJ 0221 FizzBuzz

404 Not Found やっとこさAC。なんか、ずっと今回からの入力トラップによってWAだと思っていたんだけど、環状まわりのバグだったらしい。かなり悲しいよ。 #include <iostream> #include <algorithm> #include <sstream> #include <cstdio> #include <vector> using namespace std; bool fizzBuzzCheck(int </vector></cstdio></sstream></algorithm></iostream>…

パソコン甲子園2010予選問題がAOJに

うpられたのでSubmit。 結果としては、前回ブログに載せたソースだと、6と9がWA,10がTLE出した。6は本選で通った解法が通らなくてAC率大変なことに。 よって9を書き直したら、順列とか使う必要がなくて、単純に負辺をたった一度だけ通れるようにしたdijkstra…

AOJ Problem 1030 : Cubes Without Holes

404 Not Found ← 問題文 なんか問題内容の割に正答率低い問題。何か落とし穴があるのだろうか。自分は気づかずACできた。 ホントやるだけ。500^3は一億超えちゃうので三次元配列とか用意すると死ぬと思う。setで節約 + 重複除去で一石二鳥。 #include <set> #incl</set>…

AOJ Problem 1046 : Ghost Buster!

404 Not Found ← 問題文 パソコン甲子園2010の双子のソースを改変したレベルの解法。ソースが溜まっていくとこういうことが出来るから良い。 確定ノード情報のために五次元配列を確保したけど、初めて使ったよ5次元配列とか・・・。 #include <iostream> #include <vector> #in</vector></iostream>…

AOJ Problem 1217 : Family Tree

404 Not Found ← 問題文 木構造が与えられた後に、関係を表す命題が与えられるので、真か偽か判定する。 解くにあたっては、各ノードの親の情報だけあればいい。なぜなら、 X is a child of Y. → Xの親がYである。 X is the parent of Y. → Yの親がXである。…

むぅ。

404 Not Found を解いていて久々にリアルに紙を使った。 1.最初に置くロールケーキの中心座標は、箱の左端をx座標の0、床をy座標の0だとして、である。 2.どのロールケーキもy座標は床からの高さである(問題文から)。 3.よって、判明していないのは、片方の…

AOJ 0122 Summer of Phyonkichi

404 Not Found ピョン吉の夏。パソコン甲子園2005過去問。 とりあえず実装方法誤ると大変なことになることが予想される探索でした。探索だったら何でもいいと思う。 WA出しまくった。原因は 上限が10固定だと思って定数指定してた nコ目(最後の撒水機)から1…

AOJ 0170 Lunch

404 Not Found nは高々10なので順列で生成してもいいんだろうけど360万ループ*重心とかの判定計算とかは効率化しないとTLEしそう。 ということでバックトラック解法 #include <iostream> #include <vector> using namespace std; vector<int> choice; string name[10]; int weight[1</int></vector></iostream>…

AOJ Problem 0072 : Carden Lantern

404 Not Found Prim法(全域最小木) + オマケに植木算。以前やったウォーターデブンのソースと似た感じ。 #include <iostream> #include <set> #include <algorithm> #include <climits> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i</cstdio></climits></algorithm></set></iostream>

AOJ Problem 0086 : Patrol

404 Not Found もろ始点・終点が決まったケーニヒスベルクの橋渡りだった。 注意しなきゃいけないのはスタートまたはゴールから伸びている辺の数が1本以外のケースもあるということ。 適当実装 #include <iostream> using namespace std; int main(){ int a,b; while(1</iostream>…

AOJ Problem 0155 : Spider Jin

404 Not Found 全点間のユーグリッド距離求めてから50以下のものだけを辺として追加し、ダイクストラ。 最近番号が不規則に振られるからってmapで管理するのは非効率的だということに気づいた。コーディングスタイルを見直そう。 #include <iostream> #include <cmath> #inclu</cmath></iostream>…

AOJ 0212 Highway Express Bus

404 Not Found 解けるようになっててビビった。先輩ん家で解説された時何となく言ってることは分かるけど、実装方法とかチンプンカンプンだったのに。 「ネタ(アルゴリズム)」を持っていると強いです。 クソ最適化されてない害クストラ #include <iostream> #include <queue> </queue></iostream>…

AOJ 0180 Stellar Performance of the Debunkey Family

404 Not Found Prim法(全域最小木)そのまま。前知ったアルゴリズム。 非常に単純で、『プリム法(最小全域木問題)』を読めば単純明快です。 ノード情報は隣接行列で実装。 #include <iostream> #include <list> #include <algorithm> #include <climits> using namespace std; #define rep(i,n) </climits></algorithm></list></iostream>…

AOJ 0178 TETORIS

404 Not Found 簡易テトリスで安心した。大体ビットを使って表現。 なんとなくサイズ5の縦棒が大量にきた場合も溢れないように、配列のサイズ5000くらいにした。 bitはビットが立ってる本数を数える関数。最下位が63なのは消えない番兵として。 #include <iostream> #i</iostream>…

AOJ 0193 Deven-Eleven

404 Not Found なんか1時間くらい掛かって、超スパゲッティソースになって、 添え字とか意味不明だけど一発Acceptきたこれ。 内容としては幅優先にいろいろつけたかんじ。ボロノイ図的なサムシング マスの入力毎に 全てのマスに対して幅優先探索かけて、最初…

AOJ 0526 Boat Travel

404 Not Found JOI過去問。昨日くらいに解いた。経路情報管理には隣接行列を用いるのが楽。 問題文読んでからコーディング時間計測開始、全力の高速実装で10分強+くだらないバグ見つけるのに20分くらい掛かった。 いろいろと無駄の多いソース。dijkstra。 #i…

AOJ 0144 Packet Transportation

404 Not Found BFSで解いて、学校に出すレポートそれで書いた後にワーシャルフロイド法で解けるじゃんって気づいた。死しかない。 辺の重みが1均一。 BFSソース #include <iostream> #include <queue> #include <map> #include <climits> using namespace std; #define rep(i,n) for(int i=0</climits></map></queue></iostream>…

AOJ 0117 A reward a Carpenter

404 Not Found 最短経路出力する問題だと思って、それだとワーシャルフロイド法だと困るよなぁとか思ってダイクストラで解いて、提出した直後にただの最小コスト求める問題だったということに気づき絶望。 結局初めてやったダイクストラ法では必死にがんばっ…

AOJ 0110 Alphametic

404 Not Found 落とし穴:まさかの多倍長 多倍長マジ死ぬべき。先輩に言われるまで気づかなかった。何でWrong出るのか分からなかった。 スパゲッティソース、pls()で簡易多倍長足し算してる。筆算の仕組み。効率的な書き方誰か教えて。 #include<iostream> #include<vector> #in</vector></iostream>…

AOJ 0041

404 Not Found 超強引に解いた。かっこでくくるパターンを絞ってみたら5パターンしか無かった。 オペレータの順列生成で3倍無駄があるけど間に合う。擬似的に重複組み合わせ再現する。 #include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; int an</cstdio></algorithm></vector></iostream>…