テキトーなメモ帳

テキトーなメモ帳

AOJ:1224 Starship Hakodate-maru

全探索です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include </set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1257 Sum of Consecutive prime Numbers

全探索です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include </set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1241 Lagrange's Four-Square Theorem

動的計画法です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include …</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1240 Unreliable Message

変換を全て逆方向にして(例えばMr.Jの「左に全て1文字ずらす」なら「右に全て1文字ずらす」にする)、 出力から入力へ変換していきます(例えばサンプル1ならaB23dにはPMJAの順で変換を掛ける) #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #incl…

AOJ:1210 Die Game

ただのシミュレーションです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #in…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1202 Mobile Phone Coverage

x,y,rを各々100倍して整数化した後、さらにx,yに20000を足して 必ずx,yが非負の値に成るようにします。 その後、ステージを100*100の領域の集合として捉え、ある100*100の領域が アンテナの電波で覆われている場合は、そこに印をつけておきます。 さいごに、…

AOJ:2409 Power

区間スケジュール問題。 貪欲法で解きました。 ある複数の(ひとつの)部屋を守りたい時に、 複数の教授を使える時は、権力の及ぶ部屋番号の数字の大きい(bの値が大きい)教授を優先的に選んでいけば良いです。 #define _USE_MATH_DEFINES #define INF 100000…

AOJ:2410 Janken

はじめに期待値をとって、最強の一手を出し続ける戦法では負けてしまいます。 そこで、50回ごとに期待値をとって目標点数350点に届きそうにない場合は手を変えるようにしました。 しかし、これで勝てるという根拠はゼロです・・・ #define _USE_MATH_DEFINES…

AOJ:2408 Social

mapを使うと楽です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <cstdio> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #includ…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></cstdio></iostream>

AOJ:2407 Simple Othello

oのが連続している箇所の個数がxの連続している箇所の個数以上ならoの勝ちです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <cstdio> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #incl</string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></cstdio></iostream>…

AOJ:2406 Al dente

問題文のとおりにやるだけです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <cstdio> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #in…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></cstdio></iostream>

AOJ:1201 Lattice Practices

バックトラックです。 非常に長いコードになってしまいました。 縦棒→横棒→縦棒・・・の順に左上から右下へ向かってラティスを組んでいきます。 ラティスを組む操作ごとに、接合点が正しいかどうかを判定して、枝狩りしていきます。 プログラム中のstate変数…

AOJ:1209 Square Coins

動的計画法です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include …</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1200 Goldbach's Conjecture

久々のエラトステネスの篩です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #i…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1116 Jigsaw Puzzles for Computers

バックトラックです。 if文による場合分けが酷いです。 012 345 678 の順にパズルを埋めていきます。 パズルを埋めていく各々の操作において該当ピースの接合点が正しいかどうかの判定を行います。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #inclu…

AOJ:1107 Spiral Footrace

arctanを使って(回転方向がどっち向きかわかるから) 人間の向いている方向の方向ベクトルと 現在の点と次の候補地点との方向ベクトルとの回転角をだします。http://www5d.biglobe.ne.jp/~noocyte/Programming/Geometry/RotationDirection.html#GetAngle の…

AOJ:1121 Kanglish:Analysis on Artificial LKanglish:Analysis on Artificial Language

mapにアルファベット2文字で構成されるkanglishの文字を保存しておきます。(キーはその接頭辞) そうすると、文中のあるアルファベットを走査している際に mapにキーが見つかった→2文字のkanglish文字かもしれない→2文字かチェック mapにキーが見つからな…

AOJ:1106 Factorization of Quadratic Formula

全探索です。ただし、 p = a/r q = c/s を利用してオーダーをに減らします。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #includ…</string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0232 Life Game

動的計画法です。 dp[pos][coin] := 位置posでcoin円を持っている確率 としていきます。 最後にpos=Yの時の期待値を算出します。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:0244 Hot Spring Trip

ダイクストラ法です。 cost[現在位置、券を使ったエッジの番号] にコストを保存していきます。 券を使っていない場合は、券を使ったエッジの番号は(-1,-1)となります。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #i</sstream></iostream></cstdio>…

AOJ:0243 Filling Game

ダイクストラ法です。 ステージを一次元化するとコストを保存しやすくなります。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #inc</string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:0242 Input Candidates

WA連発してしまいました。 どこが間違っていたのかわからない・・・ #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring>…</cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0241 Quaternion Multiplication

問題文中で与えられている表は 多項式を展開した時の係数の位置(1,i,j,k)とその符号(-,+)を示していると考えます。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #i</stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:0240 Interest Rates

問題文どおりにやるだけです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #in…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0239 Calorie Counting

構造体を使うと楽です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #inclu…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0238 Time to Study

問題文通りにやるだけです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #inc…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0215 Pachimon Creature

ダイクストラ法で解きました。 実行時間は4.7s。ギリギリでTLEしません。 遅さの原因はたぶんmapかな・・・ はじめ、 各属性のパチクリの数はそれぞれ 0 以上 1000 以下の整数とします。 を パチクリの数はそれぞれ 0 以上 1000 以下の整数とします。 と「各…

AOJ:1180 Recurring Decimals

stoiを使ってstring→int変換すると楽です stoiってC++11じゃないと使えないんですね。 知りませんでした。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #</map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1179 Millennium

(1年1月1日からミレニアム記念日までの経過日数)-(1年1月1日から誕生日までの経過日数) で「誕生日からミレニアム記念日までの経過日数」が求まります。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #inc</cstdlib></cmath></sstream></iostream>…

AOJ:1161 Verbal Arithmetic

next_permutationで全探索→TLEというわけで、両側探索で解きました。 下記のサイトを参考にさせていただきました。 http://d.hatena.ne.jp/kkishi/20090707/1246930309 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #inc</cmath></sstream></iostream>…

AOJ:1103 Board Arrangements for Concentration Games

DFSで全探索です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> #include …</deque></set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1111 Cyber Guardian

問題文の通りに判定関数を作るだけです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> …</deque></set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1110 Patience

ステージを一次元の配列(string型の文字列)で管理すると、ステージを詰める操作が楽になります。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1175 And Then. How Many Are There?

DFSです。 任意の2枚の円盤が取り除けるかの判定関数の実装が若干面倒かな? #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include </cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1150 Cliff Climbing

ダイクストラ法です。 といっても、はじめDFSで解いてTLEを起こしてしまいました。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #in</cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1127 Building a Space Station

プリム法です。 ただし、自分でコストの隣接行列を作ってあげないといけないです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #in</cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1149 Cut the Cakes

ケーキの切れ端の情報をクラスで管理していくと楽です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1138 Traveling by Stagecoach

ダイクストラ法です。 cost[現在位置][今までに使った券の情報]にコストを記録していきます。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #in</string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1132 Circle and Points

分割統治法です。 プログラム・プロムナードに詳しく書いてあります。 http://www.ipsj.or.jp/07editj/promenade/4511.pdf #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #inclu</stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1136 Polygonal Line Search

sin(i*90.0*(M_PI/180.0)) とするべき所を sin(i*90.0) としてしまいました。 気がつくのに時間がかかった・・・ 回転については 比較元の図形(L0)の0,90,180,270度回転の4パターンを予め用意。 比較先(L1~Ln)の各々とさっき用意した4パターンを比較してい…

AOJ:1167 Pollock's conjecture

動的計画法です。 計算量が10^12で確実にTLEの様に見えますが、うまい具合に枝狩りされるみたいです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #incl</map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1174 Identically Colored Panels Connection

DFSで全探索です。 もっと綺麗に書けそう。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include </set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1140 Cleaning Robot

巡回セールスマン問題というよりは 幅優先探索の際に cost[現在のマス][すでに訪れた汚れたマスをビットで管理したもの] に最小のコストを記録していく感じです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib></cstdlib></cmath></sstream></iostream>…

AOJ:1131 Unit Fraction Partition

DFSです。作り出したい分数をAとすると A=1/B+1/C+1/D+... (B となることに注意です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include </string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1119 Exploring Caves

問題文通りにやるだけです。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> #inclu…</deque></set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1166 Amazing Mazes

入力をノード(座標)間のコストを記したグラフに変換→ダイクストラ法です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set></set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1156 Twirling Robot

メモ化再帰でいけるのかなあ→TLE 結局、ダイクストラ法で解きました。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1114 Get a Rectangular Field

全探索です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> #include </deque></set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>

AOJ:1126 The Secret Number

動的計画法です。 dp[y][x]:座標(x-1,y-1)を数字列の終端とした時の最大の値 とします。ゼロの処理に注意です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #inclu</limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>…

AOJ:1155 How can I satisfy thee? Let me count the ways...

再帰下降構文解析です。 #define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> #include…</deque></set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream>