AOJ埋め

簡単な問題をたくさん解いた。

2021 : 姫血液の問題。memo[ノード][冷凍残り時間]でdjikstra
1145 : ゲノム文字列の問題。構文解析. 長さがインデックスになるまで解凍する感じ。
1138 : 馬車チケットの問題。memo[ノード][持ってるチケット]でdijkstra
1140 : 掃除ロボットの問題。bfsで各汚れ間の距離を出して10!通り試す。
1136 : 折れ線を探す問題。回転したやつとかを全部探索するだけ。回転は虚数掛けると楽
1127 : 宇宙ステーションの問題。最小全域木やるだけ。
2399 : プライバシーを守る問題。やるだけ。
2019 : 姫が護衛を雇う問題。貪欲法。
1165 : 角角画伯の問題。やるだけ。
2151 : 姫が護衛を雇う問題。memo[ノード][残り予算]でdjikstra
2402 : 星間ダイクストラの問題。五角形にして星同士の距離やってdijkstra
2182 : Eleven Loverの問題。なめるだけ。
1189 : 素数洞窟の問題。メモ化探索。
1187 : ICPCのランキング付けの問題。プレディケート書いてソートするだけ。
2014 : WとBの柵の問題。やるだけ。
1335 : 漸化式立ててメモ化。漸化式考えるの楽しかった。
2007 : お釣りを渡す店員が親切な問題。持ってる金全部渡してみるというのがわかれば楽
2012 : 宇宙ヤシガニの問題。探索の順番。
1142 : 列車の文字列の問題。やるだけ。
1125 : できるだけ沢山木をとる問題。英語読むだけ。
1137 : ローマ数字の足し算の問題。YARUDAKE.

こんな問題がDとかに来てていいのかよ、って感じの問題が散見された。

AOJ 2182 : Eleven Lover

問題:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182

解法:

11の倍数は
偶数桁目の和 - 奇数桁目の和 ≡ 0 (mod 11)
で判定できる。
そこで、F[i][j] = 0からk桁目まで「先頭から足し引きを交互にして11を法としてjになる」ようなkの個数(k<=i)
とすれば良い。
ただし0-leadingは許さないので、string[i+1]='0'ならばF[i][j] = 0にする。

ソースコード:

https://gist.github.com/knewknowl/a31bbb3cc1a625a0989a

AOJ 2586 : 流れ星に願いを

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2586
空間上にn個の球がある。
それぞれの球は速度(vx,vy,vz)で移動し1秒でvrだけ半径が減少し、
二つの球が接触もしくは半径<=0になったらその球は消滅する。

それぞれの球が消滅するまでの時間を求めよ。

解法

まず二つの球が接触するかどうかを判定するために球iと球jのt秒後の距離をf(t)とおくと
f(t)は下に凸な関数になっているので三分探索を使って極小値を求める。この極小値が0以下ならば二つの球は接触するので、極小値を与えるtと0との間で二分探索をすれば良い。

こうすれば接触時間と消滅時間がわかるので、それらの時間をソートして最初に起こるイベントから順に処理していけば良い。

・・・よく考えたら接触時間は二次方程式になるので三分探索する必要はなかった。

ソースコード

https://gist.github.com/knewknowl/9913126a26b210230e4d

AOJ 2584 : Broken Cipher Generator

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2584

解法

?がついてるところはAにすれば良い。あとは愚直に構文解析するだけ。
構文解析のやり方は
https://gist.github.com/draftcode/1357281
がすごくわかりやすくて良いと思います。

ソースコード

https://gist.github.com/knewknowl/98ba3331fc465b42416c#file-brokenciphergenerator-cpp

AOJ 1196 : 橋の撤去

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196
簡単に言えば木が与えられてどっかのノードからスタートして全ての辺を取り壊していく話。

解法

どの辺を何回通るか、というのを考えると、葉とつながってる辺は1回、普通の辺は行きと帰りと撤去で３回、スタート地点とゴール地点によっては行きと撤去の２回、の３通りがある。
２回の辺をできるだけ多くしたいけどこれの最大値=木の直径*2
になっている。
木の直径は簡単に求められる。

AOJ 1195:暗号化システム

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1195&lang=jp

解法

インクリメントするのは2^n通りくらいあるから全試しすれば良い。

AOJ 1194:バンパイア

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1194&lang=jp

解法

二分探索。

ビルのx座標が整数値でしかも絶対値が20以下なので

H[i] = 区間[i,i+1]のビルの最大値

とおいてt秒あとの区間[a,a+1]の太陽の高さを求めてかぶってるかどうかを判定すれば良い。

AOJ 0225

Kobutanukitsuneko

問題:

n個の文字列が与えられたときにそのn個全部を使ってしりとりのループを作ることが出来るかどうかを判定する問題。

解法:

アルファベットをノード、単語をエッジと見て各単語の最初と最後の文字のアルファベットノードに有向枝をはったグラフを作り

・グラフが連結かどうか

・オイラーグラフかどうか

を判定すれば良い