naoya_t@hatenablog

いわゆるチラシノウラであります

CodeChef October Long Challenge 2017

f:id:n4_t:20171017122525j:plain
https://www.codechef.com/OCT17
最初と最後だけ(=週末参加)
2回めの週末はデバッグで時間を溶かしただけ
617.88214点で241位

長期コンテストだと最初の頃に何やってたか忘れちゃうんだよね
解法を忘れちゃったやつはアとか書いておけばいいのか
ていうかアって何

続きを読む

DISCO presents ディスカバリーチャンネル コードコンテスト 2017:Web予選

10/7(土) 21:00〜22:30
f:id:n4_t:20171007222930p:plain

ディスカバリーチャンネル コードコンテスト 2017

あからさまに新卒学生向けコンテストだし、別に出なくていいかなと思ったんだけど
折角起きてたので参加。

全完82位…

2018年卒業見込み学生100人、それ以外から上位100名(年齢不問)の計200人、ということなので
予選通っちまったか… オンサイト出れるのかなあ(スケジュール的に)

→ 折角予選通ったし本戦も出たかったんだけど、2時間のコンテストに出るだけのために1日拘束されるのはきついので辞退。
(出る人は最後までいろ、との事で、コンテストが終わって昼食前に離脱みたいなオプションがない)

続きを読む

deeplearning.ai受講メモ

f:id:n4_t:20170926194609p:plain
https://www.deeplearning.ai/

Andrew Ng先生のディープラーニング専門講座 deeplearning.ai を受講したメモ。久々のCoursera!

現在のところ、全5講座

  1. Neural Networks and Deep Learning
  2. Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization
  3. Structuring Machine Learning Projects
  4. Convolutional Neural Networks
  5. Sequence Models

のうち3つ目の Structuring Machine Learning Projects まで開講されている。

Courseraの中でもこの講義は Specialization という枠組みで、基本有料(月$49.00;講義ビデオを視聴するだけで課題なしCertificateなしで良ければ無料)のコース。最初の1週間は無料*1

講義はすべて英語*2
1つ目のやつは日本語や中国語の字幕が用意されていたけど、後の方は英語字幕だけだった。

*1:無料になるのは講座単位ではなく Specialization の枠組み単位らしい

*2:Andrewの英語を聞くのって前に受けたMachine Learningコースぶりか?いやそんなこともないか

続きを読む

Codeforces: Manthan, Codefest 17

出てないけど

agwたんから聞いた問題

B. Marvolo Gaunt's Ring

http://codeforces.com/contest/855/problem/B

真ん中の値を固定(1〜N)して左右をO(log N)でどうにかするのかなあと一瞬思ったんだけど
サンプルケースを見ながら、ああ同じ数字を3回使ってもいいのか、もしかしてこれDPで解けるんじゃないかと思って dp[N][3] みたいな配列を作り、

  • p·ai + q·aj + r·ak の(1〜kまででの)最大値は p·ai + q·aj のそこまでの最大値と r·ak の和だし
  • p·ai + q·aj の(1〜jまででの)最大値は p·ai のそこまでの最大値と q·aj の和だし
  • p·ai の(1〜iまででの)最大値は普通に最大値だし

って
左からDPで、前のi←i←j←kだけ参照できればいいからdp[3]で良くて

ll solve(int n,  ll p, ll q, ll r, vector<int>& a) {
    vector<ll> dp(3);

    ll a0 = (ll)a[0];
    dp[0] = a0 * p;
    dp[1] = a0 * (p+q);
    dp[2] = a0 * (p+q+r);

    for (int i=1; i<n; ++i) {
        ll ai = (ll)a[i];
        dp[0] = max(dp[0], p*ai);
        dp[1] = max(dp[1], dp[0]+q*ai);
        dp[2] = max(dp[2], dp[1]+r*ai);
    }

    return dp[2];
}

int main() {
    vector<int> a(100000);
    loadvec(a, 4);
    int n=a[0],p=a[1],q=a[2],r=a[3];
    loadvec(a, n);
    ll ans = solve(n,p,q,r,a);
    cout << ans << endl;
    return 0;
}

あと、値の範囲は±3e18までだしlong longで行けるし
→WA食らった
http://codeforces.com/contest/855/submission/30692320
なんでだろう?
n=1の場合とか?いや問題ないよね

ちょっと書き換えてもう一度。

ll solve(int n, ll p, ll q, ll r, vector<int>& a) {
    vector<ll> dp(3, 0x8000000000000000LL);
    rep(i, n) {
        ll ai = (ll)a[i];
        dp[0] = max(dp[0], p*ai);
        dp[1] = max(dp[1], dp[0]+q*ai);
        dp[2] = max(dp[2], dp[1]+r*ai);
    }
    return dp[2];
}

int main() {
    vector<int> a(100000);
    loadvec(a, 4);
    int n=a[0],p=a[1],q=a[2],r=a[3];
    loadvec(a, n);
    ll ans = solve(n,p,q,r,a);
    cout << ans << endl;
    return 0;
}

→またWA食らった
http://codeforces.com/contest/855/submission/30692406
どゆこと?

テストケース見たら、-1000000000 だけから成る入力で0が出てる。

デバッグプリントして気がついた。vector<int>の読み込み部分(自作)でバグってる。
確保しているスペースと読み込み最大長がINT_MINを想定していない。
そこを直して(INTSPACE=11を12に変えただけだが)
→AC
http://codeforces.com/contest/855/submission/30692462

CodeChef September Long Challenge 2017

f:id:n4_t:20170912134258j:plain
https://www.codechef.com/SEPT17
9/1 15:00IST 〜9/11 15:00IST

今回は全問からちょこちょこ(=部分点多数)得点できた。
最終104位。
(新レーティングまだ出てない)
→総合2195(+108), Long Challenge2043(+173)
f:id:n4_t:20170914055127p:plain:w288 f:id:n4_t:20170914055146p:plain:w288
(最初の数問だけ解いて放置した前回の失点が痛い)

CodeChefのLong Challengeはハードな時間制限がないし再提出についても緩い(ペナルティもないし、TopCoderのMMみたいな2時間待ちもない)から、問題だけ読んでおいてふと思いついたときに解いて時間のあるときに提出できるのが良い。趣味でやってる社会人競プロ勢に優しい。
cf.
上司に言われたこと「社会人になったら趣味を持て!」その理由に納得の声 - エキサイトニュース(1/3)

続きを読む

AtCoder Beginner Contest 073

先月の070に参加して以来のABC。
この1ヶ月でレーティングが1200を上回ったのでレート変更はない。

とりあえず4完したけどDで3WA出した…
オーバーフロー?とか思ってあれこれ見回してみた
先に食事して、ふと気づいた…WFのループの順番がi,j,kになってる
そこ直してAC

続きを読む

AtCoder Regular Contest 082

まさかの三完
oo-o 1400pts 120th, 1465→1660 (+195)
f:id:n4_t:20170902230441p:plain:w360
今回のパフォーマンスは2347だった

このグラフだと分からないけど青の上って何?黄色?
(青→黄色→オレンジ→赤だった。400刻みなので黄色は2000から)

続きを読む