AOJ

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 なんか昔プライオリティキューを使って解くというのを見たせいでまったく解けなかった。頭悪い。。。 プライオリティキュー忘れて適当にメモ化再帰したら解けたっていう...。 しかもこっちの方が短いし早い気が。再帰だ…

AOJ Problem 0132 : Jigsaw Puzzle

本文:404 Not Found 「超 大 作」。 枝狩りがうまくできなかったので先輩の手助けなどを借りた。とっても感謝。 とりあえずしたこと。気が狂う感じだった。 入力制約よく分からないので色々対策 まあ当然元々の'.'とパーツの'#'の個数照合して不一致だったら…

AOJ Problem 1235 : Life Line

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

AOJ Problem 0187 : Stoning Fortune

AOJ

問題文:404 Not Found ライブラリゲー。ccwやintersectSS,crosspointはspaghetti sourceのもの。 本選でのこれの配点があんまり高くないのは悲しいよね。 気をつけるべきは「0,0,0,1」とかの入力を見逃さないこと。 #include <iostream> #include <vector> #include <complex> using nam</complex></vector></iostream>…

AOJ Problem 1140 : Cleaning Robot

AOJ

問題文:404 Not Found 幅優先探索 + 巡回セールスマンな問題。 先に汚れ同士の最短経路を計算しておけば10!解法でも通るかもしれない。 巡回セールスマンの実装の軽さは異常。 #include <iostream> #include <queue> using namespace std; #define rep(i,n) for(int i=0;i</queue></iostream>

AOJ Problem 0190 : Eleven Puzzle

AOJ

問題文:404 Not Found 両側探索とかしてもメモリ死ぬしTLEするんで適当に枝狩しましょう的な問題。 「正しい位置との距離+現在にたどり着くまでのコスト>20」で枝狩した。前やったとき両側探索で死んだ。正しい0の位置は考慮せずに枝狩して通った。(むしろし…

AOJ Problem 1202 : Mobile Phone Coverage

AOJ

404 Not Found 円とか与えられるけど、円とかほとんど関係なくて重なる正方形の面積求めるだけの問題。 超絶嘘解法。本当は座標圧縮とかするらしい。こういうのもアリかな? x軸を細切れにして、細切れを線分として見ていろいろしたらなぜか通ってしまった。 …

AOJ Problem 1166 : Amazing Mazes

AOJ

問題文:404 Not Found フォーマット弄って幅優先でやりました。これが一番楽だと思った。 フォーマットうけつけが問題な問題。勝手に盤面拡大してるので、出力するのは/2したりしてゴニョる。 迷図と命ず[Amazing Mazes](渾身のギャグ) こんなイメージ↓ #inc…

AOJ Problem 0234 : Aizu Buried Treasure

AOJ

すごくたすかる助言によって通ったので書きます。 >o は 3 以上 m 以下の整数とします このときなぜか2以下が含まれてる だそうなので、これだけ対策したら通りました。 問題文:404 Not Found さて本題。 H,Wは<=10以下ですが、掘った箇所を記録する際、2^(…

AOJ Problem 0105 : Book Index

AOJ

ノリでC言語で書いてみた。あらためてC++最強だとおもった。連想配列すごい。 no title めちゃくちゃなコード書きまくったのに大体バグらなかったのが嬉しかった(小学生並の感想) #include "stdio.h" #include "string.h" #define min(a,b) (a

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>…