2020-06-20

北海道大学周辺グルメ

これはなに

北海道大学に入学してから 4 年と 3 ヶ月がたちました．一人暮らしをしていると，どうしても外食が多くなります．そんな僕が，北大周辺のグルメを様々なジャンルを横断して紹介したいと思います．いずれも HUPC の会場から徒歩圏内です．

焼きスープカレー専門店 Curry Ya ASAP

札幌には数多くの有名スープカレー屋さんがあります．そんな中でも僕が一番オススメしたいのは，こちらの「焼きスープカレー専門店 Curry Ya ASAP」．

数多くの料理店で修行をした店主さんが，個人でやっているお店になります（open 当初にそのような説明が店内に書いてあった気がしています．間違ってたらすいません）リンク

f:id:monkukui:20200620152430p:plain — いろいろ野菜カレー

スパゲティAndare

筆者が一番よく行くお店です．定番のスパゲティや変わり種のスパゲティがあります．サイドメニューも洒落ていて，何を注文しても楽しめるお店です．常連になると，裏メニューが 50 個追加されます（店主さんの裏メニューメモをプレゼントされます．）リンク

f:id:monkukui:20200620153712p:plain — なすトマトベーコン

f:id:monkukui:20200620153748p:plain — 牡蠣のクリームパスタ

f:id:monkukui:20200620153823p:plain — 鮭の白子燻製

海味はちきょう本店

言わずと知れた「つっこ飯」のお店．漁師風の店主さんがいくらを嫌という程つっこんでくれるのがうり．筆者は，最初に見たとき食べきれるか心配でしたが，いくらの質がとてもよく，一人でペロリと完食しました．リンク

f:id:monkukui:20200620154158p:plain — つっこ飯

えびそば一幻総本店

オススメのラーメン屋はたくさんありすぎて紹介しきれないのですが，ここではこちらの店を紹介します．「すすきの」の方まで足を運ぶと美味しいラーメン屋さんがたくさんある印象です．リンク

f:id:monkukui:20200620154532p:plain — そのまま・えびみそ

夜空のジンギスカン本店

北海道を語る上で外せないのは，ジンギスカンですね．こちらのお店がコスパ最強（若干パフォーマンスに振れている（ちょっと高いけど，めちゃくちゃ美味しい））です．本店と姉妹店がありますが，本店に行くことをオススメします．（メニューが全然違うし，味が美味しかった）リンク

f:id:monkukui:20200620154932p:plain — ジンギスカン個別注文たくさん

いかがでしたか？

HUPC2020 の申し込みは本日（6/20）の 18:00 からです．みなさま，奮ってご参加ください！

2020-05-24

Slack の api を使って，授業の出席管理システムを開発した

背景

新型コロナウイルスの影響で，オンライン授業を導入している大学は少なくない．北海道大学の学部の授業も，オンラインで進める方針だ．学生の出席管理を，学生と教員双方にとって簡単に実現すべく，Slack 上での出席管理システムを開発した．（メールなどでの出席をするのは，送る側もめんどくさいし，確認する側も大変である）

成果物

f:id:monkukui:20200524145426p:plain — slack の出席チャンネルの様子

f:id:monkukui:20200524145522p:plain — スプレッドシートに出力される

やったこと

Slack の Outgoing Webhooks ってやつで bot を登録
チャンネル内の発言を拾って，Google Apps Script を起動
GAS で，スプレッドシート書き込み処理と，Slack の api（チャンネルへの POST）処理を行う

api.slack.com

developers.google.com

感想

ほむらちゃんありがと

slack の api を開発したい
とあるチャンネルで発言したら，発言内容と slack id を拾ってスプレッドシートかなんかに出力したい
これってできるかしら
— monkukui (@monkukui2) 2020年5月21日

こういうの？ https://t.co/Hfbc22u9hu
— homu (@homuhomucomp) 2020年5月21日

やりたいことにより近そうなのありました (ただ token 作れなくなったからここから工夫する必要はある) https://t.co/TadMXE09G5
— homu (@homuhomucomp) 2020年5月21日

あ、出席管理か
ならこれが一番近そうですね https://t.co/G677h0nWUK
— homu (@homuhomucomp) 2020年5月21日

2020-05-21

初めて OSS に commit した話

きっかけ

OSS にコミットっていうやつを，学生のうちにやってみたいなぁ
— monkukui (@monkukui2) 2020年5月13日

yosupo judge で作問するといいですよ (Issue にあってまだ手がつけられていないネタをやるか、新しくネタを作るか、どちらでもいいと思っている)
— tsutaj (@tsutaj) 2020年5月13日

Library Checker

github.com

やったこと

問題原案を issue で提案し，以下の作業を終えて Pull Request を出した．

問題文
generator
input checker
output checker

作業内容については，ドキュメントを読めば完全に理解できました．ドキュメントとはかくあるべきだなぁと感じました．

また，よすぽさんのサポートがとても手厚くて，プログラムの間違いなどを優しく指摘していただきました．ありがとうございました．

library-checker-problems/guideline.md at master · yosupo06/library-checker-problems · GitHub

作った問題

木構造が与えられて，木の直径（最遠頂点対の距離）を求める問題です． judge.yosupo.jp

2019-12-29

PAST：第一回アルゴリズム実技検定の解説　〜エントリーを目指して〜

はじめに

アルゴリズム実技検定，通称「PAST」とは，AtCoder 株式会社が主催するプログラミングの実技検定です．

past.atcoder.jp

検定結果に応じて，エキスパート，上級，中級，初級，エントリーの 5 段階の認定が与えられます． PAST の特徴は，選択肢回答による知識型の検定試験とは異なり，1 からアルゴリズムを考えプログラムを書かせて実行し，その結果で能力を判定する点です．つまり，実践的なコーディング力を正確に測ることができる検定だと言えるでしょう．

2019/12/14 に第一回目の検定が実施され，受験した結果「エキスパート」の認定が授与されました！今回は，出題された計 15 問のうち，前半 4 つの問題の解説，およびソースコードの掲載を試みます．なお，掲載されるコードは C++ です．ご了承ください．

はじめに
A 問題「2 倍チェック / Is It a Number?」
B 問題「増減管理 / Up and Down」
C 問題「3 番目 / The Third」
D 問題「重複検査 / Duplicated?」
最後に

A 問題「2 倍チェック / Is It a Number?」

A - 2 倍チェック / Is It a Number?

問題概要

長さ 3 の文字列 $s$ が与えれれる． $s$ の各文字が '0' 〜 '9' であるなら， $s$ を数としてみた値に 2 倍した値を出力せよ．そうでない場合，"error" を出力せよ．

制約

$s$ の長さは 3 である． $s$ の各文字は数字または英小文字である．

解説

いきなり気をつけることが多い問題です．以下のステップでコードを書くと，正解が得られます．

各文字は '0' 〜 '9' であるか．

for (auto c: s) {
  if (isdigit(c)) ...

と書けます.

文字列を整数に変換する．

std::stoi 関数で，std::string 型から int 型への変換ができます．例えば "00112" という文字列も 112 という整数に変換してくれます．便利ですね．

最後に 2 倍して出力

ソースコード

int main(){
    
  string s; cin >> s;
  for(int i = 0; i < 3; i++) {
    if(!isdigit(s[i])) {
      cout << "error" << endl;
      return 0;
    }
  }

  int n = stoi(s);
  cout << 2 * n << endl;

  return 0;
}

B 問題「増減管理 / Up and Down」

B - 増減管理 / Up and Down

問題概要

長さ $n$ の数列 $a_1, a_2, \ldots, a_n$ が与えられる．各 $i$ $(2 \leq i \leq n)$ に対して， $a_{i - 1} \lt a_i$ なら "up" と $a_i - a_{i - 1}$ を空白区切で， $a_{i - 1} \gt a_i$ なら "down" と $a_{i - 1} - a_i$ を空白区切で， $a_{i - 1} = a_i$ なら "stay" を出力せよ．

制約

$2 \leq n \leq 100000$

解説

for 文と if 文が書けるかを問う問題です． A 問題より，こちらの方が簡単に感じました．

ソースコード

int main(){
  
  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];

  for(int i = 1; i < n; i++) {
    if(a[i] == a[i - 1]) cout << "stay" << endl;
    else if(a[i] > a[i - 1]) cout << "up " << a[i] - a[i - 1] << endl;
    else cout << "down " << a[i - 1] - a[i] << endl;
  }
  return 0;
}

C 問題「3 番目 / The Third」

C - 3 番目 / The Third

問題概要

6 つの整数が与えられるので，小さい方から 4 番目の整数を出力せよ．

解説

std::vector や配列などで整数を受け取り，昇順ソートした後に 4 番目の値を出力します．ソートに関しては自分で実装する必要はなく，多くのプログラミング言語の標準機能で使えます．ここまで解けると「エントリー」の認定が与えられます．

ソースコード

int main(){
  vector<int> a(6);
  for(int i = 0; i < 6; i++) cin >> a[i];
  sort(a.begin(), a.end());
  cout << a[3] << endl;
  return 0;
}

D 問題「重複検査 / Duplicated?」

D - 重複検査 / Duplicated?

問題概要

長さ $n$ の数列 $a_1, a_2, \ldots, a_n$ が与えられる．数列 $a$ は，長さ $n$ の順列の，高々 1 つの値が $1 \leq x \leq n$ を満たす整数 $x$ に書き換わったものである．（一つも書き換わっていない可能性もある）

書き換わりが発生していなければ "Correct" を出力し，書き換わりが発生していれば，書き換わった後の整数と書き換わる前の整数を空白区切で出力せよ．

制約

$1 \leq n \leq 200000$

解説

各値が何回出現したかを調べます． $1$ から $n$ までの全ての値がちょうど 1 回づつ出現していれば，"Correct" を出力します．そうでない場合，書き換わる前の値の出現回数は 0 になり，書き換わった後の値の出現回数は 2 になるので，そのような二つの値を探して出力します．計算量は $O(n)$ です．

ソースコード

int main(){
  
  int n; cin >> n;
  // cnt[i] := 値 i が何回出現したか
  vector<int> cnt(n + 1, 0);
  for(int i = 0; i < n; i++) {
    int a; cin >> a;
    cnt[a]++;
  }
  
  bool ok = true;
  for(int i = 1; i <= n; i++) {
    // 値が書き変わらない場合，全ての値はちょうど 1 回出現している．
    if(cnt[i] != 1) ok = false;
  }

  if(ok) {
    cout << "Correct" << endl;
  } else {
    // from から to に値が書き換わる．
    int to;
    int from;
    for(int i = 1; i <= n; i++) {
      if(cnt[i] == 0) from = i;
      if(cnt[i] == 2) to = i;
    }
    cout << to << " " << from << endl;
  }
  return 0;
}

最後に

当初は全問題の解説を試みていましたが，途中で挫折しました．そのことをえびちゃん（@rsk0315）に伝えたら，たった 1 日で全問題の解説記事を書き上げてくれました． E 問題以降の解説はこちらを参照してください．

はてなブログに投稿しました #はてなブログ
PAST アルゴリズム実技検定 #1 解説 - えびちゃんの日記https://t.co/Ge4X33kFN7
— えびちゃん (@rsk0315_h4x) 2019年12月28日

2019-03-08

RUPC2019 day3 の writer 解まとめ

RUPC 2019 お疲れさまでした
day3 北大セットの writer 解(A B C D F) を掲載します
詳しい解説などは解説スライドを参照ください

RUPC Day3 の解説が生えたマジ？
※download または full screen しないと見れないものが一部あり
A: https://t.co/B9W5qJAu1O
B: https://t.co/FHgjp89tUp
C: https://t.co/kYLnbyiHCu
D: https://t.co/MkOa5IcXf1
E: https://t.co/bQA621ssXS
F: https://t.co/7u2EYYzcwO
G: https://t.co/9FB0spIaoE
— tsutaj (@_TTJR_) March 7, 2019

[問題リンク]
Aizu Online Judge Arena

A問題: 情報検索

尺取り解を掲載します

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

int main(){

    int n, m; cin >> n >> m;
    vector<int> a(n);
    vector<int> b(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];

    vector<int> and_result;
    vector<int> or_result;

    int j = 0;
    for(int i = 0; i < n; i++){
        while(j < m && b[j] <= a[i]){

	    if(a[i] == b[j]){ 
		and_result.push_back(a[i]);
	    }else{ 
		or_result.push_back(b[j]);
	    }
    
            j++;
	}
		
	or_result.push_back(a[i]);
    }

    for(;j < m; j++) or_result.push_back(b[j]);

    cout << and_result.size() << " " << or_result.size() << endl;
    for(int i = 0; i < and_result.size(); i++) cout << and_result[i] << endl;
    for(int i = 0; i < or_result.size(); i++) cout << or_result[i] << endl;
    return 0;
}

B 問題: 括弧を語る数

本質は同じですが、僕は stack を使いませんでした

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

int main(){

    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        //i 番目の閉じ括弧が in 番目の開き括弧に対応
        int in; cin >> in;
        in--;
        a[in] = i;
    }

    vector<int> vec(n, 0);
    
    int cnt = 0;
    for(int i = 0; i < n; i++){

        //i := 消費している開き括弧
        //cnt := 消費している閉き括弧
        int idx = i + a[i] - cnt;
        if(idx < 0 || n - 1 < idx){
            cout << ":(" << endl;
            return 0;
        }
        vec[idx]++;
        cnt += vec[i];
    }

    for(int i = 0; i < n; i++){
        cout << "(";
        for(int j = 0; j < vec[i]; j++) cout << ")";
    }

    cout << endl;

    return 0;
}

C 問題: 約数ゲーム

実装自体は素因数分解と約数列挙です

#include<iostream>
#include<vector>
#include<map>
using namespace std;

#define int long long

vector<int> ans_max(int n){
    vector<int> res;
    for(int i = 1; i * i <= n; ++i){
        if(n % i != 0) continue;
        res.push_back(i);
        if(n/i == i) continue;
        res.push_back(n/i);
    }
    return res;
}

map<int, int> ans_min(int n){
    map<int, int> res;
    if(n == 1){
        res[n] = 1;
        return res;
    }
    for(int i = 2, _n = n; i*i <= _n; i++){
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }

    if(n != 1) res[n] = 1;
    return res;
}

signed main(){
    
    int n; cin >> n;
    cout << ans_min(n).size() << " " << ans_max(n).size() - 1 <<  endl;
    return 0;
}

D問題矢

矢の長さにかかわらず、m[0] - 1 の損失はおこります。
また x = n + 1 の位置に送風機があることとします。
こうすることで、座標の両端に送風機があることとして問題を解くことができます。

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

int main(){

    //入力
    int N, M; cin >> N >> M;
    vector<int> m(M);
    for(int i = 0; i < M; i++) cin >> m[i];
    m.push_back(N + 1);
    vector<int> a(N, 0);

    // 前処理
    for(int i = 1; i <= M; i++){
        a[m[i] - m[i - 1] - 1]++;
    }

    vector<int> dp(N + 1);
    dp[N] = m[0] - 1;
    int sum = 0;
    for(int i = N - 1; i >= 0; i--){
        sum += a[i];
        dp[i] = dp[i + 1] + sum;
    }

    //二分探索
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        int x; cin >> x;
        int l = 0;
        int r = N + 1;
        while(r - l > 1){
            int d = (r + l) / 2;
            if(dp[d] > x) l = d;
            else r = d;
        }

        if(r == N + 1) cout << -1 << endl;
        else cout << r << endl;
    }

    return 0;
}

問題F: 赤黒そーるじぇむ

包除原理です。
包除原理を知ってる人は解説スライドを参考にしてください。
知らない人は以下のスライドを参考にしてください。
http://compro.tsutajiro.com/archive/181015_incexc.pdf

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2020;
int comb[MAXN][MAXN];
int N, M;

void init(){
    for(int i = 0; i < MAXN; i++){
        comb[i][0] = 1;
        for(int j = 1; j <= i; j++){
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M;
        }
    }
}

int mod_pow(int x, int n){
    int res = 1;
    while(n > 0){
        if(n & 1) res = res * x % M;

        x = (x * x) % M;
        n = n >> 1;
    }
    return res;
}


signed main(){

    cin >> N >> M;
    init();
    int ans = 0;

    // r := 赤の個数
    // b := 黒の個数
    for(int r = 1; r < N; r++){
        int b = N - r;
        int sum = 0;
        
        // x := 絶対無視する黒の個数
        for(int x = 0; x <= b; x++){
            int canUse = (b - x);
            int val = (mod_pow(2, canUse) - 1 + M) % M;
            val = mod_pow(val, r) % M;
            val = val * comb[b][x];
            val %= M;
            if(x % 2 == 0) sum = (sum + val    ) % M;
            else           sum = (sum - val + M) % M;
            sum %= M;
        }

        ans += ( ( ( sum % M * comb[N][r] ) % M * mod_pow(2, r * (r - 1) / 2) ) % M * mod_pow(2, b * (b - 1) / 2) ) % M;
        ans %= M;
    }

    cout << ans << endl;
    return 0;
}

2019-03-08

RUPC2019 DAY2 の解いた問題まとめ

RUPC2019 お疲れさまでした。
DAY2 の解いた問題のまとめをソースコードとともに掲載します。
[問題リンク]
Aizu Online Judge Arena

A問題: Lunch

pair に {値段, 名前} を格納し、ソートする。

#include<bits/stdc++.h>
using namespace std;

signed main(){

    char c[3] = {'A', 'B', 'C'};
    vector<pair<int, char> > v(3);
    for(int i = 0; i < 3; i++){
        int x; cin >> x;
        v[i] = {x, c[i]};
    }

    sort(v.begin(), v.end());
    cout << v[2].second << endl;
    
    return 0;
}

B 問題: Milk

交換できる回数は max(0, (x - b)) / (a - b) で求まる

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007LL;

signed main(){
    
    int a, b, x; cin >> a >> b >> x;    
    cout << (x + ((max(0LL, (x - b)) / (a - b)) % MOD) * (b % MOD) ) % MOD << endl;
    return 0;
}

C 問題: Phone Number

ボタンの並び方は 9! 通りなので、全探索できる。
G[i][j] := i -> j と指を動かす回数をあらかじめ求めておく。

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007LL;

signed main(){
    
    int n; cin >> n;
    string s; cin >> s;
    int G[10][10] = {};
    for(int i = 1; i < n; i++){
        int cur = (int)(s[i - 1] - '0');
        int nxt = (int)(s[i] - '0');
        G[cur][nxt]++;
    }
    
    vector<int> vec(9);
    for(int i = 0; i < 9; i++) vec[i] = i + 1;
    int ans = INF;
    vector<int> ansV(9);
    
    do{
        int phone[3][3];
        for(int j = 0; j < 3; j++){
            for(int i = 0; i < 3; i++){
                phone[i][j] = vec[3 * j + i];
            }
        }

        int cost = 0;
        for(int ci = 0; ci < 3; ci++){
            for(int cj = 0; cj < 3; cj++){
                for(int ni = 0; ni < 3; ni++){
                    for(int nj = 0; nj < 3; nj++){
                        int cur = phone[ci][cj];
                        int nxt = phone[ni][nj];
                        int dis = (int)abs(ci - ni) + (int)abs(cj - nj);
                        cost += G[cur][nxt] * dis;
                    }
                }
            }
        }

        if(cost < ans){
            ans = cost;
            ansV = vec;
        }

    }while(next_permutation(vec.begin(), vec.end()));
    
    for(int j = 0; j < 3; j++){
        for(int i = 0; i < 3; i++){
            cout << ansV[3 * j + i];
        }
        cout << endl;
    }
    return 0;
}

D 問題: Tunnel

dp[i][j] := y_i までが決まっており、y_i = j となったときの面積の最大値
y の取りうる範囲を 1 <= y <= M とると、遷移は O(M) かかり、全体として O(N M^2)
m = 500 と適当に決めてといた。
算数パートは、(1)三角形が二つできるパターンと、(2)台形が一つのパターンの二つの場合分けをした。

#include<bits/stdc++.h>
using namespace std;
#define MAX_HIGHT 500
const int MOD = 1000000007LL;

signed main(){
    
    int n; cin >> n;
    vector<double> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];
    vector<vector<double> > dp(n + 1, vector<double> (MAX_HIGHT + 10, 1e18));
    dp[0][1] = 0.0;
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= MAX_HIGHT; j++){
            if(dp[i][j] == 1e18) continue;

            for(int k = 1; k <= MAX_HIGHT; k++){

                double L = abs(h[i] - j);
                double R = abs(h[i] - k);
                double S;
                if((h[i] - j) * (h[i] - k) <= 0){
                    
                    //三角形二つ
                    if(abs(L * L + R * R) < 1e-8) S = 0.0;
                    else S = (L * L + R * R) / (2.0 * (L + R));                    
                }else{
                    //台形
                    if(abs(L + R) < 1e-8) S = 0.0;
                    else S = (L + R) / 2.0;
                }


                dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + S);
            }
        }
    }

    double ans = 1e18;
    for(int i = 0; i <= MAX_HIGHT; i++) ans = min(ans, dp[n][i]);
    printf("%.10f\n", ans);
    return 0;
}

E 問題: こたつがめを燃やさないで

ダイクストラ法でがんばる。
上下左右移動(1)
斜め移動(2)
爆弾がある場合(a)
爆弾がない場合(b)
の組み合わせの 4 通りの辺の張り方がある
実装は、グリッドをグラフに変換してから Dijkstra をしている

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007LL;
const int INF = MOD;
int di[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dj[8] = {1, 1, 0, -1, -1, -1, 0, 1};

vector<int> dijk(int s, int v, vector<vector<pair<int, int> > > adjlist){
    
    priority_queue <pair<int, int> > wait;
    vector<int> result(v, INF);

    //スタート地点を追加
    result[s] = 0;
    wait.push(make_pair(0, s));

    //ダイクストラ本体
    while(!wait.empty()){    //waitが空になるまで

        int nowpoint = wait.top().second;
        int nowcost = -wait.top().first;
        wait.pop();

        if(result[nowpoint] < nowcost) continue;

        //今いる頂点と隣接しているすべての頂点をなめる
        for(int i = 0; i < adjlist[nowpoint].size(); i++){

            int nextpoint = adjlist[nowpoint][i].second;
            int nextcost = nowcost + adjlist[nowpoint][i].first;
            //現時点より安く到達できそうであれば、結果を更新して優先度付きキューに格納
            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push(make_pair(-nextcost, nextpoint));
            }
        }
    }
    
    return result;         //結果列を返す
}


signed main(){
    
    int h, w, a, b; cin >> h >> w >> a >> b;
    vector<vector<char> > G(h + 2, vector<char> (w + 2, 'x'));
    
    int si, sj, gi, gj;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> G[i][j];
            if(G[i][j] == 's'){
                si = i;
                sj = j;
                G[i][j] = '.';
            }

            if(G[i][j] == 'g'){
                gi = i;
                gj = j;
                G[i][j] = '.';
            }
        }
    }

    int GridtoGraph[1010][1010];
    int num = 0;
    for(int i = 0; i <= h + 1; i++){
        for(int j = 0; j <= w + 1; j++){
            GridtoGraph[i][j] = num;
            num++;
        }
    }

    //first := コスト　second := 行先   
    vector<vector<pair<int, int> > > adjlist(num); 
    int s = GridtoGraph[si][sj];   
    int g = GridtoGraph[gi][gj];
    
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            int cur = GridtoGraph[i][j];
            
            bool isExist = false;   //爆弾が周りにあるか
            if(G[i][j] == '*') isExist = true;
            for(int h = 0; h < 8; h++){
                int ni = i + di[h];
                int nj = j + dj[h];
                if(G[ni][nj] == '*') isExist = true;
            }

            for(int h = 0; h < 8; h++){
                int ni = i + di[h];
                int nj = j + dj[h];
                if(G[ni][nj] == 'x') continue;

                //この時点で '.' '*' '#' の三通り
                int nxt = GridtoGraph[ni][nj];
                if(h % 2 == 0){
                    //上下左右の移動
                    if(G[ni][nj] == '#'){
                        if(isExist) continue;
                        adjlist[cur].push_back({a + b, nxt});
                    }else{
                        adjlist[cur].push_back({a, nxt});                        
                    }

                }else{
                    //斜め移動
                    int subi1 = i + di[h - 1];
                    int subj1 = j + dj[h - 1];
                    int subi2 = i + di[(h + 1) % 8];
                    int subj2 = j + dj[(h + 1) % 8];                    
                    
                    if(G[ni][nj] == '#' || G[subi1][subj1] == '#' || G[subi2][subj2] == '#'){
                        if(isExist) continue;
                        adjlist[cur].push_back({2 * a + b, nxt});                        
                    }else{
                        adjlist[cur].push_back({2 * a, nxt});
                    }
                }
            }
        }
    }

    vector<int> result(num);
    result = dijk(s, num, adjlist);
    int ans = result[g];
    if(ans == INF) cout << "INF" << endl;
    else cout << ans << endl;
    return 0;
}

楽しかったです。会津大学さん、ありがとうございました。

2019-02-06

AtCoder 青になるために必要だと思う知識

内容はこじんの見解であり、(略)

レーティング推移グラフを見る限り、青になるまでに時間がかかっております。

僕は AtCoder を始めた当初から、目標は青になることでした。

そんな僕が、個人的に AtCoder 青になるために最低限必要な知識を上げてみます。

レートが上がる要因は地頭と知識で 5:5 だと思っております。以下に挙げるのはあくまで必要な知識です。また、アルゴリズムの細かい解説は Google 先生に任せます

- imos 累積和

- DFS BFS

- 二分探索尺取り法

- 貪欲法

- DP

imos 累積和

区間を扱う問題で威力を発揮します。

累積和は 2 次元のものも知っていたほうがいいです。

DFS BFS

グリッドに対する探索や、グラフ上の探索、など様々なパターンが考えられますが、

全探索は全てのアルゴリズムの基本だと思います。

グラフに限らず、以下のような問題対して全探索の気持ちになれるといい感じだと思います。

C - 755

二分探索　尺取り法

概念から実装まで、しっかり理解することが大事だと思います。

高得点の問題でも要求される考え方のように思います。

貪欲法

難しいです。

貪欲に何かをすることの最適性をプチ証明する練習をするといいかもしれません。

DP

これが一番大事といっても過言ではありません。状態の遷移を考えることがキモだと思います。ここで、DP の次元は本質ではないです

まとめ

青になるために最低限必要な知識をまとめてみました

思ったより少ないですね！

これはなに

焼きスープカレー専門店 Curry Ya ASAP

スパゲティAndare

海味 はちきょう 本店

えびそば一幻 総本店

夜空のジンギスカン 本店

いかがでしたか？

背景

成果物

やったこと

感想

きっかけ

Library Checker

やったこと

作った問題

はじめに

A 問題「2 倍チェック / Is It a Number?」

問題概要

制約

解説

B 問題「増減管理 / Up and Down」

問題概要

制約

解説

C 問題「3 番目 / The Third」

問題概要

解説

D 問題「重複検査 / Duplicated?」

問題概要

制約

解説

最後に

A問題: 情報検索

B 問題: 括弧を語る数

C 問題: 約数ゲーム

D問題 矢

問題F: 赤黒そーるじぇむ

A問題: Lunch

B 問題: Milk

C 問題: Phone Number

D 問題: Tunnel

E 問題: こたつがめを燃やさないで

内容はこじんの見解であり、(略)

imos 累積和

DFS BFS

二分探索 尺取り法

貪欲法

DP

まとめ

海味はちきょう本店

えびそば一幻総本店

夜空のジンギスカン本店

D問題矢

二分探索　尺取り法