ふくぶちょ〜

黄色コーダー

ふくぶちょ〜

黄色コーダー

タイムカプセルを掘り起こした話

懐かしい話を思い出したので綴ることにする。 昔、かわたれ公園と呼ばれる公園が家の近くにあって学校の放課後によく遊んでた。 実際の公園は「空風(そらかぜ)公園」という名前だったがそれを「からかぜ」と読む人が現れいつの間にか「かわたれ」になっていたというのが僕らの通説だった。何か焼き鳥みたいな名前だとよく話題になっていたのを覚えている。 田舎ということもあり土地は有り余っているのかこの公園はかなり広く学校のグラウンド以上の広さがあった。 そのため沢山の子供たちが来ても十分遊べて縄

ふくぶちょ〜

    • 就活について

      はじめにどうも、ふくぶちょ〜です。 就活が終わった(内定取り消しetcが無ければ)ので就活に関する記事を書きます。 参考にできる点もあれば、できない点もありますのでその辺はどうかご勘弁を。 就活に対する考え初めは、仕事したくね〜モラトリアム享受しつづけて〜だから就活したくね〜めんどい〜みたいな気持ちでいっぱいでした(今も一部そう)。 そして、シンプルにやりたいこととか、将来の夢とか、行きたい企業があまり無く、まず何処を受けたらいいのかもよく分かりません。 また、大企

      ふくぶちょ〜

      • Toyota Programming Contest 2023 Spring Final 参加記録

        はじめに楽しかった。 予選Qual A 本当に黄色コーダーですか？ D問題の実装で無限時間を消費してしまい敗北。 Qual B 本当に黄色コーダーですか？(逆の意味) F問題通ってニコニコしてたら何故かG問題も通せてしまい……。 決勝前日 Twitterを見たらFFが旨そうなカツ丼を食べてたので僕も行く。 とんかつ丸七という店らしい。 美味しいけど油分で死にかけた。 その後とりあえずオタクなので秋葉原に行く。 研究室用のUSBメモリが壊れかけていたので新しいUS

        ふくぶちょ〜

        • 破壊の快楽

          はじめにモノを作ることに達成感といったプラスの感情を覚える人がいる。これに違和感はないだろう。世の中を見れば絵を描いたり曲を作ったりしている人が無数にいるからだ。 では、「モノを壊す」ことにプラスの感情を覚える人を想像できるだろうか？ これを聞いてバンクシーの「少女と風船」を思い出した人がいるかもしれない。軽くこれについて述べると、オークション完了後該当作品がシュレッダーによって部分的に破壊されたというものだ。ただし、今回私が述べたい「破壊」とは本質が異なると思われる。想

          ふくぶちょ〜

        タイムカプセルを掘り起こした話

        ふくぶちょ〜

          N xor [N/2]で隣り合う数のハミング距離が1のbit列が出来るわけ

          はじめにみなさん、ハミング距離は知っていますか？ 二つの数のハミング距離というのは二つの数を二進数表記した時、何bit異なるかを指します(間違ってたらごめんなさい)。 例えば、$${12}$$と$${45}$$なら$${1100_{(2)}}$$と$${101101_{(2)}}$$でハミング距離$${2}$$です。 さて、ここで隣り合う数のハミング距離が1のbit列を作る方法として$${N}$$番目の数を$${N\ \text{xor}\ [\frac{N}{2}]}$$と

          ふくぶちょ〜

          N xor [N/2]で隣り合う数のハミング距離が1のbit列が出来るわけ

          ふくぶちょ〜

          Mo′s Algorithm(クエリ平方分割)について

          はじめに区間計算を行う際に累積和やSegment Treeを用いがちですが、それでは上手くいかない問題もあります。 そのような問題の一部を解く手法としてMo′s Algorithmがあります。 次にMo′s Algorithmが使える問題の例を挙げます。 問題$${N}$$個の数$${A_0……A_{N-1}}$$があります。 次の$${Q}$$個のクエリに答えてください。 「$${l,r}$$が与えられるので$${A_l……A_r}$$に含まれる値の種類数を答えよ」 制

          ふくぶちょ〜

          Mo′s Algorithm(クエリ平方分割)について

          ふくぶちょ〜

          高速ゼータ変換を知っていますか？

          はじめに高速ゼータ変換、名前いかついですよね。 実は次元の高い累積和みたいなことをやっているだけです。 高速ゼータ変換とは$${2^n}$$個のデータ$${A_0…A_{2^n-1}}$$があります。 各$${0\le i\le 2^n-1}$$について、$${j }$$の立っているbitが$${i}$$にも立っているようなすべての$${j}$$についての$${A_j}$$を考え、それらすべての演算(足し算や最小最大など)結果を$${B_i}$$とします。 この$${B_i

          ふくぶちょ〜

          高速ゼータ変換を知っていますか？

          ふくぶちょ〜

          AtCoder Beginner Contest 241(Sponsored by Panasonic）について

          はじめに実装雑魚なのでF問題一生実装できませんでした😢。 A - Digit Machine確かにループなしでかけるけど、面倒。 $${a_{a_{a_0}}}$$が答え。 B - Pasta配列で個数を持ちたいが、値がでかすぎる。 連想配列などを利用することで高速でできる。 C - Connect 6実装重いがやることは単純。 連続した$${6}$$マスを見て$${4}$$マス以上黒なら達成可能。 塗る場所を全探索すると$${O(N^4)}$$で通らないので注意。

          ふくぶちょ〜

          AtCoder Beginner Contest 241(Sponsored by Panasonic）について

          ふくぶちょ〜

          Apex Legendsでのランパートの使い方

          はじめに僕はAPEXより前はほぼFPSに触れたことがなく、APEXでも急な戦闘とかが苦手でスナイパーなど遠距離武器が好きでした。 そこでスナイパーと相性の良いキャラ、ランパートを使うようになりました。 現在はほぼランパートしか使っていません。 いわゆる弱キャラ扱いされていますがソロでダイヤに行けるぐらいには使えるので今回はその使い方を解説したいと思います。 持つ武器自由。 一応LMG強化があるのでディヴォーションを持つといいかもしれません。 増幅バリケードの使い方増幅バリ

          ふくぶちょ〜

          Apex Legendsでのランパートの使い方

          ふくぶちょ〜

          01-ナップサック(重量・価値が高い場合)

          はじめに問題は前回(基本的な動的計画法(価値が高い場合の01-ナップサック))と同じで制約が異なります。 問題内容 重さ$${W}$$まで入るナップサックがあります。 荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。 ナップサックに入れる荷物の価値の和の最大を求めてください。 ただし、同じ荷物を$${2}$$個以上入れることは許されません。 制約 $${1\le N\le 36}$$ $${1\le W\le

          ふくぶちょ〜

          01-ナップサック(重量・価値が高い場合)

          ふくぶちょ〜

          人生でやりたいこと・経験したいことリスト(共感性羞恥注意)

          はじめに人生においてやりたいこと・経験したいことってありますよね。 当然僕にもあります。 かなり不可能なものが多いのですが今回はそのリストを大公開しようかなと思います。 (あとで追記する可能性があります) 内容「今からいうことは独り言なんだが」 何かしら重要な職務に就いている自分に対して、アドバイスを求める後輩職員。 しかし、その内容は自分の役職柄重要な情報で漏らしてはいけない。 当然「その質問には答えられない」と強く主張。 後輩職員はうなだれて立ち去ろうとする。 そこで

          ふくぶちょ〜

          人生でやりたいこと・経験したいことリスト(共感性羞恥注意)

          ふくぶちょ〜

          基本的な動的計画法(価値が高い場合の01-ナップサック)

          はじめに問題は前回と同じで制約が異なります。 問題内容 重さ$${W}$$まで入るナップサックがあります。 荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。 ナップサックに入れる荷物の価値の和の最大を求めてください。 ただし、同じ荷物を$${2}$$個以上入れることは許されません。 制約 $${1\le N\le 500}$$ $${1\le W\le 10^{12}}$$ $${1\le w_i\le 10

          ふくぶちょ〜

          基本的な動的計画法(価値が高い場合の01-ナップサック)

          ふくぶちょ〜

          基本的な動的計画法(01-ナップサック)

          はじめに01-ナップサック問題とは何なのかという話をしていきたいと思います。 問題内容 重さ$${W}$$まで入るナップサックがあります。 荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。 ナップサックに入れる荷物の価値の和の最大を求めてください。 ただし、同じ荷物を$${2}$$個以上入れることは許されません。 制約 $${1\le N\le 500}$$ $${1\le W\le 10000}$$ $${

          ふくぶちょ〜

          基本的な動的計画法(01-ナップサック)

          ふくぶちょ〜

          AtCoder黄色になった話

          はじめに僕は大学で情報ではなく化学をやっている人です。 それでも、約四年間AtCoderをやることで黄色になることができました。 しかし、情報についての知識はかなり無いので、アルゴリズムにだけ詳しい謎の生命体になってしまいました。 具体的にどれくらい知識がないかというとプログラムを書いて他のファイルを開くやり方すら知りませんし、簡単なWebページを作成するだけで死にそうになります。 AtCoder黄色になったコンテスト(ABC 233)ABCDEGの6完で7817人中120

          ふくぶちょ〜

          AtCoder黄色になった話

          ふくぶちょ〜

          超基礎的な動的計画法について

          はじめに動的計画法ってあまり優しくなさそうですよね。 なんかナップサック問題とかに関わるらしいくらいの認識の人もいると思います。 そこで、今回はもっと簡単な例を挙げていきます。 最小値の計算さて、みなさん数列の最小値を計算するときどのような処理をしているでしょうか？ バブルソートなどでソートし先頭をとる 計算量は$${O(N^2)}$$です。 計算量が重いため、正直これをやる人はあまりいないと思います。 #include <iostream>#include <vec

          ふくぶちょ〜

          超基礎的な動的計画法について

          ふくぶちょ〜

          自己紹介

          はじめに どうも、ふくぶちょ〜です。 現在は某国立大学の4年生をやっております。 あとちょっとで大学院1年生。 そして更に少し経てば就活。 社会に出たくない僕としては嫌な話です。 うぅ……情けないぜ助けてくれ。 自己紹介 本編 名前：ふくぶちょ〜 年齢：22歳 誕生日：10月16日 血液型：AB型 趣味：お絵描き・競技プログラミング・ゲーム等 所属サークル：計算研究会 好きなアルゴリズム：動的計画法 好きなゲーム：APEX Legends(FPS)・ひまわり-pebbl

          ふくぶちょ〜

          自己紹介

          ふくぶちょ〜