夏休みが終わった

早いもので、もう夏休みが終わってしまいました。

競技プログラミングだけでなく、DTMで秋M3に出典したり色々やってましたが、その中で目標はどれくらい達成できたのでしょうかねー。とりあえず、夏休みでどれだけのことをしたかをざっと書いてみます。

夏休み中に出たプログラミングコンテスト

まとめました。

• AtCoder

日時	コンテスト名	結果	レート	diff
8/21	AtCoder Grand Contest 003	526th	642 -> 775	+133
8/28	AtCoder Beginner Contest 044	56th	775 -> 949	+174
9/11	AtCoder Beginner Contest 045	74th	949 -> 1050	+101
9/24	CODE FESTIVAL 2016 qual A	528th	1050 -> 1171	+121

割と順調にレート伸びた感じはするけど、もう少し伸ばしたかった。AGCでなかなか解けなかったのは今後の課題ですね。

• TopCoder

日時	コンテスト名	結果	レート	diff
8/11	Single Round Match 696 (Div.2)	161st	889 -> 768	-121
9/18	Single Round Match 698 (Div.2)	127th	768 -> 866	+98
9/27	Single Round Match 699 (Div.2)	316th	866 -> 805	-61

TopCoderに関しては本当にダメだった。レートは700点台と800点台を永遠に行き来していて緑色にすらなったことがないという悲惨な状況。もう少し過去問を解いて形式に慣れたい。というかUIもうすこしましにしてほしい・・・

• Codeforces

日時	コンテスト名	結果	レート	diff
9/17	Round #372 (Div.2)	4201st	unrated -> 1403
9/23	Round #373 (Div.2)	3175th	1403 -> 1366	-37
9/30	Round #374 (Div.2)	737th	1366 -> 1472	+106
(10/3)	Round #375 (Div.2)	1071st	1472 -> 1503	+30

夏休みも終わりに差し掛かったくらいから参加し始めた。レーティングのつき方が優しいので続けやすそうだなあと思った(初心者並みの感想) 10/3は本当は夏休みじゃないけどせっかくだから載せた。同じ英語開催コンテストだけど、個人的には(10/4現在)TopCoderの5000倍くらい好き。

この他にも、大学のサークル内で行われたVirtual Contestに5回くらい参加しましたが割愛します。

ライブラリ作成

夏休みに入ってから、競技プログラミングのライブラリ作成をはじめました。Dropboxで管理するととても快適なことがわかったので、そこにおいています。人様に見せられるところまで整備できれば公開するかもしれません(期待してはいけません)。

特に幾何ライブラリはだいぶ揃いました。AOJでVerifyしたりSpaghetti Source見たりしながら作ってました。たぶん間違いのないライブラリにはなっていると思いますが、もう少しVerifyが必要な気がします。

今後はグラフとか木とかのライブラリを充実させたいです。そもそもそこらへん詳しくないのでもう少し勉強します。

目標達成したか？

前の記事で定めた目標をどれくらい達成したかを書いてみます。

項目	点数	備考
CODE FESTIVAL 2016 予選突破	0	(突破して)ないです
TopCoder青色	0	(青どころか緑にもいって)ないです
AtCoder水色	0	あと29
AOJ200AC	0	夏休み前 35AC → 131AC
AtCoder200AC	5	夏休み前 136AC → 254AC (達成)
蟻本読破	0	精進が足りない
グラフ理論の本読破	0	同上
TOEIC模擬テスト5回分こなす	0	夏休み中で本を紛失した
AtCoderコンテスト150位以内	10	一応2回達成(ABC044, ABC045)

というわけで、合計15点。再履修不可避。夏休み再履修したい。

目標設定時から薄々感じてたけど、目標が高すぎました。今度こういうことやるときは実現可能な目標にしたいですね。

というわけで、ぼくのなつやすみはこれで終了。こどふぇす予選突破目指して頑張ります。

AOJ 0097: Sum of Integers II

やっぱり俺の敵はDPだ・・・

— つたじろう (@_TTJR_) 2016年8月10日

DPは難しい、はっきりわかんだね。

問題概要

原文 → 整数の和 | Aizu Online Judge

0 から 100 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力せよ。

解説

私はDPが書けないのでDPの練習をしました。

dp[ i ][ j ] = dp[取り出す個数][合計] = 組み合わせの数

という dp テーブルを作ります。ここで重要なのが、 i のループは逆順であるということです。こうしないと、 dp テーブルの更新時に i に関して自分の一つ前を見る関係で、「重複を許した」組み合わせの数を計算することになってしまい、「異なる」 n 個の数、という制約を満たすことができません。この辺が難しいですよね。rep の順序もこの通りに書かないとうまくいきません。

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
using namespace std;
int main() {
    ll dp[11][1010];
    dp[0][0] = 1;
    rep(k,0,101) repr(i,9,0) rep(j,0,1001-k) {
        dp[i+1][j+k] += dp[i][j];
    }

    int n, s;
    while(cin >> n >> s){
        if(n == 0 && s == 0) break;
        cout << dp[n][s] << endl;
    }
    return 0;
}

数をこなせばできるようになるんだろうか・・・

2017/2/3 追記: なんか人類が理解しにくいコードを書いていたので、もっとわかりやすく書きました。逆順ループは使っていません。

この問題は 0 があるのが非常に厄介なのですが、この組み合わせは (1 〜 100 から n 個選ぶときの組み合わせ) + (1 〜 100 から (n-1) 個選ぶときの組み合わせ) と等価になりますので、それで書いてあげればシンプルになります。

int dp[110][20][1010];
signed main() {
    int n, s;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    repq(i,1,100) repq(j,0,15) repq(k,0,1000) {
        dp[i][j][k] = dp[i-1][j][k];
        if(k - i < 0) continue;
        if(j != 0) dp[i][j][k] += dp[i-1][j-1][k-i];
    }
    while(cin >> n >> s, n || s) {
        cout << dp[100][n][s] + dp[100][n-1][s] << endl;
    }
    return 0;
}

配列再利用するなら (逆順ループ入ってもいいなら) こうも書けます。メモリ効率は良いですね。でもこれ元のやつとあまり大差ない気がする。

int dp[20][1010];
signed main() {
    int n, s;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    repq(i,1,100) repr(j,15,0) repq(k,0,1000) {
        if(k - i < 0) continue;
        if(j != 0) dp[j][k] += dp[j-1][k-i];
    }
    while(std::cin >> n >> s, n || s)
        std::cout << dp[n][s] + dp[n-1][s] << std::endl;
    return 0;
}

AOJ 0096: Sum of 4 Integers II

今日もAOJを埋めるだけの簡単なお仕事 (簡単とは言ってない)

問題概要

原文 → ４つの整数の和 | Aizu Online Judge

4000以下の正の整数が与えられる。0から1000までの範囲の整数の組でを満たす組み合わせの数を出力せよ。

解説

ナイーブ解法だと4重ループですが、とか間に合うわけありません。そこで、一旦「2つの0以上の整数の和がになる組み合わせの数」を0～2000の範囲で考え、配列に保存しておきます。

これがわかれば、「{の和がになる組み合わせ} = {の和がになる組み合わせ} + {の和がになる組み合わせ}」より、1つの入力あたり最大2001回の計算で解くことができます。が負になったり2000を超えたりしないように注意ですね。

ちなみに私は読解力がないので、が「0から1000までの整数」をとるという制約を忘れ、Combinationで解いてしまい最初死亡しました。まあおかげでCombinationのライブラリが副産物で出来上がったのでよしとしよう()

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
using namespace std;

int main() {
    int n;
    int a[2010];
    memset(a, 0, sizeof(a));
    rep(i,0,1001) rep(j,0,1001) a[i+j]++;
    while(cin >> n) {
        int ans = 0;
        rep(i,0,2001) {
            if(0 <= n-i && n-i <= 2000) ans = ans + a[i] * a[n - i];
        }
        cout << ans << endl;
    }
    return 0;
}