あまり広まっておらず知る人ぞ知るテクみたいになってる気がしたので。 グリッド上でBFSをするときに、単純に書くとこのような感じになると思います。 bool bfs(const vector<vector<int>>& grid, int r, int c) { vector<pair<int, int>> queue = { {r, c} }; vector<vector<bool>> visited(H, vector<bool>(W)); visited[r][c] = true; int qi = 0; while (qi < queue.size()) { auto [cr, cc] = queue[qi]; for (int i = 0; i < 4; ++i) { int nr = cr + DR[i]; int nc = cc + DC[i]; if (nr < 0 || H

背景 システムの概要 CDKやその他のコード テスト実行結果 コスト 他のアイデア Lambdaのメモリに関する実験など LambdaのメモリとCPUに関する仕様 Lambdaに割り当てるメモリ量を変えながら実験 不満ポイント ※この記事は包括的な解説というよりは、同じようなことをやろうとした人へのインプットになればいいかなと思っています。C++のソースコード用に書きましたが、少し手を入れれば他の言語でも使えると思います。 AWSを触ったことがない人向けには書いていないです。すいません... <7/23追記> Lambdaのメモリと処理能力について理解があやふやだったので検証した記録を残しました。メモリは1.8GBくらいにするのが良さそうです。 <8/20追記> 実際にコンテストで使ってみたところ、この構成だと不満が多かったです。それに関するレポートを書きました。 <11/7追記> 実際に

この記事は「でぶ Advent Calendar 2022」向けのジョーク記事です。普段は硬派なマラソンブログをやっています。 adventar.org 初めに DebuScript— shojin_debu (@shojin_pro) 2022年11月18日 shojinさんがDebuScriptという言語を欲していたので作りました。 DebuScriptについて 基本的にはBrainfxxkの各文字をshojinさんが使いやすいようになじみのある単語に置き換えました。 DebuScript(Brainfxxk)の仕様について Brainfxxkは多くの人がわかりやすい解説を書いているので、詳細は割愛します。 詳しく勉強したい方はきちんと書かれた記事を参照していただければと思います。 大雑把な理解としては以下のような感じです: 1byteの値(0~255)が入る配列(memory)があり

0.はじめに 1.前職と求人に応募するまでの話 2.オンラインでの1次面談 3.大学の就職活動と新卒で入社したときの話 4.オンラインでの2次面談 5.対面での最終面談 6.終わりに 7.おまけ：入社後の競技プログラミング参加について 0.はじめに はじめまして、もしくはお久しぶりです、競プロ歴3年のかえでです。46歳で競技プログラミングを始め、今の年齢は49歳になります。 そんな私が、本日2023年2月1日、AtCoder株式会社に入社しました。 atcoder.jp いったい何が起こったのかと驚かれた方も多いのではないかと思います。私自身もこの事実を人から聞いたとしたら、「え、どういうこと？」と思ったことでしょう。だから、書ける範囲で入社までの経緯を書きたいと思います。（事前にchokudaiさん*1とけんしょーさん*2には読んでいただいて許可をもらっています。） 1.前職と求人に応募

考察をショートカットしたいので書きました。負の数が絡むと頭が壊れがち。 見つけ次第追加していこうと思います。 定義 床関数 $ x $ が有理数のとき 天井関数 $ x $ が有理数のとき 不等式評価 床関数 天井関数 切り捨て除算を使った実装 オーバーフローを避けて $ab$ と $c$ を比較する 平方分割 $ \left\lfloor \frac{n}{ab} \right\rfloor = \left\lfloor \left\lfloor \frac{n}{a} \right\rfloor / b \right\rfloor $ Sum of Floor of Linear 定義 床関数 $ x \in \mathbb{R} $ 以下の最大の整数を $ \lfloor x \rfloor $ で表し、$ \lfloor \cdot \rfloor $ を床関数（floor fun

同じ列にある つの式は、の元で同値です。 次の つの式が成立します。

0.はじめに 1.簡単な自己紹介 2.年をとるにつれて衰える能力 3.低下した記憶力で競プロに取り組む 4.AtCoderのレベル感 5.競プロ上達への道のり 6.競プロとの向き合い方 7.競プロの依存性 8.競プロのコミュニティ 7.これから 8.終わりに 9.＜番外編＞もし後悔があるとすれば 0.はじめに こんにちは。競技プログラミング歴一年半のかえでです。 私はAtCoder Problems でLongest Streak にチャレンジしています。Longest Streakは、これまで解いたことのない問題から一日一問以上解いた連続日数を競うものです。今日、この記録が500日に到達しました。私は解説ACもするので、純粋に自分の力で解いた問題ばかりではありません。それでも、こつこつと続けてきた自分を、ほめてもよいのではないかという気持ちになりました。 ここまで長く続けられたのは、At

Twitter で医師を拾ってきて Google のソフトウェアエンジニアにするだけの簡単なお仕事 - 白のカピバラの逆極限 S.144-3 はじめに 「【転職エントリ】Googleに入社します｜Lillian｜note」という、医師から未経験で Google のソフトウェアエンジニアになった記事があります。 note.com 私は、この記事に出てくる「とある元 Google のソフトウェアエンジニア」で、面接の対策を立てました。 記事が出た当初から大反響で、私もそれなりの反応を見まして、いろいろと誤解されているなあ、と思う一方、アドバイザーはあくまでもアドバイザーだから、アドバイザーとして知りえた情報については、口をつぐむべきだと思っていました。 ただ、あまりにも誤解されており、悪影響が大きく、犠牲者も多くなってきたと思ったので、… 同僚からこれについてどう思うか、と聞かれた。元の文章が

ちょくだいさん、ごめんなさい。(ちょくだいさんが中高の後輩で、中学校一年生や中学校二年生の頃の印象からアップデートされていないことも行き違いの原因かと思いますので、この書き方にいたします。) nuc.hatenadiary.org このあいだ書いた上の文章に対して、なぜか、ちょくだいさんに反論されています。 chokudai.hatenablog.com しかし、ちょくだいさんには、かなり感謝と配慮をした文章を書いたつもりでした。 まず、前の方には、ちょくだいさんのおかげで、りりあんさんは模擬面接を受けることになったよ、ちょくだいさんがいなければ知り合うことすらなかったよ、ということが書いてあって、後ろの方には AtCoder のこのあたりの過去問(4問時代のABCのC問題)を解くといい勉強になるよ、とまで書いてあるわけじゃないですか。宣伝までしたくらいの気持ちでしたよ。 というわけで、ち

まぁnucたんはリアル世界では知的で温厚な人間だからこの侮辱的な発言も笑ってスルーしてくれるだろう． 2008-10-11 申し訳ないが、ここでは知的でも温厚でもない。 おかげさまで、 なぜ「大してうれしくない」か - 白のカピバラの逆極限 S.144-3 は500以上のはてなブックマークを稼ぎ、二日で一万五千ものアクセスがあった。 実は、これは極めて計画的なものであった。つまり、実験的に、はてなブックマーク向けの文章を書くにはこうすればよいという自分の仮説を検証するという目的があったのだ。 私は発表当日から カビボ先生に関すること 南部先生は日本人かということ 小林益川理論のほうが分かりやすいために、南部先生の扱いが極めて軽くなること など、それから数日の間にネット上に出てくる話や起きるであろうことが一通り分かる状況にあった。 こういった内容は「こんな訳分からない業績でノーベル賞なんかと

AtCoder Libraryが遅延伝播機能を持つセグメント木 atcoder::lazy_segtree を提供しているものの、何か渡すものいっぱいあるしドキュメントは数学用語だらけだしよく分からん！みたいな人向けの記事です。 問題を解いていて、セグメント木に必要な機能（区間加算操作と区間最小値取得がしたい！みたいな）が明確になったときに、それを実現するためには atcoder::lazy_segtree の生成時に何を渡せばいいかを考えられるようになることがこの記事の目標です。ただしコンテスト中に読める分量ではなくなったので、整数列に対する単純な機能の組み合わせについてはコピペで使えるチートシート的なものを別途作る予定です。→作りました 対象読者は「セグメント木（抽象化も遅延伝播もナシで可）を書いたことがあって、その構造と動作の仕組みについて何となく理解している人」くらいを想定していま

というかチートシートを作りました。C++版APIに準拠しています。 URLはこちら：https://www.notion.so/AtCoder-Library-ACL-01a562f6c38e481e88f5a838fd78eb0e www.notion.so

注意点 「CEDEC2020のPERACONが参加人数が多すぎて、提出物の質が低くなった」という問題については、書いてません。あくまで審査員の質についてだけを書いています。*1 記事を書くにあたって、審査員は匿名で書きたかったのですが、 審査員全員の名前が公開されていて、中途半端に匿名にしても無意味なこと。 根本的な問題では、反省はしてなさそう。 審査員にも責任があるべきといっていること。 なので、審査員の実名を出しました。ただ、悪い部分だけをピックアップすることはないように、できるだけ多くのデータを出し、客観的に判断するように心がけました。 はじめに CEDECというゲーム業界のカンファレンスで、PERACONというゲーム企画コンテストがあります。今年からはCESAというゲーム業界最大の団体の人材育成部会で引き取って、毎年人材を育成するという目的で行っていくことになったようですが、これか

GDC2018 にて Microsoft から「Inertialization: High-Performance Animation Transitions in 'Gears of War'」と題した講演が行われました。実用的で良い講演だったので解説していこうと思います。 www.gdcvault.com 講演概要 従来のクロスフェードによるアニメーションブレンドでは、ブレンド中に2つのアニメーションを評価する必要があり、ゲームの状態により瞬間的な処理コストが跳ね上がるという問題を抱えている。 Gears of War ではアニメーションブレンド時に2つのアニメーションを評価する事を辞め、アニメーション遷移後のポスト処理としてブレンドを行った。 ブレンド開始時点の関節速度を維持することで、遷移前アニメーションの評価を止めても自然なブレンドを実現できる。 従来のクロスフェード Gears

長さ の数列 が与えられる。以下のクエリにたくさん答えよう。 クエリ : 区間 中に出現する数の種類数を求めよ 以下の制約で、効率的に解くことはできるだろうか？ 数列の長さ： 要素の値： クエリの数： 以下、解法を3つ紹介する。 解法1 : Mo's algorithm 事前にクエリを特別な方法でソートしておけば、区間を左右に動かすだけで簡単に求まる。 この記事では深入りしないが、ざっくり説明すると 数列を 個のバケットに分け、クエリを < のバケット番号, > でソート 配列 d[x] : 値 x を現在の区間でいくつ持ってるか を用意 (0で初期化) ソートしたクエリを順番に処理するとき、L／Rの増減に合わせて以下の処理をする。 d[(増えた位置の数 or 減った位置の数)] の値を増減し、d[x] が 1 に増えた or 0 に減ったら現在の答えに ±1 計算量は 。 解法2 : も

職場が変わって、前の職場と比べるとよりインターナショナルになりました。今はアメリカ人の人はいてなくて、インド、メキシコ、ロシア、中国、エジプト、ブラジルかなりインターナショナルです。 前回私は批判についての気づきをシェアしましたが、今までのブログの中でも１、２を争うぐらいに多くの人に読んでいただいたみたいです。そのリアクションの中で、多く含まれたコメントが「批判」と「非難」「中傷」はちがうというコメントが多くありましたの、今回はそのトピックに関して書いてみたいと思います。 simplearchitect.hatenablog.com 反対意見や批判が全くつらくない職場 私がアメリカに移ってから職場が２つ目ですが、今まで反対意見を言われたり、批判をされたときに心がつらくなったことがありません。日本にいたときを思い起こすとそうではなくて、批判や、反対意見を聞くと正直心がつらいと思っていました。

std::multiset の罠っぽい仕様と，その仕様なのが妥当だと思えそうな説明をするやつをします． 気が向き次第，別の罠や初心者向け tips も今後扱うと思います． 罠 以下の二つについて正しく答えられますか？ erase std::multiset<int> ms; ms.insert(0); ms.insert(10); ms.insert(10); std::cout << ms.count(10) << std::endl; // 2 ms.erase(10); std::cout << ms.count(10) << std::endl; // ? 10 が一つ消えて 1 と出力されるか，全て消えて 0 と出力される，などが考えられますね． count ms の要素数が \(n\) のとき，ms.count(x) の計算量はいくらでしょう？ 答え合わせ ms.erase(1

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！ 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美味しさの総和 選んだ寿司に含まれるネタの種類数を として の合計値で決まる。スコアの最大値を求めよ。 制約 考えたこと この手の最適化問題では ある量を決めるとどうすべきかが Greedy に決まらないか 「こういうものだけ探索すればよい」というのが絞れないか をひたすら考えることになる。こういう考察を意識的にやることは高難易度でも有効なイメージ。この問題では 選ぶネタの種類数 を固定したくなる。 を決めると最適解が自然に決まるのではないかと考えたくなる。ここでしばしばやる注意点として 選ぶネタの種類がちょうど でなければならない としてしまうと考

これはレイトレアドベントカレンダー2019の記事です。 https://qiita.com/advent-calendar/2019/raytracing https://enoki.readthedocs.io/en/master/ enokiというのは最近公開されたC++テンプレートライブラリで、SIMDやCUDAによるベクタライズを抽象的にサポートした算術ベクトルライブラリとなっており、自動微分も可能なものになっています。SIGGRAPH ASIA 2019で発表されたMitsuba2(https://rgl.epfl.ch/publications/NimierDavidVicini2019Mitsuba2)はenokiを全面的に採用しており、SIMDによる"wide"なレンダラを容易に記述できる、Differentiable Rendererを容易に記述できる、といった恩恵が得ら