AOJ 2200 : Mr. リトー郵便局

Mr. Rito Post Office | Aizu Online Judge

船をどこに置いておくかで結果が変わっておきそうなので、
これを状態に持ってDPするのが良さそう。

あらかじめ陸路と海路で分けてワーシャルフロイド法で
各町村間の最短経路を求めておく。

DPするときは船は放っておいて陸路を使い目的地へ移動する遷移と
1~nに今あるところから船を移動させて目的地へ移動する遷移をする。

状態-値はdp[どこに船を置いたか][何番目まで集荷したか] := 最小コスト
で持っておく。

O(M + N^3 + RN^2)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2367010#1

AOJ 2747 : カーテン

カーテン | Aizu Online Judge

素直に実装しても良いが大変そう。
どうしても頂点の数に左右されてしまうので、
どうせだったら座標圧縮をして1x1の正方形について考える。
すると一気に楽になる。

例えばサンプルケース3つ目(問題文に図として紹介されているもの)だと、
以下のようになる。

f:id:arukuka:20170613054722p:plain

窓に内包され、かつカーテンに内包されていないとき、
圧縮した座標を元に戻して足していく。
その合計が答え。

内外判定に外積を使おうとしたが
凹多角形については通用しない。
高専プロコンのときに勉強した
以下のページを参考に実装した。

www.nttpc.co.jp

AC

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2366488#1

とは言えど、この内外判定が想定されているような気がしない。
解説を見ると

点と多角形の内包判定は判定したい点から無限に伸びる半直線を考え,
その半直線と多角形の線分が奇数回交差すれば点は多角形に含まれる.

2016/Practice/模擬国内予選B/講評 - ACM-ICPC Japanese Alumni Group

確かに…。

もう少し自分の頭で考えるようにしたい
(せっかくなのでライブラリに追加しましたが)。

AOJ 2631 : Clique Coloring

Clique Coloring | Aizu Online Judge

なんとも微妙な方法で解いてしまった。

まずaを降順にソートしておく。
前2つの要素においては(a[0] - 1) + (a[1] - 1) + 1個の点が
どうしても必要になることが考えると分かる。
一番最初のサンプルのように、1つの頂点を定めてそれにぶら下がるイメージ。
3つ目はa[2] - 1よりもすでに1番目2番目で定めた頂点を
利用してぶら下がればa[2] - 2個の点で十分となる。
それ以降について、簡単にするために a_i > 3のケースについて考えると
下の図のように、-3, -4としていけば最小になる。

f:id:arukuka:20170613051650p:plain

a_i \leq 3 について、a_i = 2のときは
1番目2番目で定めた頂点の間にリンクを張れば済む。
a_i = 3のときは1番目2番目3番目で定めた頂点の間にリンクを張れば済む。
ただし、点や辺が足りなくなることもあるので、
そのときはしょうがないので点を1つ追加すると良い。

f:id:arukuka:20170613053000p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2366100#1

nに対しての一般性が極めてないので
あまりスマートな感じではなくなってしまった。
もしかすると撃墜できるのかもしれない。

AOJ 2748 : 夏合宿の朝は早い

夏合宿の朝は早い | Aizu Online Judge

確率は苦手…。システムの稼働率みたいに考えるのかなと思ったけど、
サンプルが単純な例で複雑なグラフになったとき結果がどうなるか分からず。
あきらめて解説を見る。

2016/Practice/模擬国内予選B/講評 - ACM-ICPC Japanese Alumni Group

解説があるのありがたい…。

解説が丁寧すぎて特筆すべきことがない。

強連結成分分解は以下のページを参考に実装した。

mathtrain.jp

前処理の「適当な頂点からdfs」について、
雑に選んでいいのかなと思って0からdfsしたら、
4つ目のサンプルでWAになった。

5
0.10 0
0.20 1 1
0.30 1 1
0.40 1 1
0.50 1 1

これが全部強連結として判定されてしまう。

しょうがないので↑のページでいうところの
t(v)に値が代入されていないときは再度その点から
dfsするようにしたらACできた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2364555#1

お世辞にもきれいな実装とは言えないので何とかしたい。

yukicoder No.528 : 10^9と10^9+7と回文

No.528 10^9と10^9+7と回文 - yukicoder

愚直に頑張って数えました。

文字列をs、長さをnとします。
前処理として、[1, n)桁までの回文数を数えます。
これは一番左の桁が[1, 10)、他が[0, 10)の個数を数えれば良いです。

次にn桁ある場合、
左からi番目の桁がdだったとします。
n桁目(i==0)を除き、この桁が[0, d)の値を持つ場合は下の桁がどんな値も取り得ます(n未満になるので)。
残った桁 n - 2 * (i + 1) は[0, 10)の回文数を作れるので、
d * 10 ^ ((n + 1) / 2 - (i + 1)) を足していきます。
n桁目については[1, d)の範囲で数えます。

最後に、n以下の最大回文数を考えます(各桁でdを含めていないので)。
中央から左右を比較したときに、
左 > 右の場合はすでに数えているので無視します。
左 < 右があった場合は数えていないので1を足します。
すべて左 = 右(つまりnが回文数)の場合は数えていないので1を足します。

f:id:arukuka:20170610055504p:plain

こうして数えてきた回文数を出力すればACします。

http://yukicoder.me/submissions/179185


数え間違えたりで時間内に書けなかったのですが、
桁DP解法が分からなかったので自分の方法を信じて実装しました。
どなたか桁DPの解説を書いていただけると幸いです……。



追記

桁DP解法について調べていたら、もっと簡単に求まることが分かりました。

http://yukicoder.me/submissions/179227

これを皮切りに短縮を図って下さった方々がいたようで、
golf熱が再燃しました。
しかしこれ、やめどころが分からない…。

肝心の桁DPについての理解はなんとなくでしか理解できませんでした。
また時間を置いて桁DPに出会ったときに考えたいと思います。
てけてけに、少しずつ。

AOJ 2612 : Phutball

Phutball | Aizu Online Judge

状態数は少なそうなので普通にDFSをすれば良さそう。
同じ状態にたどり着くケースはなくはない。
少し心配なのでメモ化してみる(2^20 * 19 * 15)がMLE。
メモ化部分を消して提出する。

WA

は~?! 考えても分からなそうなのでケースを見てみたら
勝利条件を見誤っていた。はみ出さなくても一番下の段につけばOKとのこと。

if (y >= 19) { // 18もOK!
  return 0;
}
if (x < 0 || 15 <= x || y < 0) {
  return INF;
}

WA

^^ハゲそう
今度は

if (y >= 18) {
  return 0;
}
if (x < 0 || 15 <= x || y < 0) {
  return INF;
}

としているのがよくなかった(下の段にいてもはみ出たらダメ)。

if (y >= 19) {
  return 0;
}
if (x < 0 || 15 <= x || y < 0) {
  return INF;
}
if (y >= 18) {
  return 0;
}

これでよし!

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2361893#1


すぐにテストケースを見ないで考えておくべきだったなあ・・・。
反省。

AOJ 2643 : AI

AI | Aizu Online Judge

構文解析。ループの判定をどうするかだが、
命令のindex、x, y, 向いている方向を持てば良い。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2360572#1

横着してTreeSetで到達済みの状態を管理していたらTLE。
logはバカにならないので気を付けよう!
(logを殺してくる問題はあまり好きになれない)

動作文の実行回数をグローバルに持ってしまっていてあまり綺麗でない。
どうすればいいものか・・・。