競技プログラミングで学ぶプログラミングの基礎

11/20（水）、11/21（木）13:00-16:30

回数：2日間

形式：対面（AICラウンジ）

主催：AIC

締切：11/18（月）12:00

塾生のお申し込みはこちら

社会人のお申し込みはこちら

プログラミングの世界に一歩踏み出してみませんか？

講習会の概要

競技プログラミングの基礎をしっかりと学ぶことで、文法の理解から計算量の効率化といったスキルを習得できます。それだけでなく、次に控える中上級者向けの競技プログラミング講習会や、機械学習などの高度な講習会にも役立てられる強固な基盤を築くことを目指しています。

プログラミング未経験の方も大歓迎です。各セッションでは、専門の講師が魅力的な解説と工夫を凝らした参考資料でサポートします。前半40分は講義形式で基礎を学び、後半40分は演習形式で実践力を高める充実したプログラムを提供いたします。

各回終了後には、使用したスライドなどを公開しますので、ご自宅での自習にもご活用いただけます。この講習会を機に、あなたもプログラミングのスキルを磨き、新しい可能性を広げてみませんか？
ご参加を心よりお待ちしております！

講師

原田賢利（理工学研究科）
石川裕一朗（理工学部　数理科学科）

日程

11/20（水）、11/21（木）　両日とも13:00から16:30
※2日間、途中参加不可

形式

対面（日吉協生館2階　AICラウンジ）

実施内容

1日目（11/20）	第１回 13:00～14:00 第２回 14:15～15:15	簡単な講習会の説明の後、基礎的な文法事項について学びます。主な内容として、変数と演算・場合分け・ループ処理・配列・ソートアルゴリズムなどが挙げられます。(参考書の第３章に相当します。)
	第３回 15:30～16:30	いくつかの問題を解くことで第１回・第２回で学んだ文法事項の演習をします。問題は実際のプログラミングコンテストで出題された問題から出題します。
2日目（11/21）	第４回 13:00～14:00 第５回 14:15～15:15	１日目に学習した文法事項の復習のほか、計算量やアルゴリズムの概念について学びます。余力のある方はより高度な演習問題に挑戦できます。 (参考書の第４章・第５章の一部に相当します。)
	第６回 15:30～16:30	最適解を求めることが難しいものに対して、短時間の計算でなるべく良い答えを求める「ヒューリスティック問題」を紹介します。１日目に学んだ文法事項が問題解決にどのように活かせるかを実感できると思います。

持ち物

ノートPC、AtCoder アカウント、紙とペンやタブレットなどメモできるもの

※ノートPC貸出希望の方はAICオフィスにご相談ください。
※講習会では、講師が参考文献に基づいて講義内容を用意します。参加者が個別に参考文献を購入する必要はありません。

演習例の回答はこちらをクリック

答え：860秒

ワーシャルフロイド法で各施設間の距離を求めた後、施設を訪れる順番を全探索すれば解くことが出来ます。

下の▶の行をクリックするとそれぞれの実装例（プログラムコード）を参照できます。

実装例(Python)

import itertools

res = 10000
resv = []
s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
name = ["日吉記念館", "藤山記念館", "塾生会館", "食堂", "保健管理センター", "第6校舎", "独立館", "図書館", "日吉駅", "AICラウンジ"]

cost = [[10000 for _ in range(10)] for _ in range(10)]

cost[0][1] = 130
cost[0][4] = 150
cost[0][7] = 180
cost[1][0] = 130
cost[1][2] = 70
cost[1][3] = 70
cost[1][4] = 130
cost[2][1] = 70
cost[2][3] = 20
cost[2][5] = 100
cost[2][6] = 80
cost[3][1] = 70
cost[3][2] = 20
cost[3][6] = 70
cost[3][7] = 50
cost[4][0] = 150
cost[4][1] = 130
cost[4][7] = 40
cost[4][9] = 60
cost[5][2] = 100
cost[5][6] = 130
cost[6][2] = 80
cost[6][3] = 70
cost[6][5] = 130
cost[6][7] = 50
cost[6][8] = 80
cost[7][0] = 180
cost[7][3] = 50
cost[7][4] = 40
cost[7][6] = 50
cost[7][8] = 110
cost[8][4] = 80
cost[8][6] = 80
cost[8][7] = 110
cost[8][9] = 60
cost[9][4] = 60
cost[9][7] = 80
cost[9][8] = 60

for k in range(10):
    for i in range(10):
        for j in range(10):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

for perm in itertools.permutations(s):
    if perm[0] != 8:
        continue
    sum_cost = 0
    for i in range(9):
        sum_cost += cost[perm[i]][perm[i + 1]]
    sum_cost += cost[perm[9]][perm[0]]
    
    if res > sum_cost:
        res = sum_cost
        resv = perm

print(f"cost: {res}")
print("route:")
for a in resv:
    print(name[a])
print("日吉駅")

実装例(C++)

#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    int res = 10000;
    vector<int> resv;
    vector<int> s = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    vector<string> name = {"日吉記念館", "藤山記念館", "塾生会館", "食堂", "保健管理センター", "第6校舎", "独立館", "図書館", "日吉駅", "AICラウンジ"};
    vector<vector<int>> cost(10, vector<int>(10, 10000));
    cost[0][1] = 130;
    cost[0][4] = 150;
    cost[0][7] = 180;
    cost[1][0] = 130;
    cost[1][2] = 70;
    cost[1][3] = 70;
    cost[1][4] = 130;
    cost[2][1] = 70;
    cost[2][3] = 20;
    cost[2][5] = 100;
    cost[2][6] = 80;
    cost[3][1] = 70;
    cost[3][2] = 20;
    cost[3][6] = 70;
    cost[3][7] = 50;
    cost[4][0] = 150;
    cost[4][1] = 130;
    cost[4][7] = 40;
    cost[4][9] = 60;
    cost[5][2] = 100;
    cost[5][6] = 130;
    cost[6][2] = 80;
    cost[6][3] = 70;
    cost[6][5] = 130;
    cost[6][7] = 50;
    cost[6][8] = 80;
    cost[7][0] = 180;
    cost[7][3] = 50;
    cost[7][4] = 40;
    cost[7][6] = 50;
    cost[7][8] = 110;
    cost[8][4] = 80;
    cost[8][6] = 80;
    cost[8][7] = 110;
    cost[8][9] = 60;
    cost[9][4] = 60;
    cost[9][7] = 80;
    cost[9][8] = 60;
    for(int k = 0; k < 10; k++){
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < 10; j++){
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
    do{
        if(s[0] != 8) continue;
        int sum = 0;
        for(int i = 0; i < 9; i++){
            sum += cost[s[i]][s[i+1]];
        }
        sum += cost[s[9]][s[0]];
        if(res > sum){
            res = sum;
            resv = s;
        }
    }while(next_permutation(s.begin(), s.end()));
    cout << "cost: " << res << endl;
    cout << "route:" << endl;
    for(auto a : resv) cout << name[a] << endl;
    cout << "日吉駅" << endl;
}