問題 D - Logical Expression 解法 DPを使った解法。入力例1で考えてみる。 2 AND OR 以下のDP配列を定義する。 dp[n][x]:= n個までの文字列で結果がx(0/1)になるケースの数 n = 0 true / false それぞれ1通りのみ dp[0][0] = 1 dp[0][1] = 1 n = 1 AND(積集…

問題 D - equeue 解法 操作A-D(問題文より) 操作 A: D に詰められた宝石のうち、左端の宝石を取り出して手に入れる。 操作 B: D に詰められた宝石のうち、右端の宝石を取り出して手に入れる。 操作 C: 持っている宝石を 1 つ選んで D の左端に詰める。 操作 …

Amazon検索URLの末尾に &emi=AN1VRQENFRJN5 を追加することでAmazon以外の販売会社の商品が表示されなくなる(マーケットプレイス出品が非表示になる)と聞いた。実際に試してみた。 イヤホンの検索結果(通常) イヤホンでの検索結果URLに&emi=AN1VRQENFRJN5を…

問題 E - Peddler N個の町がある。 町を結ぶM本の道がある。 それぞれの道は $ X_i $ から $ Y_i $ への一方通行になっている。 $ 町_i $ では $ A_i $ 円の金(gold)を買ったり売ったりできる。 ある町で金を買い、いくつかの道を使った後、買った町とは別の…

問題 D - Decayed Bridges 解法 ぱっと見でUnionFindだろうなと思ったが、少々工夫が必要だった。 橋の削除操作は難しいため、逆順から橋を追加していく操作を考える 橋が一つもない状態の不便さは $ {}_n C_2 $ で求まる 橋を追加後の不便さは、次で求まる …

問題 D - AtCoder Express 2 解法 列車の区間L-Rを二次元座標として考える。 Q個のクエリを求める必要があるが、都度計算すると間に合わない。 二次元累積和を使って前計算しておくことで、Q個のクエリに対して高速に答えを出す。 #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

問題 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…

問題 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>…

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

問題 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>

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

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

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

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

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

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

問題 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>…

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

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

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…

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

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

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

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

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

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

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

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

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

以下の挙動をする 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))) 与えられた全ての関数をスプレッド演算子...を…