AOJ2403

AOJ2403

2012模擬国内予選E問題

単純な枝刈りで充分
軍事力順でソートして、残りを全て取って現状の最大値を超えられるか見る


以下、本番で提出したコード

AOJ1251

AOJ1231

やるだけ。気合。

AOJ1263

AOJ1263

入力として与えられる隣接行列の対角成分以外は2以上なので、必ずスイッチを経由する。
まず頂点のどれかから辺を伸ばして、スイッチを1つ設置して木のルートと見る。
そうすると、ある頂点からある頂点へ移動するときにそのルートを経由する必要があるかどうかが判定できる。
経由しなくても行ける頂点同士には、ルートから新たに辺を伸ばしてスイッチを設置して同様の処理を繰り返す。

AOJ2033

AOJ2033

まず強連結成分分解する。
その後、連結成分を圧縮した森でルートとなっている頂点を探す。
その頂点に含まれる本来の頂点のどれかをそれ単体で作成する。

強連結成分分解のコードを描いたのがだいぶ昔なので、描き直したい衝動に駈られている。

AOJ2391

AOJ2391
JAGの春コンテストのC問題

両側からBFSする。
答えが45を超えるような入力は存在しないという制約があるので、
22ステップだけ両側から探索する。

とはいっても、N<=4のときはただのBFSで事足りる。

この実装だど、メモリがぎりぎり。
キューに入れる前に終了や打ち切りの条件を確かめる必要がある。キューから取り出したモノでやるとMELする。
どちらかでも23ステップやるとMLEする。

AOJ1163

AOJ1163

解くのは初めてではないんだけど、何となくフローを描いてみたくなったのでやってみた。

AOJ0570

AOJ0570
memo[桁数][最後に使った数][ここまでの余り][増加or減少][与えられた数より小さくなったかどうか]
筆算をする。
[与えられた数より小さくなったかどうか]はつまり、ここまで作った数字のプレフィックスが一致しているかどうか。
D桁目まで一致しているのであれば、次の数字は与えられた数NのD+1桁目以下でなければならない。
この制約があることで、ある数N以下で条件を満たす個数が分かる。
既に一致していない場合は、D+1桁目より大きな数を選んでもよい。

 (y - x + mod) % mod を忘れると答えが負になることがある。これで相当悩んだ。

EmacsからAOJにサブミットする

Emacs Lisp 初挑戦。
Emacs から Aizu Online Judge (AOJ) にサブミットする Emacs Lispを描いてみた。

AOJ1215

尺取