以下の問題の解説を理解するための知識をまとめてみました。 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に置き換わる中、どのような問…