Search on the blog

2016年5月22日日曜日

Pythonでログ出力をする

問題設定

2016-05-22 18:02:48,092 INFO [message]
2016-05-22 18:02:48,199 INFO [message]
2016-05-22 18:02:48,300 INFO [message]
...

のように出力時刻、レベル名、メッセージをログファイルに出力する場合を考える。
また、一定時間ごとにロテートする機能が欲しいとする。

実装1
import logging
import time

from logging.handlers import TimedRotatingFileHandler

logger = logging.getLogger("app")
logger.setLevel(logging.INFO)
handler = TimedRotatingFileHandler('test.log', when="s", interval=1, backupCount=5)
handler.setFormatter(logging.Formatter('%(asctime)s %(levelname)s %(message)s'))
logger.addHandler(handler)

def main():
    for i in range(100):
        logger.info("%d th iteration!" % i)
        time.sleep(0.1)

if __name__ == '__main__':
    main()

TimedRotatingFileHandlerを使うと目的のロテートが出来る。
上の実装だと1sごと(when, intervalで設定)にロテートするようにしている。
最新のログはtest.logに吐かれ、古いログは
test.log.2016-05-22_18-02-48
test.log.2016-05-22_18-02-49
...
のようにロテートされる。保持する古いログファイルは5つ(backupCountで設定)までとしている。

実装2
複数のロガーを使いたい場合は、実装1のように毎回プログラム上でロガーを作成していては面倒。その場合は、設定ファイルを使ってロガーを定義しておくとよい。

log_conf = {
  "version": 1,
  "disable_existing_loggers": False,

  "formatters": {
    "simple": {
      "format": "%(asctime)s %(levelname)s %(message)s"
    }
  }, 

  "handlers": {
    "time_rotate": {
      "class": "logging.handlers.TimedRotatingFileHandler",
      "formatter": "simple", 
      "filename": "test.log", 
      "when": "s",
      "interval": 1,
      "backupCount": 5
    }
  },

  "loggers": {
    "app": {
      "level": "INFO",
      "handlers": ["time_rotate"]
    }
  }
}

とりあえずpythonのdictで設定を書いた。
設定ファイルはdictに変換できればいいので、jsonやyamlで書いてもいい。

設定ファイル3行目のdisable_existing_loggersは、既存のロガーを無効化するかどうかの設定。デフォルト の値はTrueで、その場合、設定ファイルをロードする前に生成されたロガーが無効化されてしまう。無効化して欲しくない場合は、Falseを設定する。

設定ファイルのロードは以下のように行う。実装1と比べるとだいぶスッキリした。
import logging.config
import time
from conf import log_conf

logging.config.dictConfig(log_conf)
logger = logging.getLogger("app")

def main():
    for i in range(100):
        logger.info("%d th iteration!" % i)
        time.sleep(0.1)

if __name__ == '__main__':
    main()

2016年5月19日木曜日

SRM 571 Div2 1000 MagicMoleculeEasy

問題概要
グラフG(V, E)が与えられる。
各ノードには得点p[i]が割り振られている。
Vの中からk個のノードを選びたい。ただし、ノードv-w間にエッジが存在するとき、v, wのいずれかは必ず選ばなければならない。
選ばれたノードの得点の和の最大値を求めよ。

解法
あるエッジ(v, w)に注目すると、
vが選ばれなかった場合、wは必ず選ばなければならない。
wが選ばれなかった場合、vは必ず選ばなければならない。
という2パターンの分岐が発生する。どちらかを選ぶとkは1つ減る。

つまり全列挙を行っても高々2^k程度のパターンしかなく全列挙が可能。
ノードを選ぶ・選ばないではなく、エッジで結ばれるノードのどちらを選ぶかで状態を考えるという発想力が必要な問題。

今回の問題のように、入力のサイズ(=今回はグラフのサイズ)とは関係のないパラメータkに対してのみ指数時間かかるアルゴリズムをFPT(Fixed Parameter Tractable)アルゴリズムと呼ぶらしい。

実装
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int n;
bool conn[50][50];
int point[50];
vector<pair<int, int> > es;

int solve(int k, set<int> &s) {
  int p;
  for (p = 0; p < es.size(); p++) {
    if (!s.count(es[p].first) && !s.count(es[p].second))
      break;
  }

  if (p == es.size()) {
    int ret = 0;
    vector<int> ps;
    REP (i, n) {
      if (s.count(i))
        ret += point[i];
      else
        ps.push_back(point[i]);
    }
    sort(ps.rbegin(), ps.rend());
    REP (i, k) ret += ps[i];
    return ret;
  }

  if (es.size() - p > k * n)
    return -1;

  int ret = -1;
  int x = es[p].first;
  int y = es[p].second;

  s.insert(x);
  ret = max(ret, solve(k-1, s));
  s.erase(x);

  s.insert(y);
  ret = max(ret, solve(k-1, s));
  s.erase(y);
  
  return ret;
}

class MagicMoleculeEasy {
public:
  int maxMagicPower(vector<int> magicPower, vector<string> magicBond, int k) {
    n = magicPower.size();
    memset(conn, 0, sizeof(conn));
    REP (i, n) REP (j, n) conn[i][j] = magicBond[i][j] == 'Y';
    REP (i, n) point[i] = magicPower[i];
    es.clear();
    REP (i, n) REP (j, i) if (magicBond[i][j] == 'Y') es.push_back(make_pair(i, j));
    set<int> s;
    return solve(k, s);
  }
};

2016年5月18日水曜日

SRM 652 Div2 1000 NoRightTurnDiv2

問題概要
二次元座標上にN個の点が与えられる。
このN個の点すべてをある順番に従って訪れたい。以下の条件を満たすように移動するとき、どのような順で点を訪れればよいか求めよ。
  • 点から点への移動するときは二点を結ぶ直線上を移動しなければならない
  • 移動したパスが交差してはならない
  • 右にターンすることはできない(パスは反時計周りにならないといけない)
解法
最も右側の点から始める。最も右側の点が複数個ある場合は、その中で最も下側にあるものを選ぶ。あとは反時計まわりになるように、外側の点からgreedyに訪問すればいい。反時計まわりの判定、最も外側の判定は外積を使って行う。

実装
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int vis[50];

long long cross(long long x1, long long y1, long long x2, long long y2) {
  return x1 * y2 - x2 * y1;
}

class NoRightTurnDiv2 {
  public:
  vector<int> findPath(vector<int> x, vector<int> y) {
    memset(vis, 0, sizeof(vis));
    vector<int> ret;
    int n = x.size();
    int p2 = 0;
    FOR (i, 1, n) {
      if (make_pair(x[i], -y[i]) > make_pair(x[p2], -y[p2]))
        p2 = i;
    }
    x.push_back(x[p2]);
    y.push_back(y[p2]-1000);
    vis[p2] = true;
    ret.push_back(p2);
    int p1 = n;
    
    REP (i, n-1) {
      int p3 = -1;
      REP (j, n) {
        if (vis[j])
          continue;
        if (p3 == -1 ||
            (cross(x[p2]-x[p1], x[j]-x[p2], y[p2]-y[p1], y[j]-y[p2]) >= 0 &&
             cross(x[j]-x[p2], x[p3]-x[p2], y[j]-y[p2], y[p3]-y[p2]) >= 0)) {
          p3 = j;
        }
      }
      vis[p3] = true;
      ret.push_back(p3);
      p1 = p2;
      p2 = p3;
    }
    return ret;
  }
};

2016年5月11日水曜日

SRM 647 Div2 1000 BuildingTowers

問題概要
N個のビルがあり、ラベルが1からNまで振られている。
以下の条件を満たすとき、ビルNの高さの最大値を求めよ。
  • ビル1の高さは0
  • すべてのビルの高さは非負整数
  • 隣り合うビルの高さの差はK以下
  • ビルx[i]の高さはt[i]以下
解法
与えられたx[]のビルについて、最大の高さを求める。
このとき、前から見たときと、後ろから見たときに、3つ目の条件を満たすように最大の高さを計算しないといけない。
x[]のビルについて決まったら、x[i]とx[i+1]の間の区間に立てられるビルの最大の高さを求める。これをすべてのiについて行う。

後ろから見たときのチェックは見落としがちなので、注意が必要。

実装
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const long long oo = 1LL<<60;

class BuildingTowers {
  public:
  long long maxHeight(int N, int K, vector<int> x_, vector<int> t_) {
    vector<long long> x(ALL(x_));
    vector<long long> t(ALL(t_));

    if (x.size() && x[0] == 1) t[0] = 0;
    else {
      x.insert(x.begin(), 1);
      t.insert(t.begin(), 0);
    }

    int m = x.size();
    for (int i = 1; i < m; i++)
      t[i] = min(t[i], t[i-1] + K * (x[i] - x[i-1]));
    for (int i = m-2; i >= 0; i--)
      t[i] = min(t[i], t[i+1] + K * (x[i+1] - x[i]));
    
    long long ret = 0;
    REP (i, m-1) {
      long long z = (t[i+1] - t[i] + K * (x[i] + x[i+1])) / (2 * K);
      if (x[i] <= z && z <= x[i+1])
        ret = max(ret, t[i] + K * (z - x[i]));
      ++z;
      if (x[i] <= z && z <= x[i+1])
        ret = max(ret, t[i+1] + K * (x[i+1] - z));
    }
    ret = max(ret, t[m-1] + K * (N - x[m-1]));
    return ret;
  }
};

2016年5月9日月曜日

Codeforces Round #351 Div2 E. Levels and Regions

問題概要
あなたはテレビゲームをプレーしている。
このゲームでは、1からnまでの階があり、それらはk個の地区に分かれている。
各階iには、対応するトークンがt[i]個ある。

今あなたは地区Xにいるとする。
そのとき、コンピュータによって以下の操作が行われる。
  • 袋にX内のクリア済みの階に対応するトークンを入れる。
  • 袋にX内のまだクリアしていない最低階に対応するトークンを入れる。
  • 袋から一様な確率でランダムにトークンを引く。
あなたは袋から引かれたトークンに対応する階をプレーしないといけない。

一つの階をクリアするには1時間かかる。
各階をどのように地区に振り分けるかは自由である。
すべての階をクリアするために必要なプレー時間の期待値の最小値を求めよ。

解法
(地区を何個まで区切ったか, 階)を状態数としてDPすればいいのはすぐ分かる。
これだけだと遅いので、うまく式変形してConvex Hull Trickを使って高速化する。

実装
ライブラリ化している人が多かったので、自分もライブラリ作ってみた。
処理の詳細な説明は蟻本に載っている。
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const double oo = 1e100;
int n, k;
int ts[200000];
double sum[200000+1];
double rev[200000+1];
double pre[200000+1];
double dp[50+1][200000+1];

template <typename T>
// line f(x) = ax + b
struct line {
  T a, b;
  line() {}
  line(T a, T b) : a(a), b(b) {}
  T eval(T x) { return a * x + b; }
};

template <typename T>
// get min_l {f_l(x)} with convex hull trick
struct CHT {
  int s;
  int t;
  vector<line<T> > deq;

  CHT(int n) {
    deq = vector<line<T> >(n);
    clear();
  }

  void clear() {
    s = t = 0;
  }
  
  bool check(const line<T> &l1, const line<T> &l2, const line<T> &l3) {
    return (l2.a-l1.a) * (l3.b-l2.b) >= (l2.b-l1.b) * (l3.a-l2.a);
  }
  
  void push(T a, T b) {
    line<T> l(a, b);
    while (s + 1 < t && check(deq[t-2], deq[t-1], l))
      --t;
    deq[t++] = l;
  }
  
  
  T get(T x) {
    while (s + 1 < t && deq[s].eval(x) >= deq[s+1].eval(x))
      ++s;
    return deq[s].eval(x);
  }
  
};

void solve() {
  REP (i, n) sum[i+1] = sum[i] + ts[i];
  REP (i, n) rev[i+1] = rev[i] + 1.0 / ts[i];
  REP (i, n) pre[i+1] = pre[i] + sum[i+1] / ts[i];
  REP (i, k+1) REP (j, n+1) dp[i][j] = oo;
  dp[0][0] = 0.0;
  CHT<double> cht(n+1);
  REP (i, k) {
    cht.clear();
    REP (j, n) {
      cht.push(-sum[j], dp[i][j] - pre[j] + rev[j] * sum[j]);
      double tmp = pre[j+1] + cht.get(rev[j+1]);
      dp[i+1][j+1] = min(dp[i+1][j+1], tmp);      
    }
  }
}

int main() {
  scanf(" %d %d", &n, &k);
  REP (i, n) scanf(" %d", ts+i);
  solve();
  printf("%.9lf\n", dp[k][n]);
  return 0;
}

2016年5月8日日曜日

Google Code Jam 2016 Round 1C Fashion Police

問題概要
あなたはJ枚のジャケット、P枚のパンツ、S枚のシャツを持っている。(J <= P <= S)

以下の条件を満たすように、毎日服装を選ばなければならない。
同じ{ジャケット、パンツ、シャツ}の組み合わせを2回以上着ることはできない。
同じ{ジャケット、パンツ}の組み合わせをK回以上着ることはできない。
同じ{パンツ、シャツ}の組み合わせをK回以上着ることはできない。
同じ{シャツ、ジャケット}の組み合わせをK回以上着ることはできない。

最大で何日間上記の条件を満たしながら服装を選ぶことができるか?
日数と服装の選び方を出力せよ。

解法
K >= Sの場合は、J*P*Sのすべてのパターンを1回ずつ着ることができる。
以下では、K < Sの場合を考える。

鳩ノ巣原理により、求める日数をxとすると、
x <= J * P * K
x <= P * S * K
x <= S * J * K
が成り立つ。さらに、J <= P <= Sの条件から、
x <= J * P * K
となる。

もし、x = J * P * Kとなるような選び方ができれば、それが解となる。
ジャケットをi, パンツをjに固定したとき、シャツkを以下のように選んでみる。
k = (i + j + d) % S, 0 <= d < K.

K < Sより、上のkはすべて異なっている。
このとき、固定した{ジャケット、パンツ}ごとにK通りのパターンがあるので、全体でJ * P * Kパターンの選び方ができていることに注意。

この選び方が{ジャケット、シャツ}および{パンツ、シャツ}を固定したときにも制約に違反していないことが確認できれば、これが解となる。

ジャケットをi, シャツをkに固定した場合を考えてみる。
(i, j, k)が解に含まれるとき、
k = (i + j + d) % S, 0 <= d < K.
となるようなdが存在する。このとき
j = (k - i - d) % S.
となる。dはKパターンしかないため、同じ{ジャケット、シャツ}のパターンがK回以上着られることはない。

{パンツ、シャツ}を固定した場合も同様にK回以上着られることはない。
よってこれが解となる。

実装
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int J,P,S,K;

void solve() {
  cin >> J >> P >> S >> K;

  if (K >= S) {
    cout << J*P*S << endl;
    REP (x, J) REP (y, P) REP (z, S) {
      cout << x+1 << " " << y+1 << " " << z+1 << endl;
    }
  } else {
    cout << J*P*K << endl;
    REP (x, J) REP (y, P) REP (z, K) {
      cout << x+1 << " " << y+1 << " " << (x+y+z)%S+1 << endl;
    }
  }
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }
    return 0;
}