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 : イウィ
問題リンク :
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 : ナップザック
問題リンク :
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 : 辞書順
問題リンク : 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; }
UVa 13039 : Fibonacci Triangle
問題リンク :
https://uva.onlinejudge.org/external/130/13039.pdf
問題概要 :
1番目のフィボナッチ数を2, 2番目のフィボナッチ数を３とする
i番目のフィボナッチ数と同じ長さの線分がそれぞれa[i]個存在する
これらの線分を使って作れる三角形の本数の最大値を求めよ
解法 :
これもlaycrsさんの解説をみて解いた
三角形のうち一番長い線分の長さをF、Fの１つ前のフィボナッチ数の長さをF1とする
この時に考えられる三角形の構成は次のとおり
1. F が３本
2. F が２本 + なんでも良いので１本
3. F が１本 + F1が２本
短い線分から順番に三角形を作っていくことを考えたとき、
最大の辺の長さより前のものをできる限り消費したいので、
3,2,1の順番で三角形を作っていくとよい
コード:
nclude<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; int main() { int T; cin >> T; while( T-- ) { int n; cin >> n; vector<ll> vec(n); rep(i,n) cin >> vec[i]; ll sum = 0, prev = 0; rep(i,n) { while( i-1 >= 0 && vec[i] && vec[i-1] >= 2LL ) { vec[i-1] -= 2LL, prev -= 2LL, --vec[i]; ++sum; } while( prev && vec[i] >= 2LL ) { vec[i] -= 2LL, --prev; ++sum; } while( vec[i] >= 3LL ) { vec[i] -= 3LL; ++sum; } prev += vec[i]; } cout << sum << endl; } return 0; }
UVa 13036 : Birthday Gift to SJ - 2
問題リンク :
https://uva.onlinejudge.org/external/130/13036.pdf
問題概要 :
フィボナッチ数の積として表されるような数で、a以上b以下のものの最大値を求めよ
解法 :
laycrsさんの解説を読んで解いた
フィボナッチ数のうち2から89までを前半、それ以降を後半として列挙する
前半のフィボナッチ数を入れた配列をX、後半のフィボナッチ数を入れた配列をYとする
Xの各要素について、b/X[i]となるようなYの最大値を求める
これでも結構時間がかかるので、
素因数分解した時に、全て他のフィボナッチ数で表されるようなものは配列から除外した(8と144だけかな
コード:
#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 MAX = 1000000000000000000LL; vector<ll> sasami_san_kawaii(vector<ll> vec) { vector<ll> S; S.push_back(1); rep(i,(int)vec.size()) { ll coef = vec[i]; vector<ll> tmp = S; tmp.push_back(coef); rep(j,(int)S.size()) { ll v = S[j]; while( v <= v * coef && v * coef <= MAX ) { v *= coef; tmp.push_back(v); } } S = tmp; } S.erase(S.begin()); sort(S.begin(),S.end()); S.erase(unique(S.begin(),S.end()),S.end()); return S; } int main() { vector<ll> X,Y; { vector<ll> fib1,fib2; fib1.push_back(2); fib1.push_back(3); fib1.push_back(5); fib1.push_back(13); fib1.push_back(21); fib1.push_back(34); fib1.push_back(55); fib1.push_back(89); fib2.push_back(233); fib2.push_back(377); while( 1 ) { int size = (int)fib2.size()-1; ll tmp = fib2[size] + fib2[size-1]; if( tmp > MAX || tmp < 0 ) break; fib2.push_back(tmp); } X = sasami_san_kawaii(fib1); Y = sasami_san_kawaii(fib2); } int T; cin >> T; while( T-- ) { ll a,b; cin >> a >> b; ll maxi = -1LL; rep(i,(int)Y.size()) { if( Y[i] < a ) continue; if( Y[i] > b ) break; maxi = max(maxi,Y[i]); if( maxi == b ) break; } rep(i,(int)X.size()) { if( X[i] < a ) continue; if( X[i] > b ) break; maxi = max(maxi,X[i]); if( maxi == b ) break; } rep(i,(int)X.size()) { if( X[i] > b ) break; if( a <= X[i] && X[i] <= b ) maxi = max(maxi,X[i]); if( maxi == b ) break; ll v = b / X[i]; if( v < 233LL ) continue; int pos = lower_bound(Y.begin(),Y.end(),v) - Y.begin(); if( 0 <= pos && pos < (int)Y.size() && Y[pos] > v ) --pos; if( pos < 0 || (int)Y.size() <= pos ) continue; maxi = max(maxi,X[i] * Y[pos]); } cout << maxi << endl; } return 0; }
