以下の問題の解説を理解するための知識をまとめてみました。 atcoder.jp 繰り返し二乗法 繰り返し二乗法とは、x1, x2, x4, x8, x16, ... を組み合わせて、xnを高速で計算するアルゴリズムです。 x1, x2, x4, x8, x16 は、二乗していけば、簡単に求めていくこ…

atcoder.jp DPをしつつ、セグメント木で高速化する。 普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。 dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。 セグメント木の更新は、dp[i]の値を一通り一気…

atcoder.jp 2、3回解いているが、なかなか覚えられないのでメモ。 マンハッタン距離が出たら、ひとまず45度回転を考えるのは覚えていた。 45度回転の方法は (X, Y) = (x-y, x+y) を計算すること。 45度回転すると、距離の領域が正方形になり、処理がしやすく…

atcoder.jp ソートして、最小値と最大値に対して、操作を繰り返せば良いかなと思ったが、うまくいかずにTLE。 答えに上限があることは分かったが、２分探索する発想はできなかった。 典型問題の「答えで２分探索する」は思いつきたかった。 そのあとの判定問…

atcoder.jp 末尾がT[i]個の0になっている整数を作っていけば良いことは分かったが、作り方の方針が誤っていた。 「2T[i] で割り切れて、2T[i]+1で割り切れない整数」と言い換えられるところは典型っぽい考え方か？ 上記の条件に加えて、「A[i-1]より大きい整…

atcoder.jp 浮動小数点の理解があまかったせいでACできなかった。 100倍して計算結果を100で割るところまでは思いついたが、キャストの部分でも誤差が出ることを理解していなかった。 例えば 0.79の場合、２進数で表すと 0 .1100101000111101011100001010001…

atcoder.jp 1の位の周期性を考える。 BCは繰り返し二乗法で求めて、周期の長さで割れば良い。 周期の中でどの位置にあるのかを求めるのが少し苦戦してしまった。 例えば、3 の周期は「3 9 7 1」の長さ4であり、39 の場合は周期により、1となる。単純に 9 % 3…

atcoder.jp 茶diffらしいが、実感としては緑diffくらいに感じる。 値の範囲にマイナスが含まれているので、場合分けや反転させる処理が思いつけなかった。 値の範囲が正のみ(D>0 && A,X > 0)であれば、特に難しいことはない。 負の場合(D<0)、反転するには、…

atcoder.jp 結構雰囲気で解いてしまった。 まずceil(AiM/N)でBiをざっくり求める。 Biの合計値を算出したら、Mと差分が出るので、max(BiN - AiM)が最小になるように、Biの値を減らしていく。 max(BiN - Ai*M) が大きい順に減らしていきたいので、PriorityQue…

atcoder.jp 表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0 dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1 dp[N][S]が1であればYes、そうでないならNo。 ま…

atcoder.jp UnionFindだろうと思ったが、ACLの使い方の理解が浅かったので、BFSで解いてしまった。 void solve(long long N, long long M, std::vector<long long> u, std::vector<long long> v){ vvl G(N+9); REP(i, M) { G[u[i]].push_back(v[i]); G[v[i]].push_back(v[i]); } vb</long></long>…

atcoder.jp 再帰的なDFS。 パッと書けるようにしたい。 void dfs(string S, ll n) { if (n==0) { cout << S << endl; return; } REP(i, 3) { S.push_back('a'+i); dfs(S, n-1); S.pop_back(); } } void solve(long long N){ dfs("", N); }

はじめに ソフトウェア開発では、問題を解決することが最も重要な目的です。しかし、実際の開発プロセスでは、技術的な課題やプログラミング言語の複雑さによって、手段が目的化してしまうことがあります。以前、私は「イシュードリブンでソフトウェアを作る…

1. ChatGPTでのブログ記事作成の驚くべき簡単さ 先日、ChatGPTを使ってブログ記事を書いてみたところ、驚くほど簡単に記事が作成できてしまった。これには正直、驚かされた。 2. ブログの目的とChatGPTの活用方法 ブログの目的によっては、ChatGPTの活用方法…

1. AIの進化とエンジニアの役割 ChatGPTの進化により、さまざまなタスクがAIに置き換わっている。これを受けて、エンジニアとして新たな役割と成長が求められる時代が到来している。 2. 重要なスキルと視点 問題解決や仕事がAIに置き換わる中、どのような問…

概要 技術的なインプットは本で行い、その他のインプットは動画や音声で行う、といった使い分けをしています。各種の動画・音声サービスで、自分がどのような情報をインプットしているのかを書き出してみました。 YouTube www.youtube.com なんだかんだでYou…

はじめに プログラマの仕事は、端的に言うと問題を解決するソフトウェアを作ることです。 ソフトウェアを作るために、さまざまなプログラミング言語やオブジェクト指向やDDDやアジャイルなどの手法があります。こういった実装技術はとても奥が深く、勉強して…

ブロックとキャラの当たり判定アルゴリズムについて考えています。 当たり判定の考え方としては、 「キャラ(自機)の中心の座標が、ブロックの中心から角をつないだ線よりも左側にあるか右側にあるか」を判定する形になります。 「ある点がある線よりも左側に…

現場で役立つシステム設計の原則 ~変更を楽で安全にするオブジェクト指向の実践技法作者: 増田亨出版社/メーカー: 技術評論社発売日: 2017/07/05メディア: 単行本（ソフトカバー）この商品を含むブログ (1件) を見る 分析や設計について勉強したいと思い、読…

デジタルアートに関することが学びたくて読みました。 デザインとプログラミング 2018 yoppa.org ブラウザ上で動作を確認しながら読み進めました。 editor.p5js.org 以下のことが一通り学べます。 Processingの基礎 画像データから絵を書く サウンドデータか…

概要 タイトルのとおりです。そうでなければ、CloudFormationは以下の実行エラーを出します。 The new key policy will not allow you to update the key policy in the future (新しいキーポリシーは将来のキーポリシーの更新を許可していません) aws.amazo…

ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装作者: 斎藤康毅出版社/メーカー: オライリージャパン発売日: 2016/09/24メディア: 単行本（ソフトカバー）この商品を含むブログ (18件) を見る 2章 パーセプトロン パーセプトロンは…

パーセプトロン とは、ニューラルネットワーク (ディープラーニング) の期限となるアルゴリズムです。複数の信号を入力として受け取り、ひとつの信号を出力します。 以下はパーセプトロンを数式で表したものです。 x, y は入力値 は 重み は閾値 bはバイアス…

概要 以下のような形式のCSVファイルを想定しています。 User name,Password,Access key ID,Secret access key,Console login link {user_name},{password},{access_key},{secret_access_key},https://{account_name}.signin.aws.amazon.com/console スクリ…

概要 いくつかのAWSアカウント内で、クロスアカウント用のロールを作成する必要があったので、スクリプトを作成しました。 以下、作成したスクリプト。 PROFILE= ROLE_NAME= ACCOUNT_ID= Principal=$(cat<< EOS { "Version": "2012-10-17", "Statement": { "…

概要 ブルーグリーンデプロイメントのAWSホワイトペーパー https://d1.awsstatic.com/whitepapers/AWS_Blue_Green_Deployments.pdf AWSのサービスやツールを使った Blue/Green デプロイメントを実装する方法が学べます。 以下、読書メモです。 Blue/green de…

概要 Overview of Deployment Options on AWS https://d1.awsstatic.com/whitepapers/overview-of-deployment-options-on-aws.pdf AWSへのプロビジョニングやデプロイの方法が紹介されている資料です。 以下のようなことを知ることができます。 デプロイに関…

概要 employment.en-japan.com こちらの記事を読みました。普段使っているDockerが、内部でどのようなことを行っているのかを、少しイメージできるようになりました。 感想 コンテナ の説明は、仮想マシン と比較して、以下のように説明されることが多いと思…

結論 最初に結論を。 週に1回、パーソナルトレーニングで筋トレする 毎日、アブローラーを使って筋トレする 毎日、BCAAを飲んで1時間の有酸素運動をする 毎日、炭水化物(糖質)を減らし、プロテインを3回飲む 毎日、自撮りをする 本やサイトで筋トレのことを…

結論 この記事では、以下の結論となっています。 DynamoDBLocal が LocalStack の DynamoDB よりパフォーマンスが良い 自動テストでは、DynamoDBLocal を使うほうが良い 概要 手元のPCで動く開発用 DynamoDB は以下の2つがあります。 LocalStack · GitHub Dy…