土下座しながら探索中

主に競技プログラミング

herokuでカスタムドメインを使いたい

備忘録 heroku

herokuでweb appを作ると通常xxx.herokuapp.comというurlになっている
このherokuapp.comを消してxxx.comにしたい
したのでその過程をメモ
ちなみに月1100円くらいかかる

1. ドメインを買う ( 年1300円くらい、購入するドメイン名によるけど ）
自分は
VALUE-DOMAIN バリュードメイン
で購入した
以降購入したどめいん名をxxx.comとする

2. web appのあるディレクトリにどうして
$ heroku domains:add xxx.com
を実行

3. DNSさーばを借りる ( 月1000円くらい　海外のだと$5とかで借りれる )
ルートドメインを使いたいのでALIAS（だったかな）を使えるとこでDNSサーバに登録してもらう
herokuの公式サイトにいくつか紹介されているけど、英語弱者なので日本のが良いと思い
日本のとこを探した
DNSを自由に簡単に。Dozens（ダズンズ）
ここに登録してbasicプラン（月１０００円）に入る
するとTypeでALIASを選べるようになるのでそれを使う
Recode Nameにはなにもかかず(.xxx.com)となるはず
TypeはALIASに、
Contentにxxx.herokuapp.comと書く
あとはそれで登録
登録するとDNSサーバを教えてもらえるので、（といっても固定なので登録しなくても分かるが
それをdomain-valueに言ってネームサーバに記入しておわり

第2回 ドワンゴからの挑戦状 予選 D : 庭園

累積和

問題リンク :
D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder

問題概要 :
略

解法 :
長方形を２つ選ぶので、縦か横に領域を分割して
それらの中の最大値を足したものの最大値が答えとなる
そのため、ある長方形の中の最大値について求めることができれば良い

まず、以下の問題を解こう
Frame | Aizu Online Judge
y軸を２つ選ぶというアイデアを得ましたね
では次に、以下の問題を解きましょう
https://uva.onlinejudge.org/external/126/p12640.pdf
（この解説は
UVa 12640 : Largest Sum Game - 土下座しながら探索中）

数列について、連続した部分の総和の最大値の求めかたが分かりましたね
ではもうこの問題についても分かったでしょう



つまり、y軸を２つ固定すると、その固定された範囲の各x軸については和をとってまとめることが可能で、こうするとただの数列の連続した部分列の最大値を求める問題になります


コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll LLINF = LLONG_MAX;
const int MAX = 310;

ll b[MAX][MAX],sum[MAX][MAX];
ll upper[MAX], bottom[MAX];

void rotate90(int h,int w){
  swap(h,w);
  vector<vector<ll> > ret(h,vector<ll>(w,0));
  for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
      ret[y][x] = b[w-1-x][y];
    }
  }
  rep(i,h) rep(j,w) b[i][j] = ret[i][j];
}

inline ll calcSum(int x1,int y1,int x2,int y2) {
  ll ret = sum[y2][x2];
  if( y1-1 >= 0 ) ret -= sum[y1-1][x2];
  if( x1-1 >= 0 ) ret -= sum[y2][x1-1];
  if( y1-1 >= 0 && x1-1 >= 0 ) ret += sum[y1-1][x1-1];
  return ret;
}

ll calc(int h,int w) {
  rep(i,h) rep(j,w) {
    sum[i][j] = b[i][j];
    if( j-1 >= 0 ) sum[i][j] += sum[i][j-1];
    if( i-1 >= 0 ) sum[i][j] += sum[i-1][j];
    if( j-1 >= 0 && i-1 >= 0 ) sum[i][j] -= sum[i-1][j-1];
  }
  rep(i,h) upper[i] =  bottom[i] = -LLINF;
  rep(y1,h) REP(y2,y1,h) {
    ll maxi = -LLINF;
    ll mini = 0;
    rep(x,w) {
      maxi = max(maxi,calcSum(0,y1,x,y2)-mini);
      mini = min(mini,calcSum(0,y1,x,y2));
    }
    upper[y2]  = max(maxi,upper[y2]);
    bottom[y1] = max(maxi,bottom[y1]);
  }
  REP(y,1,h) upper[y] = max(upper[y],upper[y-1]);
  for(int y=h-2;y>=0;y--) bottom[y] = max(bottom[y],bottom[y+1]);
  ll maxi = -LLINF;
  rep(y,h-1) maxi = max(maxi,upper[y]+bottom[y+1]);
  return maxi;
}

void compute(int h,int w) {
  ll maxi = calc(h,w);
  rotate90(h,w);
  swap(h,w);
  maxi = max(maxi,calc(h,w));
  cout << maxi << endl;
}

int main() {
  int h,w;
  cin >> h >> w;
  rep(i,h) rep(j,w) cin >> b[i][j];
  compute(h,w);
  return 0;
}

herokuのサーバー上に一時ファイルを作ったこと

備忘録 heroku

herokuのサーバー上に一時ファイルを作る必要があり、それが出来るようになるまでに困ったところと解決策をメモ

1. 一時ファイルを作成できるのは /tmp 内だけ

それ以外の場所にファイルを作成しようとしても無駄です

例えば、 java で一時ファイルを作るためには次のようにする

try {
  File file = new File("/tmp/X.txt"); // /tmp 内なのでOK
  PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file)));
  pw.println("XXXXXXX");
  pw.close();
} catch(IOException e) {}


以下のようにしても一時ファイルは作成されない

try {
  File file = new File("X.txt"); // カレントディレクトリが/tmpでないならファイルは作成されない
  PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file)));
  pw.println("XXXXXXX");
  pw.close();
} catch(IOException e) {}

2. dynosは３つある
一時ファイルがちゃんと作成されているか確認したい
では、heroku run "ls /tmp" で確認してみよう -> 見当たらない...
見当たらないのでてっきり出来ていないものかと思いきや、そういうわけではない
dynosは３つ存在するのだ
1つ目は Web Dynos, 2つ目は Worker Dynos, 3つ目は One-off Dynos (これらの詳細は下記のリンク先で確認できる)
heroku runは(多分)One-off Dynos
1.のプログラムが実行され、ファイルを書き込んでいるのは Web Dynos か Worker Dynos のどちらか (知らない)
1.のプログラム実行後に heroku run で /tmp の中身を見ても、それらのDynosは相互に影響を与えないため確認できない
heroku公式の以下のリンク先にある Types of dynos を読むとそれが分かる
Dynos and the Dyno Manager | Heroku Dev Center
経緯
一時ファイルが作成できない
/tmpにしかファイルは書き込めないらしい
/tmpにjavaでファイルを作成して、heroku runでファイルが作成されたか確認
ない
stack overflowにそれっぽい記事がある
heroku公式の説明をちゃんと読めとある、読もう
herokuは3つのdynos上で動くらしい
One-off Dynos は temporary dynos で administrative tasks を処理するために使われる...と書いてあるのでなんとなく heroku run はここっぽい
また、javaのプログラムはadministrative taskでもないしここではなさそう
Web DynosとWorker Dynosの説明を見るかぎりjavaはこのどちらかっぽい
ひょっとしてheroku runにファイルが存在しないのは、作られてないんじゃなくて作られたサーバーが違うのでは...? => その通りだったっぽい

Typical DP Contest I : イウィ

典型DPコンテスト 動的計画法

問題リンク :
I: イウィ - Typical DP Contest | AtCoder

問題概要 : 最大iwi数

解法 :
メモ化再帰 => WA
区間DP => TLE
TLEを解消する方法が全く浮かばなかったので諦めてrngさんのコードを参考に解いた

dp[L][R] := 閉区間[L,R]までで得られるiwiの最大値
区間DPでよくやる、長さが小さい順に値を更新をする

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

string s;
int dp[301][301];

int main() {
  getline(cin,s);
  int n = s.size();
  REP(length,1,n+1) rep(sp,n-length+1) { // length : 区間の長さ, sp : 左から順に区間の値を更新
    int ep = sp + length - 1;
    REP(k,sp+1,ep) dp[sp][ep] = max(dp[sp][ep],dp[sp][k]+dp[k+1][ep]);
    if( s[sp] == 'i' && s[ep] == 'i' ) {
      REP(k,sp+1,ep) if( s[k] == 'w' ) {
        bool fail = false;
        int len = (k-1)-(sp+1)+1;
        if( len && !( len >= 3 && dp[sp+1][k-1] == len ) ) fail = true;
        len = (ep-1)-(k+1)+1;
        if( len && !( len >= 3 && dp[k+1][ep-1] == len ) ) fail = true;
        if( !fail ) {
          dp[sp][ep] = ep - sp + 1;
          break;
        }
      }
    }
  }
  cout << (int)(dp[0][n-1]/3) << endl;
  return 0;
}

Typical DP Contest H : ナップザック

典型DPコンテスト 動的計画法

問題リンク :
H: ナップザック - Typical DP Contest | AtCoder

問題概要 : 日本語なので略

解法 :
まずナップザックに入れるものを色の番号が小さい順にソートする
（同じ色のものは連続した場所に存在するようにしたいだけ）
通常のナップザックに加えて、今追加しようとしている色が既に追加されているかされていないかという情報を持たせる
下記の配列にあるstate(0か1)がその情報を表す
dp[i][state][c][w] := i番目のものを追加しようとしていて、i番目のものと同じ色を既に追加したかどうか(state), 現在の色の数(c), 重みの総和(w) としたときの最大値

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

struct Data {
  int w,v,c;
  bool operator < ( const Data &dat ) const {
    if( c != dat.c ) return c < dat.c;
    if( w != dat.w ) return w < dat.w;
    return v < dat.v;
  }
};

int N,W,C,dp[2][2][60][10010];
Data data[101];

void compute() {
  memset(dp,-1,sizeof(dp));
  dp[0][0][0][0] = 0;
  sort(data,data+N);
  int maxi = 0;
  rep(i,N) { 
    int cur = i & 1;
    int next = !cur;
    rep(j,2) rep(k,C+1) rep(l,W+1) dp[next][j][k][l] = -1;
    Data &info = data[i];
    rep(j,2) {
      rep(k,C+1) {
	rep(l,W+1) {
	  if( dp[cur][j][k][l] == -1 ) continue;
	  dp[next][j][k][l] = max(dp[next][j][k][l],dp[cur][j][k][l]);
	  int color = k + !j;
	  if( color > C || l+info.w > W ) continue;
	  int &v = dp[next][1][color][l+info.w];
	  v = max(v,dp[cur][j][k][l]+info.v);
	  maxi = max(maxi,v);
	}
      }
    }
    if( i+1 < N && info.c != data[i+1].c ) {
      rep(k,C+1) rep(l,W+1) {
	dp[next][0][k][l] = max(dp[next][0][k][l],dp[next][1][k][l]);
	dp[next][1][k][l] = -1;
	maxi = max(maxi,dp[next][0][k][l]);
      }
    }
  }
  cout << maxi << endl;
}

int main() {
  cin >> N >> W >> C;
  rep(i,N) cin >> data[i].w >> data[i].v >> data[i].c;
  compute();
  return 0;
}

Typical DP Contest G : 辞書順

典型DPコンテスト 動的計画法

問題リンク : G: 辞書順 - Typical DP Contest | AtCoder
問題概要 :
文字列sと自然数Kが与えられる
sから得られる連続でない部分文字列のうち、辞書順でK番目のものを求めよ

解法 :
他の人のブログを参考に解いたので、
コードにある通り

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;



ll K,dp[1000100][30]; // dp[i][j] := 場所iで文字jを使う数
string s;

int compute() {
  for(int i=(int)s.size()-1;i>=0;i--) {
    for(char c='a';c<='z';++c) {
      if( s[i] == c ) {
	dp[i][c-'a'] = 1; // c単体
	for(char h='a';h<='z';h++) { // 既にi番目にcを置いたので後に何が来ても良い
	  dp[i][c-'a'] += dp[i+1][h-'a'];
	  if( dp[i][c-'a'] > K ) { // 愚直に計算するとlong longでも計算できないのでK以上はK+1にまとめる
	    dp[i][c-'a'] = K + 1LL;
	    break;
	  }
	}
      } else {
	dp[i][c-'a'] = dp[i+1][c-'a']; // s[i]はcではないためiより前に置いたものを使う
      }
    }
  }
  {
    ll sum = 0;
    rep(i,26) {
      sum += dp[0][i];
      if( sum >= K ) break;
    }
    if( sum < K ) return puts("Eel");
  }

  string answer = "";
  rep(i,(int)s.size()) {
    for(char c='a';c<='z';c++) {
      if( dp[i][c-'a'] == 0 ) continue;
      if( K > dp[i][c-'a'] ) { // i番目にcを置いてもKには到達しないので使わない
	K -= dp[i][c-'a'];
      } else { // 初めて K <= dp[i][c-'a'] となった場所なのでcを使う必要がある
	answer += string(1,c);
	while( s[i++] != c ); --i; // s[i] != c なら s[i] == c であるような場所まで進まなければいけない
	--K; 
	break;
      }
    }
    if( !K ) break;
  }
  cout << answer << endl;
}

int main() {
  cin >> s >> K;
  compute();
  return 0;
}

UVa 1577 : Low Power

二分探索

問題リンク :
https://uva.onlinejudge.org/external/15/1577.pdf

問題概要 :
n台のマシーンがある
各マシーンは２つの回路を持っていて、
各回路はk個のバッテリーを持っている
つまり、全てのマシーンにバッテリーをセットするためには2*n*k個のバッテリーが必要となる
また、バッテリーのパワーは整数として表される
各マシーンにバッテリーをセットしたい
マシーンにバッテリーをセットすると、２つの回路内のバッテリーのパワーの最小値の差分が出力される
各マシーンが出力する値の最大値を最小化するようにバッテリーをマシーンにセットし、その値を出力せよ

解法 :
二分探索
バッテリーはパワーが小さい順にソートしておく
二分探索で最大値の最小値xを決める
xを決めたとき、最大値の最小値がx以下になるようにバッテリーをセットできるかチェックする
これは前から貪欲に回路の最小値のペアを作っていくことでチェックできる
バッテリーのうち一番小さい値は必ず回路の最小値となる
その値の次の値と差分をとったときに、差分がx以下ならそれらを２つの回路の最小値とする
そうでないなら今一番小さい値は前の回路のいずれかに入れてしまう

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,k,p[1000100];

bool check(int maxi_diff) {
  int remain = 0;
  int pair_cnt = 0;
  rep(i,2*n*k) {
     //iとi+1を回路の最小値とする
     //iとi+2を最小値のペアとしないのは、そうした場合i+1がi+3以降とペアになる必要がでてきて、
     //i+2が存在しない分だけその差分が離れてしまうから、それだったらiとi+1をペアにしたほうが良い
    if( pair_cnt < n && i+1 < 2*n*k && p[i+1]-p[i] <= maxi_diff ) {
      remain += ( k - 1 ) * 2;
      ++pair_cnt, ++i;
    } else {
      if( remain ) --remain;
      else         return false;
    }
  }
  return true;
}

void compute() {
  sort(p,p+2*n*k);
  int L = 0, R = p[2*n*k-1]-p[0];
  while( L + 1 < R ){
    int M = ( L + R ) / 2;
    if( check(M) ) R = M;
    else           L = M;
  }
  if( check(L) ) printf("%d\n",L);
  else if( check((L+R)/2) ) printf("%d\n",(L+R)/2);
  else printf("%d\n",R);
}

int main() {
  while( scanf("%d %d",&n,&k) != EOF ) {
    rep(i,2*n*k) scanf("%d",p+i);
    compute();
  }
  return 0;
}