atcoder abc183 E - Queen on Grid

問題 E - Queen on Grid 解法 DP + 累積和。 dp配列は、 dp[i][j] = {i,j}地点に到達できる場合の数 で考える。 するとdp[i][j] は以下のように3方向のdpの累積を足すと求められる。 dp[i][j] = dp[i][j-1] + dp[i][j-2] ... + dp[i][0] + dp[i-1][j] + dp[i…

atcoder ABC 104 D - We Love ABC

問題 D - We Love ABC 解法 ? があると複雑なため、まずは ? 抜きで考えてみる。 素朴に3重ループでA->B->Cとなるパターンを総当りしてみる。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) using ll = long long; int main() { string s; cin >> s; int n = s.size(); ll ans = 0; REP(i,n) {</n;i++)></bits/stdc++.h>…

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities

問題 E - Traveling Salesman among Aerial Cities 解法 巡回セールスマン問題。 ナイーブな全探索では $O(N{!})$ かかるため、 $ n=17 $ では時間切れになる。 そこでbitDPと呼ばれる手法を使う。 bitDPでは計算量が $ O(N{^2}2{^n})$ となるため今回の制約…

HHKB プログラミングコンテスト 2020 D - Squares

問題 D - Squares 解法 解説: Editorial - HHKB Programming Contest 2020 上記解説手順で解いてみる #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) typedef long long ll; const int mod = 1000000007; // mintは省略 https://github.com/atcoder/ac-library int main() { int t; cin >> t; REP(i,t) {…</n;i++)></bits/stdc++.h>

atcoder ABC 100 D - Patisserie ABC

問題 D - Patisserie ABC 解法 公式解説が詳しいのでそこに書いてある通り。 https://img.atcoder.jp/abc100/editorial.pdf $ x,y,z $ の3要素の正方向と負方向の組み合わせは $ 2 ^ 3 $ 通り。 それぞれの組み合わせで $ x,y,z $ の合計が大きいものから $ …

atcoder ABC 099 D - Good Grid

問題 D - Good Grid 解法 $ (i+j) \% 3 $ なので条件を満たすために使う色は3色のみ 事前に $ (i+j) \% 3 $ を3パターンに塗ったときのそれぞれのコストを計算しておく 全ての色の組み合わせについて調べる(全探索)。$O(N{^3})$ となるが $ C=30 $ の制約に…

atcoder ABC 098 D - Xor Sum 2

問題 D - Xor Sum 2 解法 全探索すると $O(N{^2})$となり間に合わないため、計算量を減らす工夫が必要になる。 この問題は単調増加する区間の数え上げなので、尺取り法の要領で解くことができる。 #include <bits/stdc++.h> using namespace std; using ll = long long; #de</bits/stdc++.h>…

atcoder ABC 087 D - Grid Components

問題 D - Grid Components 解法 $ h, w $ は 100以下という条件なので、$ h = 100, w = 100 $ で固定して考える $ 1 \leq A \leq 500, 1 \leq B \leq 500 $ の制約であれば、100x100 の 半分 50x50 の領域に500個の連結成分を作ることは可能 上記を前提とし…

atcoder ABC 087 D - People on a Line

問題 D - People on a Line 解法 以下の有向グラフを作り、DFSで頂点間の距離に矛盾が生じていないかを調べる。 $ L_i $ から $ R_i $ まで距離 $ D_i $ $ R_i $ から $ L_i $ まで距離 $ -D_i $ ただし、M個の入力から得られるグラフは連結していない場合が…

リキッドレイアウトの特定行へ差し込み要素を入れる

リキッドレイアウトで並べられたアイテムの特定行に差し込み要素を入れたい。 イメージ: 赤枠がアイテム、青枠が差込要素 リキッドレイアウトでは横幅によって1行に並ぶアイテム数が可変となる。 表示するウィンドウの横幅によっては1行3個の場合もあれば、1…

atcoder ABC 179 D - Leaping Tak

問題 D - Leaping Tak 解法 素直にDPで解けそうだが、愚直にnに対して全ての移動を試すと $ O(N{^2}) $ となり $ 2≤N≤2×10{^5} $ の制約下でTLEしてしまう。 // このコードはTLEする #include <bits/stdc++.h> using namespace std; #define COUT(x) cout<<(x)<<"\n" #defin</bits/stdc++.h>…

atcoder ABC 178 C - Ubiquity

問題 C - Ubiquity 公式解説にある通り、包除原理を理解していれば数行で解ける問題。 包除原理にたどり着けず納得が行かなかったので公式解説動画で言及されていたDP解法で解いてみた。 DP解法 DPは [N][0を含んでいるかどうか][9を含んでいるかどうか] で…

GitFlowでmasterブランチにマージしたあとのrevert作業メモ

想定ケース GitFlowによるdevelop/masterブランチ運用。 develop, master ブランチは保護ブランチ。基本的にはGitHub上でのPRベースでマージを行う。 feature ブランチで作業 例として newfile.txt というテストファイルを追加する作業を行う $ git checkout…

Error retrieving access token: TypeError: Cannot read property 'expiry_date' of undefined [clasp]

I encountered an error when I use clasp command as below. $ yarn clasp create clasp-project --rootDir ./src yarn run v1.7.0 Error retrieving access token: TypeError: Cannot read property 'expiry_date' of undefined error Command failed with…

GitHubのissueに特定のラベルが貼られたらSlackに投稿するBOTを作る

GAS

特定のリポジトリで、特定のラベルが貼られたらそれを検知してSlackに投稿するBOTをGASで書いた。 github.com こんな感じにissueに特定のラベルが貼られたら通知を送る やりたかったこと リポジトリを跨ったアプリケーション構成の場合、Aリポジトリの変更が…

web componentsについて

web componentsとは何か Webコンポーネントは、カスタム/再利用可能でカプセル化されたHTMLタグを作成できるWebプラットフォームAPIのセットである。 以下、4つの主要な仕様を持つ。 Custom Elements Custom Elements Custom Elementsは、DOM要素を独自に構…

Nuxt.jsにstylelintを導入する

インストールするモジュール stylelint stylelint.io standard ルールセット github.com .vueファイル内の<style></style>をパースするために導入する github.com インストール $ yarn add -D stylelint stylelint-config-standard @mapbox/stylelint-processor-arbitrary-t…

Nuxt(Vuex)でAtomic Designを採用するときのメモ

数ヶ月Atomic Designを採用したNuxt(Vuexパターン)アプリケーション開発を行ってみて、思ったことのメモ。 Atomic Designとは bradfrost.com 概要だけ知りたい人に説明すると、基底となるコンポーネント(原子)を作り、その原子を組み合わせて分子コンポーネ…

サーバサイドレンダリング(SSR)について [Nuxt.js]

サーバサイドレンダリング (SSR) とは何か? Vue SSR ガイド | Vue.js サーバサイドレンダリングガイド 通常では、Vue コンポーネントはブラウザで DOM を生成し操作がされます。しかし、同じ Vue コンポーネントをサーバ上の HTML 文字列に描画し、ブラウザ…

計算量(O記法)について [30seconds of interviews]

O記法は、コンピュータサイエンスにおいてアルゴリズムの複雑さを表すために使用される。 優秀なアルゴリズムは高速に結果を返し、かつ複雑度は低いと言える。 アルゴリズムは常に同じ結果にはならず、与えられるデータによって異なる結果になる場合がある。…

仮想DOMはなぜライブラリ/FWに使われるのか [30seconds of interviews]

仮想DOMとは 仮想DOM(virtual DOM)は、DOMをJavaScriptオブジェクトの形式で表現したもの。 これらのオブジェクトには、ノード名/属性/子ノードなど、実際に表示されるDOMノードを記述するプロパティがある。 <div class="counter"> <h1>0</h1> <button>-</button> <button>+</button> </div> 上記マークアップの仮想DOMは、次のよう…

JavaScript 0.1 + 0.2 === 0.3 はなぜfalseと評価されるのか [30seconds of interviews]

0.1 + 0.2 === 0.3 // false 一見trueになるように見えるが結果はfalseになる。 これはJavaScriptがIEEE 754*1を採用し、64ビット浮動小数点数を使用するためである。 要するに、コンピュータは2進数ベースで動いているため10進数の少数を計算する場合、正し…

JavaScriptの純粋関数とは何か?[30seconds of interviews]

純粋関数とは何か? 純粋関数(pure function)とは、これら2つの条件を満たす関数を指す。 同じ入力が与えられると、その関数は同じ出力を返す。 関数は、その関数のスコープにおいて副作用を起こさない。 純粋関数は、上記の2つの条件を満たす限り、関数内…

JavaScriptでパイプ関数を作成する [30seconds of interviews]

以下の挙動をする pipe関数を作成する const square = v => v * v const double = v => v * 2 const addOne = v => v + 1 const res = pipe(square, double, addOne) res(3) // 19; addOne(double(square(3))) 与えられた全ての関数をスプレッド演算子...を…

Javascriptオブジェクトをクローンする [30seconds of interviews]

How do you clone an object in JavaScript? スプレッド構文...を使うと、オブジェクト自身の列挙可能なプロパティを新しいオブジェクトにコピーできる。オブジェクトの浅いクローン(shallow clone)が作成される。 const obj = { a: 1, b: 2 } const shallow…

CSS BEMとは何か? [30seconds of interviews]

CSS

What is CSS BEM? BEMとは、スコープ問題を解決するために名前空間を定義することでよりCSSをメンテナンスしやすくするCSSクラスの命名規則。 BEMはblock, element, modifier の略。blockはプロジェクトを通して再利用可能なスタンドアロンなコンポーネント…

HTML5 Web Storage(ローカルストレージ/セッションストレージ)とは何か [30seconds of interviews]

HTML5 Web Storageとは何か HTML5では、ウェブサイトはブラウザのローカルにデータを保存できる。データはname-valueペアで格納され、ウェブページは自身で格納したデータにのみアクセスができる。 localStorageとsessionStorage ライフタイムの違い localSt…

scriptタグのdefer/async属性の違い [30seconds of interviews]

30secondsofinterviews.org 30 seconds of interviewsを一通り読んで面白かったので紹介していきたい What are defer and async attributes on a <script> tag? <script src="myscript.js"></script> <script src="myscript.js" defer></script> <script src="myscript.js" async></script> いずれの属性も指定しない場合、スクリプトは同期的にダウンロード・実行…

Vue.js 基底inputコンポーネントを作る

inputの基底コンポーネントを作る。 親コンポーネントから初期値を受け取りたい 親コンポーネントに入力を動的に伝えたい v-modelは使わずに、@inputでそのまま親に変更されたvalueをemitする。 # input基底コンポーネント Vue.component('baseInput', { pro…

Vue.js inheritAttrsの挙動を調べる

https://vuejs.org/v2/api/#inheritAttrs v2.4から inheritAttrsが使えるようになった。 By setting inheritAttrs to false, this default behavior can be disabled. The attributes are available via the $attrs instance property (also new in 2.4) and…