2014年度 OPTiM プログラミング勉強会

12月13日土曜日に東京本社で開かれたプログラミング勉強会に参加してきました。

簡単に思い出せる範囲で振り返ろうと思います。

12:30

30分早く本社に着いてしまった。近くのDOUTORで時間を潰した。

13:15

受付をすませ、担当者の指示に従って荷物を置いて席に着いた。
交通費の支払いの書類とかn回ぐらい書き間違えて辛さが高まった。

自己紹介タイム

聞いている限りでは、意外とプログラミングが苦手(というより好きではない)という人が複数人いたことが驚きだった。
どこへ行っても自己紹介はミスるので無難なものを予め用意したほうが良いという結論に至った。

以下の講演のまとめは抜けていたり勘違いしてるところもあると思いますがお許し下さい。

講演1 「企画チームの役割と仕事の話」

• 講演者は素粒子論研修室出身。
• 企画でやることと研究でやることは似ているので(競合調査とかは論文調査に対応できる)結構楽らしい。
• 「Google検索できない奴は死ね!」
• 課題対応で、開発職とバトることがよくある

講演2 「品質の話」

• 講演者の話し方が上手いと感じたので参考にする。
• 品質の定義「顧客の要求度合い」
• これに顧客の暗黙の要求も考えないといけない。
• 品質と顧客満足度の関連は高い。
• 全体的に見ても開発の流れの話が多くて難しいという印象を受けた。

講演3 「バージョンアップの話」

• マイナー/メジャーアップデート
• JenkinsとIRCで作業の自動化
• スライドがあるので細かい話はそれを見れば良さそう。

バージョンアップに負けないためのプラクティス from Yuji Tokuda

ディスカッション

• テーマは「イケているクラウドサービス」を探すというもの
• イケているの定義とかクラウドサービスの定義とかあやふやすぎて最終的にクラウドサービスではないものを挙げてしまっていた…。
• なかなか個性的なメンバーが集まっていた気がする。
• ディスカッションは全然経験無かったけど楽しかった(小並感)
• ただ同じ人が喋ってるばかりだとつまらないし意見も偏るし生産的でないなと感じた。

懇親会

• 寿司！

• ディスカッションで探してきたサービスを各グループごとに前で発表した。スライドとか使うのかなと思ったけど、ホワイトボードで説明するところがほとんどだった。自分は終始否定意見ばかり行っていた気がして、否定意見出すだけなら簡単なことなので申し訳ないなぁと感じた。
• 全然話せてなかった社員の方々・学生の方々とこの時間で話せてよかった。
• まさか、サイコロ出してくるとは思わなかった（完全に内輪ネタ)

おわりに

プログラミング勉強会という名前は抽象的すぎるし、どちらかというと開発方面の話では無かったが、企画がどういう仕事をしているとかサービスを公開するまでの流れを知れたことは良い経験になったと思う。
こういう勉強会がこれからも開かれるなら積極的に参加したい。しかし、受験生なのでそろそろ受験勉強します(小声)。

Codeforces Round #284 Div2

久しぶりにcodeforcesに出た。Cが幾何で愚直に線分交差判定しようとして謎バグで死んだ。普通に代入して不等式で判別するだけで解けるらしい。数学力の無さ…。

A

int main() {
    ios_base::sync_with_stdio(0);
    vector<pair<int,int>> v;
    int n, x, a, b, ans = 0;
    cin >> n >> x;
    rep(i, n) {
        cin >> a >> b;
        v.pb(mp(a,b));
    }
    sort(all(v));

    int p = 0, m = v[n-1].second;
    rep(i, v.size()) {
        for(; p <= m; p += x) {
            if(p + x >= v[i].first) {
                break;
            }
        }
        ans += v[i].second - p;
        p = v[i].second;
    }

    cout << ans << endl;
}

B

int main() {
    ios_base::sync_with_stdio(0);

    int n, l;
    cin >> n >> l;

    string a,b,c;
    map<string, string> m;
    rep(i,l) {
        cin >> a >> b;
        if(a.size() > b.size()) {
            m[a] = b;
        } else {
            m[a] = a;
        }
    }

    cin >> c;
    cout << m[c];
    rep(i,n-1) {
        cin >> c;
        cout << ' ' << m[c]; 
    }
    cout << endl;
}

// あとでコード上げる

Code Festival 2014 予選A

精神的にくるものがあったので久しぶりに記事を書く。

予選開始

• A問題開く。通す。
• B問題開く。通す。
• C問題開く。通す。
• D問題開く。貪欲に上から決めていけば解けそう…。
• 少し悩んでも良い実装が思い浮かばない。
• しょうがなく桁DPを書く。
• 提出する。WA...
• 原因がわからないまま終了。

反省

D問題、どうせ通るし30点取りに行かなくてもいいかなと思ってたら嵌って本選に行けない順位になってしまった。戦略ミスだなぁ。死にたさ極まる。

A問題

int main() {
    string s;
    cin >> s;
    s += "2014";
    cout << s << endl;
}

B問題

int main() {
    string A;
    long long B;
    cin >> A >> B;

    cout << A[(B - 1) % A.size()] << endl;
}

C問題

int f(int x) {
    return x / 4 - x / 100 + x / 400;
}

int main() {
    int A, B;
    cin >> A >> B;
    cout << f(B) - f(A - 1) << endl;
}

D問題

はまったところは2つあった。

• 10000 1のようなケースを想定できてなかった。
• 全ての状態を考えずにdpの処理部書いてた。

あと、添字ミスもあったしホント辛くなりますよ〜…。

const long long INF = 1e16;
const int M = 10;

long long dp1[20][4][1 << 12];
long long dp2[20][4][1 << 12];

int main() {
    string A;
    long long K, ans = INF;

    cin >> A >> K;

    int m = A.size();

    for(int i = 0; i < m; i++) {
        for(int k = 0; k < (1 << M); k++) {
            for(int b = 0; b < 2; b++) {
                dp1[i][b][k] = INF;
                dp2[i][b][k] = INF;
            }
        }
    }

    for(int i = 0; i < 10; i++) {
        int n = A[0] - '0';
        int S = (i == 0 ? 0 : 1 << i);
        if(n - i >= 0) dp1[0][(n - i) > 0][S] = n - i;
        if(i - n >= 0) dp2[0][(i - n) > 0][S] = i - n;
    }

    // pos
    for(int i = 1; i < m; i++) {
        int n = A[i] - '0';
        // carry bit
        for(int b = 0; b < 2; b++) {
            // used number
            for(int k = 0; k < (1 << M); k++) {
                // next number
                for(int l = 0; l < 10; l++) {
                    long long borrow = 0;
                    long long add = n - l;
                    bool c = add > 0;
                    int S = (l == 0 && k == 0 ? 0 : k | (1 << l));
                    int count = __builtin_popcount(S);
                    if(count > K) { continue; }

                    if(add >= 0 && b) {
                        dp1[i][0][S] = min(dp1[i][0][S], (dp1[i-1][b][k] + borrow) * 10LL + add);
                        dp1[i][1][S] = min(dp1[i][1][S], (dp1[i-1][b][k] + borrow) * 10LL + add);
                    }

                    if(add < 0 && !b) continue;

                    if(add < 0) {
                        add += 10;
                        c = add > 0;
                        borrow = -1;
                    }

                    dp1[i][c][S] = min(dp1[i][c][S], (dp1[i-1][b][k] + borrow) * 10LL + add);
                } 
                
                for(int l = 0; l < 10; l++) {
                    long long borrow = 0;
                    long long add = l - n;
                    bool c = add > 0;
                    int S = (l == 0 && k == 0 ? 0 : k | (1 << l));
                    int count = __builtin_popcount(S);
                    if(count > K) { continue; }

                    if(add >= 0 && b) {
                        dp2[i][0][S] = min(dp2[i][0][S], (dp2[i-1][b][k] + borrow) * 10LL + add);
                        dp2[i][1][S] = min(dp2[i][1][S], (dp2[i-1][b][k] + borrow) * 10LL + add);
                    }
                    
                    if(add < 0 && !b) continue;

                    if(add < 0) {
                        add += 10;
                        c = add > 0;
                        borrow = -1;
                    }

                    dp2[i][c][S] = min(dp2[i][c][S], (dp2[i-1][b][k] + borrow) * 10LL + add);
                }
            }
        }
    }

    for(int j = 0; j < 2; j++) {
        for(int k = 0; k < (1 << M); k++) {
            ans = min(ans, dp1[m-1][j][k]);
            ans = min(ans, dp2[m-1][j][k]);
        }
    }

    cout << ans << endl;
}

JOI 2012-2013 本選 問題1 電飾

反転回数は最大でも1回かと思っていたけど2回だった。反省

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 前回反転させた, 前回のランプ, 場所
int dp[3][2][100001];

int main() {
	int n, k, ans = 0;
	vector<bool> a;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> k;
		a.push_back(k);
	}

	dp[0][a[0]][0] = dp[1][!a[0]][0] = 1;

	for(int i = 1; i < n; i++) {
		dp[0][a[i]][i] = max(dp[0][a[i]][i], dp[0][!a[i]][i-1] + 1);
		dp[1][!a[i]][i] = max(dp[1][!a[i]][i], dp[1][a[i]][i-1] + 1);
		dp[1][!a[i]][i] = max(dp[1][!a[i]][i], dp[0][a[i]][i-1] + 1);
		dp[2][a[i]][i] = max(dp[2][a[i]][i], dp[2][!a[i]][i-1] + 1);
		dp[2][a[i]][i] = max(dp[2][a[i]][i], dp[1][!a[i]][i-1] + 1);
		ans = max(ans, dp[0][a[i]][i]);
		ans = max(ans, dp[1][!a[i]][i]);
		ans = max(ans, dp[2][a[i]][i]);
	}

	cout << ans << endl;
}

JOI 2013-2014 予選4番

最近forで回すDPの方が書きやすい、と感じている

最初、鍵を持っている人の情報を持ってしまっていて重複したケースも数え上げてしまっていて時間が結構かかった。

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const int MOD = 10007;

// J = 0bit, O = 1bit, I = 2bit
// i日目, 参加した人(bit表現)
int dp[1001][12];

int main() {
        map<char, int> D;
        D['J'] = 0, D['O'] = 1, D['I'] = 2;
        int N, ans = 0;
        string S;

        cin >> N >> S;

        for(int i = 0; i < 1 << 3; i++) {
                if(((i >> D[S[0]]) & 1) && ((i >> D['J']) & 1)) {
                        dp[0][i] = 1;
                }
        }

        for(int i = 1; i < N; i++) {
                for(int j = 0; j < 1 << 3; j++) {
                        for(int k = 0; k < 1 << 3; k++) {
                                for(int l = 0; l < 3; l++) {
                                        if((k >> D[S[i]] & 1) && ((k >> l) & 1) && ((j >> l) & 1))
                                        {
                                                dp[i][k] += dp[i-1][j];
                                                dp[i][k] %= MOD;
                                                break;
                                        }
                                }
                        }
                }
        }

        for(int i = 0; i < 1 << 3; i++) {
                ans += dp[N-1][i];
                ans %= MOD;
        }

        cout << ans << endl;
}

PKU 1036

少し読解困難だった．
はTLEするが，の処理は外に出すことができるためとなる．

dp[i][j] := i時間で扉がjの状態であるときに，来訪するgang達の価値の総和の最大値

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

const int INF = 1 << 30;

int dp[2][101];

int main() {
    int N, K, T, t[101], p[101], s[101], ans = 0;

    cin >> N >> K >> T;

    for(int i = 0; i < N; i++) { scanf("%d", &t[i]); }
    for(int i = 0; i < N; i++) { scanf("%d", &p[i]); }
    for(int i = 0; i < N; i++) { scanf("%d", &s[i]); }

    for(int i = 0; i < 2; i++) for(int j = 0; j <= K; j++)
        dp[i][j] = -INF;

    dp[0][0] = 0;

    for(int i = 1; i <= T; i++) {
        int n = i & 1;
        int c = !n;

        for(int j = 0; j <= K; j++) {
            dp[n][j] = dp[c][j];
            if(j+1 <= K) dp[n][j] = max(dp[n][j], dp[c][j+1]);
            if(j-1 >= 0) dp[n][j] = max(dp[n][j], dp[c][j-1]);
        }

        for(int j = 0; j < N; j++) {
            if(i != t[j]) continue;
            dp[n][s[j]] += p[j];
        }
    }

    for(int i = 0; i <= K; i++) {
        ans = max(ans, dp[T&1][i]);
    }

    cout << ans << endl;
}

JMC 2014 4番

pastaっぽいと思った。作問のプロだと感じた(小並感)

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int dp[128][128][2];
bool m[128][128];
const int MOD = 100000;

int main() {
	int N, M, L, a, b;
	cin >> N >> M >> L;

	for(int i = 0; i < L; i++) {
		cin >> a >> b;
		a--, b--;
		m[a][b] = true;
	}

	for(int i = 0; i < M; i++) {
		if(!m[0][i]) dp[0][i][0] = 1;
	}


	for(int i = 0; i < N - 1; i++) { 
		for(int j = 0; j < M; j++) {
			for(int k = 0; k < 2; k++) {
				if(k == 0) {
					if(m[i + 1][j]) continue;
					dp[i + 1][j][!k] += dp[i][j][k];
					dp[i + 1][j][!k] %= MOD;
				} else {
					for(int l = 0; l < M; l++) {
						if(m[i + 1][l]) continue;
						a = (l == j ? k : !k);
						dp[i + 1][l][a] += dp[i][j][k];
						dp[i + 1][l][a] %= MOD;
					}
				}
			}
		}
	}

	int ans = 0;

	for(int i = 0; i < M; i++) {
		ans += dp[N - 1][i][1];
		ans %= MOD;
	}

	cout << ans<< endl;
}