足跡-sokuseki-

りかの日進月歩の記録

herokuのDB(無料)を使って競技プログラミングのアプリケーション開発

自分の用意したDBにコンテスト情報を入れて、情報の閲覧&追加ができるアプリケーションを作った。
https://hackerrank-jp.herokuapp.com

DB周り

ただ情報が古いのか違うところが多少ある。
DBの接続情報取得のところは heroku postgres
f:id:wk1080id:20200623230100p:plain
からsettingタブを開くとview credencialsがある
f:id:wk1080id:20200623230237p:plain

  • view credencialsのページのHeroku CLIをコピーしてコマンドラインで実行するとDBに接続できる。多分初回はThe local psql command could not be located的なことを言われるので、そこで言われたリンク先のlocal setupをする。
  • DBに接続できたら、\lコマンドを打つとherokuに登録してあるdatabase全てが表示される。自分のdatabaseに入るには\c [database名](自分のdatabase名はview credencialsのページに載っている)を打てばよい。
  • 自分のdatabase内で\dt;(テーブルの一覧表示コマンド)を打つとDid not find any relations.と言われるはず。ここから好きにテーブルを定義して使う。
CREATE TABLE contest(
contest_id serial,
contest_name varchar(80),
contest_url varchar(80),
contest_date date,
writer varchar(80)
);

serialは連番型です。
urlはwww.hackerrank.com以下のコンテスト名だけ登録するようにします。
これを実行してから\d CONTEST;(CONTESTテーブルの情報を表示)するとテーブル構造が見れます。f:id:wk1080id:20200624004921p:plain

例えばこのテーブルに試しにhttps://www.hackerrank.com/yfkpo2を追加してみると、

INSERT INTO contest (contest_name, contest_url, contest_date, writer) 
VALUES ('ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状', 'yfkpo2', '2019-09-14', 'prd_xxx, matsu7874');

f:id:wk1080id:20200624010836p:plain
ちゃんと追加できました。あとはこれを使ってアプリケーションを作ります。

※このテーブルは初期構想のものであり、今動いてるものとは異なります

コードを書く

今回はNode.jsのexpressを使います(理由:最近勉強したので)。たぶん言語はなんでもいいです。
参考:ExpressからHeroku Postgresを使う - Qiita
githubにコードをpushします。

herokuにデプロイ

参考: 【備忘録】GitHub経由でHerokuにデプロイするまでの流れ - Qiita

package.json"start": "node main.js",書いてない(Node.jsアプリをHerokuにデプロイする | | KeruuWeb)とかherokuの環境変数の設定(Why is my Node.js app crashing with an R10 error? - Heroku Help)とかでだいぶ苦戦した。

その他

DB扱うときはインジェクションに注意しような👊

f:id:wk1080id:20200630160132p:plain
インジェクションチェックの様子

オイラーツアーとセグ木を使ってLCA、パスのクエリに答える

本記事では以下の問題を解きます。

N 頂点の重み付きの無向木が与えられる。
Q 回、ある辺の重みを変更するクエリと、ある2つの頂点の間の距離を求めるクエリが与えられる。
これを、1≤N≤100000, 1≤Q≤100000 で解け。

オイラーツアーは木をDFSしたときの順番で頂点を記録する手法です。オイラーツアーで記録した頂点を配列に順に入れておき、それをセグ木に対応付けます。
オイラーツアー、セグ木の概要はここではこれ以上触れません。

今回使うオイラーツアーは以下のものです。dfs以外の詳細は省きます。

vector<vector<int>> g(n); //グラフの隣接リスト
vector<int> v; //オイラーツアーの頂点配列
vector<int> ind(n); //各頂点がオイラーツアー配列の何番目に最初に訪れるか

void dfs(int now, int par){//今の頂点、親の頂点
    ind[now] = v.size();
    v.push_back(now);
    for(int i = 0; i < g[now].size(); i++){
        if(g[now][i] != par){
            dfs(g[now][i],now);
            v.push_back(now);
        }
    }
}

根からある頂点への距離

今回は以下の木を例に説明します。

f:id:wk1080id:20200527180135p:plain:w500

この場合オイラーツアーの配列は{1,2,3,4,3,2,5,6,5,7,5,2,1}となります。
オイラーツアー配列では、隣り合う2要素は辺で繋がれているので、辺の距離(コスト)を対応づけることができます。
f:id:wk1080id:20200622225404p:plain:w800




では距離を計算していきましょう。

例えば根1から頂点3までの距離を考えてみると、3+1=4になってほしいです。
f:id:wk1080id:20200529235609p:plain:w400
これは先ほどの配列で考えると、配列の先頭から、オイラーツアー配列で頂点3に対応するところまでの辺のコストの総和と考えることができます。
f:id:wk1080id:20200622225153p:plain:w800



根1から頂点5までの距離はどうでしょうか。同じように木で考えると、根1から頂点5までの距離というのは、 (1から5の距離:ピンク) = (1から4の距離:青) - (2から4の距離:緑) + (2から5の距離:青) と考えることができます。
f:id:wk1080id:20200530001644p:plain:w400
これを先ほどと同じように配列でうまく考えるには、帰りがけの辺のコストを負にして打ち消してあげられるようにします。
f:id:wk1080id:20200622224958p:plain:w800
こうすると、先ほど根1から頂点3までの距離を求めたのと同様、根1から頂点5までの距離は、配列の先頭から、オイラーツアー配列で頂点5に対応するところまでの辺のコストの総和と考えることができます。
f:id:wk1080id:20200622224712p:plain:w800


これで、根からある頂点への距離を先頭からのsumで計算できるようになりました。累積和などを使えば高速に計算できます。

任意の2つの頂点間の距離

先ほどの図において、頂点3と頂点6のパスを考えます。
根から頂点3と根から頂点6の距離は計算できるので、ここから無駄な部分を引けば、頂点3と頂点6の距離はわかります。
無駄な部分というのは、根から、頂点3と頂点6のLCAの頂点の距離です。
よって、LCAを求めることができれば、任意の2つの頂点間の距離を求めることができますね。
LCAの性質を考えると、頂点3と頂点6のLCAは、頂点3から頂点6に向かうパス上にあり、かつ、その中で根からの深さが最も小さいものです。
f:id:wk1080id:20200530003402p:plain:w500

そのため、オイラーツアーの配列を求める際に、根の深さを記録してセグ木を作ってあげれば、区間minを計算することでLCAを求められます。

問題を解く

よって、この問題を解くには、オイラーツアー配列を作り、それに対応するコストの配列(帰りがけは逆符号とする)を作ってsumを計算できるようにして、根からの深さ配列を記録して区間minとその対応する頂点を計算できるようにすれば、計算クエリは処理できます。

変更クエリは、クエリで与えられた辺に対応するコストの配列の要素を変更すれば良いです。そのためには、各辺がコスト配列のどこに対応するのかを持っておく必要があります。これはそれぞれの辺がコストの配列のどのインデックスに対応するかを配列で持っておくなどの方法で実現できます。

最後に

この問題はHL分解を使って解くこともできます。
(HL分解を勉強しようとしたら遭遇したので:絶対に初心者でもわかるHL分解/Heavy-Light-Decomposition - Qiita
オイラーツアーは、ある頂点の子孫に一様に操作することしかしたことがなかったので、新鮮でした。
まあHL分解のほうが木のいろんなクエリに答えることができるので、わざわざこの方法を勉強しなくてもよいという説はあります。






図作るのめんど

ブロッコリーのチヂミ

美味しかったけど、前回のチーズリゾットには負けるなあ


右のやつです。

材料(直径6cmのチヂミ8枚)

溶き卵 1個
チーズ 50g
ブロッコリーの茎(5~7mm角) 2房分(約250g)
小麦粉 大さじ3
サラダ油 適量
塩胡椒 適量
水 大さじ1

作り方

  1. 耐熱容器にブロッコリーの茎と水大さじ1を入れてレンジで4分加熱する
  2. ボウルに1と小麦粉とチーズを入れて混ぜる
  3. 2に溶き卵と塩胡椒を入れてよく混ぜる
  4. 3を4枚ずつ2回に分けて焼く。
  • フライパンにサラダ油を引き、3を1/8ずつ4枚分入れ、直径6cmの薄い円形に整える
  • 焼き色がついたら裏返し、両面に焼き色がつくまで焼く
  • 油少量をフライパンの端から入れて強火にし、両面をカリッとさせる

ブロッコリーとコーンのミルクチーズリゾット

適当に創作したらおいしかったのでメモ。
ブロッコリーの茎を使う最強レシピだと思います。うますぎ。
f:id:wk1080id:20200426231417p:plain

材料(1人分)

炊いたごはん 約200g
玉ねぎ(みじん切り) 1/4個
ブロッコリーの茎(5mm角) 1房分
コーン 適量
チーズ 適量
オリーブオイル 小さじ1
塩胡椒 少々
パセリ 適量
☆牛乳 150ml
☆水 100ml
☆鶏がらスープのもと 小さじ2

作り方

  1. 耐熱容器にブロッコリーの茎とブロッコリーの茎が浸るくらいに水を入れて、ラップをしてレンジで4分加熱する
  2. 鍋にオリーブオイルを入れ玉ねぎを炒める
  3. 玉ねぎがしんなりしたら☆を加えて一煮立ちさせる
  4. ごはんを入れて約2分煮る
  5. 火を止め、水を切ったブロッコリーの茎、コーン、チーズ、塩胡椒を入れて混ぜる
  6. お皿に盛り、パセリを飾る

数学が苦手な人のための期待値DP AtCoder 第一回PAST O - 持久戦

期待値が苦手すぎるので解説を自分が理解できる粒度まで噛み砕いて書きました。

解法


dp[i] := 直前にiを出したときの残りの回数の期待値とすると
dp[max_number]は1であり、dp[0](サイコロを1度も振っていないとき)が求める値となる。
dp[i] を求める際には  i < j なるdp[j] がわかっていればよいため、 i の降順に計算する。
 i >= j のとき、出目  i のあとに出目  j を出すと操作が終了となり期待値は0なので)


サイコロの出目は 10^9までであるが、出目の個数は高々  6N <= 1.8 \times 10^5 なので、座圧すると配列としてもつことができる。


出目がa_1,a_2,a_3,a_4,a_5,a_6のサイコロを振るとき、出目は a_1,a_2,a_3,a_4,a_5,a_6の6通りあり、それぞれ等確率なので、
期待値は([次にa1を出したときの残りの期待値] + dp[次にa2を出したときの残りの期待値] + dp[次にa3を出したときの残りの期待値] + dp[次にa4を出したときの残りの期待値] + dp[次にa5を出したときの残りの期待値] + dp[次にa6を出したときの残りの期待値])/6に今から振る1回を足した値になる。



サイコロが1つしかない場合、目を a_1,a_2,a_3,a_4,a_5,a_6(a_i < a_{i+1})とすると dp[a6] = 1

dp[5] は、a_1 から  a_5が出ると操作が終了(期待値0)で、a_6が出ると操作は終了しないので、
期待値はdp[a5] = (0 + 0 + 0 + 0 + 0 + dp[a6])/6 + 1

dp[a4]は、 a_1 から   a_4 が出ると操作が終了で、 a_5, a_6 が出ると操作は終了しないので、
期待値はdp[a4] = (0 + 0 + 0 + 0 + dp[a5] + dp[a6])/6 + 1

同様に、
dp[a3] = (0 + 0 + 0 + dp[a4] + dp[a5] + dp[a6])/6 + 1
dp[a2] = (0 + 0 + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1
dp[a1] = (0 + dp[a2] + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1
dp[0] = (dp[a1] + dp[a2] + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1



サイコロが2つ以上あるとき、直前に  i を出した後、次に振ることができるサイコロは2つある。
どちらのサイコロを振るかは選択できるので、期待値がより大きくなる方を選べば良い。
つまり、
1つ目のサイコロを(  a_1,a_2,a_3,a_4,a_5,a_6 )、2つ目のサイコロを(  b_1,b_2,b_3,b_4,b_5,b_6 )とすると
(dp[a1] + dp[a2] + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1
(dp[b1] + dp[b2] + dp[b3] + dp[b4] + dp[b5] + dp[b6])/6 + 1 の大きい方をdp[i]の値とすればよい。



サイコロが3つ以上のときも同様で、dp[i]はその時点でのすべてのサイコロの期待値のmaxを代入すればよい。



よって、すべてのdp[i]について、 N 個のサイコロの期待値のmaxを計算していけばよいので、
愚直にやると O(N^2) となる。

ここで、 j 番目のサイコロを振ったときの残り回数の期待値をexp[j]とする。
exp[j]は、直前に出した目の値によって変わり、直前に  i を出したときは
 k  i < k をみたすサイコロ  j の出目として exp[j] = sum(dp[k])/6と表記できる。
すべてのサイコロについてexp[j]を適切に計算してあげると、
dp[i]の計算はmax(exp[j])+1で良い。
exp[j]の更新は、dp[i]の計算が終わった後、サイコロ  j に出目  i が含まれている場合、exp[j] += dp[i]/6をする。

max_exp = max(exp[j])という変数を作り、exp[j]が更新されるたびにmax_expを計算し直すことにすると、dp[i] = max_exp + 1と書くことができる。



まとめると、サイコロの出目を座圧し、dp[i] i の降順に計算していきながら、出目  i があるサイコロ  j exp[j]max_expを更新していけばよい。
exp[j]の更新は高々  6N 回で、事前に出目  i があるサイコロを  O(1) で調べられるように配列に入れて管理しておけば、dpテーブルの計算量は  O(N) である。

コード

mainのみ

signed main(void) {
    int n;
    cin >> n;
    vector<vector<int> >  a(n,vector<int>(6));
    vector<int> num;//座圧用配列
    rep(i,n)rep(j,6){
        cin >> a[i][j];
        num.push_back(a[i][j]);
    }

    //座圧
    sort(all(num));
    num.erase(unique(all(num)),num.end());

    int max_number = num.size();
    vector<vector<int> > dice(max_number+1);//dice[i]:=出目がiのサイコロのindex
    rep(i,n)rep(j,6){
        int ind = lower_bound(all(num),a[i][j]) - num.begin();//座圧後のindex
        dice[ind+1].push_back(i);//1-indexedにする
    }

    vector<double> dp(max_number+1,0),exp(n,0);
    double max_exp = 0;
    for(int i = max_number; i >= 0; i--){
        dp[i] = max_exp + 1;
        rep(j,dice[i].size()){
            //サイコロdice[i][j]に出目iが書かれている
            exp[dice[i][j]] += dp[i]/6.0;
            max_exp = max(max_exp, exp[dice[i][j]]);
        }
    }

    cout << shosu(10) << dp[0] << endl;
}

https://atcoder.jp/contests/past201912-open/submissions/12285583

topcoder SRM775 参加記

SRMそんなに出ないしすぐ忘れるのでコンテスト参加記を残そうかなあと思ったので(すぐ飽きそう)

前回、初回にして爆死はこちら→wk1080id.hatenablog.com

f:id:wk1080id:20200117023005p:plain
まともにACして早く灰色から脱出したいところ。
直前にtopcoderでのコードの書き方を前回の記事を見ながら思い出す。(提出はmain関数以外全部とか)

div2Easy

長さLで使われる文字がアルファベット最初のS文字であるような文字列のうち、文字列集合forbiddenに属するどの文字列とも完全に違う文字列はいくつあるか。
完全に違うとは、長さNの2つの文字列s,tがあったときに0以上N-1以下のすべてのiについてs[i] != t[i]をみたす。
Sは1以上26以下
forbiddenの要素数は1以上30以下
forbiddenの要素の長さはすべてL
Lは1以上6以下


完全に違うの定義を誤解していて時間をたくさん使ってしまった。
i文字目に使える文字の種類を調べて、それらをかけていけばいい。

div2Med

2次元のマップcaveが与えられる。マップは何もないマス'.'と岩のマス'#'と岩に隠れているkoboldがいるマス'K'のいずれか。
マップでは4方向に移動でき、'.'は連結。
desiredAreaという数が与えられるので、'#'のマスを'.'に変更してマップの'.'の数をdesiredArea個にしたい。
ただし変更後の'.'は連結で、koboldに隣接するマスは'#'でなければならない。
この条件をみたすようにマップの'.'の数をdesiredArea個にしたときにありうる変更後のマップを1つ出力せよ。(そのようなマップが存在しないときは空のvectorを出力する)
マップの縦の長さは1以上50以下
マップの横の長さは1以上50以下
desiredAreaは最初の'.'の個数以上、マップのマスの個数以下

'#'から'.'にできない(koboldと隣接している)マスを初めに調べておいて、あとで足りない個数分だけ色ぬりすればよい。
最初、連結に気づかなくて、変更できる'#'を上から順に塗っていたけど、連結なのでbfsで書いた。
challengeフェーズで部屋の人のコードを読むとみんなdfsで書いてたし前計算とかしてなかった。

div2Hard

Nとindexが与えられる

for sum = 0 .. 3*N-3:
    for x = 0 .. N-1:
        for y = 0 .. N-1:
            for z = 0 .. N-1:
                if x+y+z == sum:
                    visit (x,y,z)

の順でN*N*Nの3次元座標にアクセスするとき、index番目(0-indexed)にアクセスする座標を答えよ。
Nは1以上10^6以下
indexは0以上N^3 - 1以下

わからねー
xがiのときの通り数は(i+2)(i+1)/2なのでそれを使ってO(N)かけてsumを確定させて、そのあとはxを0から順に調べてyを順に調べて…
でできると思ったんだけど、sumを確定させるときのそれは嘘であることが終了直前にわかり、無(x,y,zはN-1以下でないといけないので)

challengeフェーズ

ルームのhard提出が1、med提出が3とかで、無
ルーム内challengeはなかった…

システス

Med落ちたけど
というかルームでMed落ちてるの自分だけ…
(Med落ちたということは、Medの日本語問題文が間違っている可能性があります)

レート

レート変動見るの難しすぎか?一度ログアウトしてログインしなおします。
734 -> 781(+47)
灰色コーダーの旅はこれからだ!〜次回作にご期待ください〜

C++のcomplexで円と線分の交差判定

ある円Cと線分Sの交差判定をします。

定義

円と線分(ここでは直線として管理します)の定義は↓

typedef complex<double> P;

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
  L(){;}
};

struct C {
  P c;double r;
  C(const P &c,double r):c(c),r(r){}
  C(){;}
};

実装

基本的な考え方は、円の中心と線分との距離を見ます。
円Cの中心と線分Sとの最短距離を  d_{min} 、最長距離を  d_{max} としたとき、
 d_{min} \le 円Cの半径」かつ「円Cの半径 \le d_{max}
を満たすとき、円Cと線分Sは交差します。

以下のコードでは、円と線分の交差判定をintersectCS()、線分と点の距離をdistanceSP()、点と点の距離をdistancePP()で計算しています。(intersectCS()以外は省略)

bool intersectCS(const C &c, const L &l){//円と線分の交差判定
    double close = distanceSP(l,c.c);
    double far = max(distancePP(l[0],c.c),distancePP(l[1],c.c));
    if(close <= c.r && far >= c.r)return true; //重なっていても良い
    //完全に交差している場合のみだと、イコールを外す
    return false;
}

verifyと全体コード

verifyはAOJ0129で行いました。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129
提出したコード:
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4060205