Image Uploaderに着手する

概要

Qiitaで見つけたこの記事が気になった。
フルスタックエンジニアになるためのモダンな8つのプロジェクト - Qiita

とりあえず最初のImage Uploaderをやってみる。

Image Uploader

Image Uploaderの概要はこちらのリンクにある。

このページにある内容を日本語訳してみる。

Challenge: 画像アップローダーアプリケーションを作成します。
任意のフロントエンドライブラリを使用します。
APIを作成します。
既存のソリューションを見ないでください。
以下のユーザーストーリーを満たす。

とあるので、以下にあるユーザーストーリーを機能として実現できるImage Uploaderを作成する。

  • 画像をドラッグ&ドロップでアップロードできる。
  • フォルダから画像を選択できる。
  • アップロード時にローダーが表示される。
  • 画像をアップロードすると、画像を見てコピーできる。
  • クリップボードへのコピーを選択できる。

アイコンはGoogle Material Design Iconsを使っているようだ。

アイコン: https://google.github.io/material-design-icons/

その他の詳細は以下。

すべてのユーザーストーリーを満たす限り、トランジションを追加したり、独自の画像を使用したり、色を変更したり、独自のレイアウトを作成したりして、自分だけのタッチを与えることができます。
他の人があなたのソリューションを提出するのを防ぐために、フッターにあなたの名前を置くことを忘れないでください。 完了したら、GitHubリポジトリとライブアプリの両方のURLを提供して、任意のホスティングプラットフォーム(5つの無料ホスティングプラットフォーム)上でソリューションを提出し、何をしたかを簡単に説明します。他の人のソリューションをチェックして、フィードバックを与えることができます。
あなたのソリューションを #devchallenges で他の人と共有し、Twitter で @devchallengesio をタグ付けしてください。

Go何も分からんのでとりあえずBeegoでサーバ立てた

経緯

  • Goで何か作りたい
  • 何作ろう
  • 業務でバックエンドのモックを作ってるからWebサーバ立てられるようにしたい

Beegoって何

GoのWebフレームワークの一つ。
選定候補としては他にGinRevelEchoなどが挙げられる。
このBeegoは初心者向けらしい。

以下、GoのWebフレームワーク比較に関する参考資料

まずはインストールから

コンソールに何も表示されないと不安になるので-vオプションをつけている。

go get -u -v github.com/astaxie/beego

蛇足

何故かbeeのインストールでつまづく。 beeはBeegoベースの開発を進めるためのCLIツール。

go get -u -v github.com/beego/bee

上記コマンドを実行すると以下のメッセージが出る。解決方法は現在不明。

# github.com/gadelkareem/delve/service/rpccommon
go/1.15.0/src/github.com/gadelkareem/delve/service/rpccommon/server.go:83:3: cannot use logger (type *"github.com/go-delve/delve/vendor/github.com/sirupsen/logrus".Entry) as type *"github.com/gadelkareem/delve/vendor/github.com/sirupsen/logrus".Entry in field value

まあとりあえずbeegoの方はインストールできたので先に進んでみる。

BeegoのGet Started

全体のソースコード
これをgo run main.goで実行する。
その結果ブラウザでhttp://127.0.0.1:8080にアクセスするとhello worldのメッセージが表示される。

package main

// 各パッケージのinit()を実行
import "github.com/astaxie/beego"

// controllerの実装
// MainControllerはbeego.Controllerが持つメソッドを全て実行できる
type MainController struct {
  beego.Controller
}

// 上述のMainControllerが持つRESTfulメソッドを定義する
func (this *MainController) Get() {
  this.Ctx.WriteString("hello world")
}

func main() {
  // パスとcontrollerを関連づける
  beego.Router("/", &MainController{})
  // 実行する
  beego.Run()
}

Google Chrome Platfromと向き合いたい

あらすじ

業務でGCPでシステムを構築することになった。

ただ問題が。

GCP経験がない。

ということでGCPの勉強します。

GCPってなんだ

正式名称をGoogle Cloud Platformという。その名の通りGoogleが提供するクラウドサービスのプラットフォーム。 Amazonが提供するAmazon Web Serviceが競合ということでいいんだろうか。

GCPにおけるプロジェクト

GCPを始めるときに混乱するのがプロジェクトという概念。
何故混乱するかというと、例えばよくあるアーキテクチャは1つのプロジェクトというまとまりの中に複数の機能を開発する。

ところが、GCPにおけるプロジェクトとは、一つのアーキテクチャの中に「1つの機能 = 1つのプロジェクト」として複数のプロジェクトが存在しうる。

f:id:koralle_ac:20200713211426j:plain

このプロジェクトは例えば「開発用(Development)」「ステージング用(Staging)」「本番用(Release)」として切り分けることもできる。 こういう仕様のため、例えば1つのプロジェクト内に複数のApp Engineコンテナが作れないみたいなことがあったりする。

まずはこのプロジェクトという概念に慣れたい。

AtCoder Beginner Contest 171 A - E

はじめに

大会中はAB瞬殺CがわからんDが1REでパフォーマンスは544。
Cを見た瞬間に切り捨ててDに走っておけばパフォはもっと高かった気がする。

A - alphabet

今見たら訳わからない解き方してる。

if ('a' <= c && c <= 'z') cout << 'a' << endl;
else cout << 'A' << endl;

でいいよね...。

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

using ll = long long;
#define rep(n, i) for(ll i = 0; i < n; ++i)

void solve(void){
  char c; cin >> c;
  if (c - 'A' >= 26) cout << 'a' << endl;
  else cout << 'A' << endl;
}

int main(void) {
  solve();
  return 0;
}

B - Mix Juice

入力配列を昇順ソートして頭から貪欲にK回足すだけ。

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

using ll = long long;
#define rep(n, i) for(ll i = 0; i < n; ++i)

void solve(void){
  ll n, k; cin >> n >> k;
  vector<ll> p(n, 0);
  rep(n, i) cin >> p[i];

  sort(p.begin(), p.end());
  ll res = 0;
  rep(k, i) res += p[i];

  cout << res << endl;
}

int main(void) {
  solve();
  return 0;
}

C - One Quadrillion and One Dalmatians

これが解けなかった。原因はwhileループ内の先頭で--nしていなかったこと。

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

using ll = long long;
#define rep(n, i) for(ll i = 0; i < n; ++i)

const string al = "abcdefghijklmnopqrstuvwxyz";

void solve(void){
  ll n; cin >> n;

  string res = "";
  while(n > 0) {
    --n;
    res += al[n % 26];
    n /= 26;
  }

  reverse(res.begin(), res.end());
  cout << res << endl;
}

int main(void) {
  solve();
  return 0;
}

D - Replacing

最初似問題文を見たときはどう考えても計算量がO(NQ)にしかならない気がしていた。
よくよく問題文を読むと出力したいのは総和だけなので、各クエリによる総和の増減だけ意識すれば良さそうだった。

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

using ll = long long;
#define rep(n, i) for(ll i = 0; i < n; ++i)

void solve(void){
  ll n; cin >> n;
  vector<ll> a(n, 0);
  rep(n, i) cin >> a[i];
  ll q; cin >> q;
  vector<ll> b(q, 0);
  vector<ll> c(q, 0);
  rep(q, i) cin >> b[i] >> c[i];

  map<ll, ll> m;
  rep(n, i) ++m[a[i]];

  ll res = 0;
  rep(n, i) res += a[i];

  rep(q, i) {
    res += m[b[i]] * (c[i] - b[i]);
    cout << res << endl;

    ll t = m[b[i]];
    m[b[i]] -= t;
    m[c[i]] += t;
  }
}

int main(void) {
  solve();
  return 0;
}

E - Red Scarf

できれば解きたかった。でもxorの勉強全然してなかったし仕方がない。

使えそうなxorの性質だけググったりしてまとめた。

  • a ^ b = b ^ a (可換)
  • a ^ (b ^ c) = (a ^ b) ^ c(分配法則)
  • a ^ a = 0
  • a ^ a ^ b = b
  • a + b = a ^ b + 2 * (a & b)
  • (4*a) ^ (4*a+1) ^ (4*a+2) ^ (4*a+3) = 0
  • a ^ (a+1) = 1

とにかく、xorを考えるときは遇奇を意識することが重要。
この問題では、Nは全て偶数が結構重要だった。

i番目の猫の整数をbiとする。 a1 ^ a2 ^ ... ^ anの中には、b1, b2, ..., ^ bnがそれぞれ(N-1)回登場する。
Nが偶数だから(N-1)は必ず奇数となる。
このとき、(N-1)個のbiのxor和はbiになる。
だから、a1 ^ a2 ^ ... ^ an = b1 ^ b2 ^ ... ^ bnである。
aiはj = iの場合を除く全てのbjのxor和だから、s = a1 ^ a2 ^ ... ^ anとaiのxorを取ると、bi以外のbjが打ち消されてbiが取り出せる。

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

using ll = long long;
#define rep(n, i) for(ll i = 0; i < n; ++i)

void solve(void){
  ll n; cin >> n;
  vector<ll> a(n, 0);
  rep(n, i) cin >> a[i];

  ll res = a[0];
  for(ll i = 1; i < n; ++i) res ^= a[i];

  vector<ll> b(n, 0);
  rep(n, i) b[i] = (res ^ a[i]);

  rep(n, i) {
    cout << (res ^ a[i]);
    (i < n-1) ? cout << " " : cout << endl;
  }
}

int main(void) {
  solve();
  return 0;
}

AtCoder Beginner Contest 129 - C Typical Stairs

はじめに

動的計画法の経験値が欲しい。

アルゴリズムについて

i段目の階段の登り方の数え上げ方はフィボナッチ数列っぽくdp[i] = dp[i-1] + dp[i-2]でいけそう。
しかし、そもそもi段目も(i-1)段目も(i-2)段目も階段が壊れて上れない可能性がある。

数え上げ方を考えるに、初期条件はdp[0] = 1dp[1] = 1にする必要がある。
ただし、1段目の階段も壊れていればdp[1] = 0である。

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

const ll MOD = 1e9+7;

void solve(){
  ll n, m; cin >> n >> m;
  vector<bool> damaged(n+1, false);
  rep(m, i) {
    ll ta; cin >> ta;
    damaged[ta] = true;
  }

  vector<ll> dp(n+1, 0);
  dp[0] = 1;
  if (!damaged[1]) dp[1] = 1;

  for(ll i = 2; i <= n; ++i) {
    if (!damaged[i-1]) dp[i] += dp[i-1];
    if (!damaged[i-2]) dp[i] += dp[i-2];
    dp[i] %= MOD;
  }

  cout << dp[n] << endl;
}

int main() {
  solve();
  return 0;
}

参考

AtCoder ABC 129 C - Typical Stairs (300 点) - けんちょんの競プロ精進記録

Warshall-Floyd法で全点対最短路問題を考える

Warshall-Floyd法について

  • 全点対最短路問題(全ての2頂点間の最短距離を求める問題)が解ける。
  • 計算量はO(|V|^3)
  • DPで簡単に実装できる。

コードについて

この無向グラフの情報を入力して、各頂点までの最短距離を出力する。 入力は、1行目で(頂点数V, 辺の数E)を入力する。 2行目~E+1行目の入力は、E個の辺の情報(from, to, cost)を入力する。

入力例
入力例

出力は、Warshall-Floyd法によって計算した各2頂点間の最短距離とする。 同じ頂点間の距離は出力しない。

$./warshall_floyd
7 10
1 2 2
1 3 5
2 3 4
2 4 6
2 5 10
3 4 2
4 6 1
5 6 3
5 7 5
6 7 9

出力例

The distance from 1 to 2: 2
The distance from 1 to 3: 5
The distance from 1 to 4: 7
The distance from 1 to 5: 11
The distance from 1 to 6: 8
The distance from 1 to 7: 16
The distance from 2 to 1: 2
The distance from 2 to 3: 4
The distance from 2 to 4: 6
The distance from 2 to 5: 10
The distance from 2 to 6: 7
The distance from 2 to 7: 15
The distance from 3 to 1: 5
The distance from 3 to 2: 4
The distance from 3 to 4: 2
The distance from 3 to 5: 6
The distance from 3 to 6: 3
The distance from 3 to 7: 11
The distance from 4 to 1: 7
The distance from 4 to 2: 6
The distance from 4 to 3: 2
The distance from 4 to 5: 4
The distance from 4 to 6: 1
The distance from 4 to 7: 9
The distance from 5 to 1: 11
The distance from 5 to 2: 10
The distance from 5 to 3: 6
The distance from 5 to 4: 4
The distance from 5 to 6: 3
The distance from 5 to 7: 5
The distance from 6 to 1: 8
The distance from 6 to 2: 7
The distance from 6 to 3: 3
The distance from 6 to 4: 1
The distance from 6 to 5: 3
The distance from 6 to 7: 8
The distance from 7 to 1: 16
The distance from 7 to 2: 15
The distance from 7 to 3: 11
The distance from 7 to 4: 9
The distance from 7 to 5: 5
The distance from 7 to 6: 8

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pr = pair<ll, ll>;
using graph = vector<vector<pr>>;
#define rep(n, i) for(ll i = 0; i < n; ++i)

const ll INF = 1e18;

void warshall_floyd(const graph& g, vector<vector<ll>>& d) {
  ll n = (ll)g.size();
  rep(n, k) {
    rep(n, i) {
      rep(n, j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

void solve() {
  ll v, e; cin >> v >> e;
  graph g(v);
  vector<vector<ll>> dist(v, vector<ll>(v, INF));
  rep(e, i) {
    ll ta, tb, tc; cin >> ta >> tb >> tc;
    --ta, --tb;
    g[ta].emplace_back(make_pair(tc, tb));
    g[tb].emplace_back(make_pair(tc, ta));
    dist[ta][tb] = tc;
    dist[tb][ta] = tc;
  }
  rep(v, i) {
    rep(v, j) {
      if (i == j) dist[i][j] = 0;
    }
  }

  warshall_floyd(g, dist);
  rep(v, i) {
    rep(v, j) {
      if (i == j) continue;
      cout << "The distance from " << i+1 << " to " << j+1 << ": " << dist[i][j] << endl;
    }
  }
}

int main(void) {
  solve();
  return 0;
}

Dijkstraのアルゴリズム

はじめに

Dijkstraアルゴリズムについて

  • Bellman-Ford法と同様に、単一始点最短路問題を解くことができる。
  • Bellman-Ford法とは異なり、グラフの全ての辺の重みが非負でなければならない
  • その代わりに計算量はO(|E|*log|V|)と、Bellman-Ford法よりも高速になる。
  • C++で実装する際は、priority_queue(優先度付きキュー)を用いるとうまくいく。

コードについて

この無向グラフの情報を入力して、各頂点までの最短距離を出力する。 入力は、1行目で(頂点数V, 辺の数E)を入力する。 2行目~E+1行目の入力は、E個の辺の情報(from, to, cost)を入力する。

出力は、Bellman-Ford法によって計算した頂点1から各頂点までの最短距離とする。 便宜上、頂点1から頂点1までの最短距離を0として1行目で出力する。

入力例
入力例

$./bellman_ford
7 10
1 2 2
1 3 5
2 3 4
2 4 6
2 5 10
3 4 2
4 6 1
5 6 3
5 7 5
6 7 9

出力例

0
2
5
7
11
8
16

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pr = pair<ll, ll>;
using graph = vector<vector<pr>>;
#define rep(n, i) for(ll i = 0; i < n; ++i)

const ll INF = 1e18;

vector<ll> dijkstra(graph& g, ll start) {
  ll n = (ll)g.size();
  vector<ll> dist(n, INF);
  priority_queue<pr, vector<pr>, greater<pr> > que;
  dist[start] = 0;

  que.push(pr(0, start));

  while(!que.empty()) {
    auto p = que.top(); que.pop();
    auto pf = p.first;
    auto ps = p.second;

    if (dist[ps] < pf) continue;

    for (auto node : g[ps]) {
      auto nf = node.first;
      auto ns = node.second;
      if(dist[ps] + nf < dist[ns]) {
        dist[ns] = dist[ps] + nf;
        que.push(pr(dist[ns], ns));
      }
    }
  }
  return dist;
}

void solve() {
  ll v, e; cin >> v >> e;
  graph g(v);
  rep(e, i) {
    ll ta, tb, tc; cin >> ta >> tb >> tc;
    --ta, --tb;
    g[ta].emplace_back(make_pair(tc, tb));
    g[tb].emplace_back(make_pair(tc, ta));

  }

  vector<ll> result = dijkstra(g, 0);
  rep(v, i) {
    cout << result[i] << endl;
  }
}

int main(void) {
  solve();
  return 0;
}