記事一覧
Toyota Programming Contest 2023 Spring Final 参加記録
はじめに楽しかった。
予選Qual A
本当に黄色コーダーですか？
D問題の実装で無限時間を消費してしまい敗北。
Qual B
本当に黄色コーダーですか？(逆の意味)
F問題通ってニコニコしてたら何故かG問題も通せてしまい……。
決勝前日
Twitterを見たらFFが旨そうなカツ丼を食べてたので僕も行く。
とんかつ丸七という店らしい。
美味しいけど油分で死にかけた。
その後とりあえず
N xor [N/2]で隣り合う数のハミング距離が1のbit列が出来るわけ
はじめにみなさん、ハミング距離は知っていますか？
二つの数のハミング距離というのは二つの数を二進数表記した時、何bit異なるかを指します(間違ってたらごめんなさい)。
例えば、$${12}$$と$${45}$$なら$${1100_{(2)}}$$と$${101101_{(2)}}$$でハミング距離$${2}$$です。
さて、ここで隣り合う数のハミング距離が1のbit列を作る方法として$${N}$$
Mo′s Algorithm(クエリ平方分割)について
はじめに区間計算を行う際に累積和やSegment Treeを用いがちですが、それでは上手くいかない問題もあります。
そのような問題の一部を解く手法としてMo′s Algorithmがあります。
次にMo′s Algorithmが使える問題の例を挙げます。
問題$${N}$$個の数$${A_0……A_{N-1}}$$があります。
次の$${Q}$$個のクエリに答えてください。
「$${l,r}$$
高速ゼータ変換を知っていますか？
はじめに高速ゼータ変換、名前いかついですよね。
実は次元の高い累積和みたいなことをやっているだけです。
高速ゼータ変換とは$${2^n}$$個のデータ$${A_0…A_{2^n-1}}$$があります。
各$${0\le i\le 2^n-1}$$について、$${j }$$の立っているbitが$${i}$$にも立っているようなすべての$${j}$$についての$${A_j}$$を考え、それらすべての
AtCoder Beginner Contest 241(Sponsored by Panasonic）について
はじめに実装雑魚なのでF問題一生実装できませんでした😢。
A - Digit Machine確かにループなしでかけるけど、面倒。
$${a_{a_{a_0}}}$$が答え。
B - Pasta配列で個数を持ちたいが、値がでかすぎる。
連想配列などを利用することで高速でできる。
C - Connect 6実装重いがやることは単純。
連続した$${6}$$マスを見て$${4}$$マス以上黒なら
Apex Legendsでのランパートの使い方
はじめに僕はAPEXより前はほぼFPSに触れたことがなく、APEXでも急な戦闘とかが苦手でスナイパーなど遠距離武器が好きでした。
そこでスナイパーと相性の良いキャラ、ランパートを使うようになりました。
現在はほぼランパートしか使っていません。
いわゆる弱キャラ扱いされていますがソロでダイヤに行けるぐらいには使えるので今回はその使い方を解説したいと思います。
持つ武器自由。
一応LMG強化があるの
01-ナップサック(重量・価値が高い場合)
はじめに問題は前回(基本的な動的計画法(価値が高い場合の01-ナップサック))と同じで制約が異なります。
問題内容
重さ$${W}$$まで入るナップサックがあります。
荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。
ナップサックに入れる荷物の価値の和の最大を求めてください。
ただし、同じ荷物を$${2}$$個以上入れることは許されま
基本的な動的計画法(価値が高い場合の01-ナップサック)
はじめに問題は前回と同じで制約が異なります。
問題内容
重さ$${W}$$まで入るナップサックがあります。
荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。
ナップサックに入れる荷物の価値の和の最大を求めてください。
ただし、同じ荷物を$${2}$$個以上入れることは許されません。
制約
$${1\le N\le 500}$$
$
基本的な動的計画法(01-ナップサック)
はじめに01-ナップサック問題とは何なのかという話をしていきたいと思います。
問題内容
重さ$${W}$$まで入るナップサックがあります。
荷物は$${N}$$個あり、$${i}$$番目の荷物は重さ$${w_i}$$で価値が$${v_i}$$です。
ナップサックに入れる荷物の価値の和の最大を求めてください。
ただし、同じ荷物を$${2}$$個以上入れることは許されません。
制約
$${1\
AtCoder黄色になった話
はじめに僕は大学で情報ではなく化学をやっている人です。
それでも、約四年間AtCoderをやることで黄色になることができました。
しかし、情報についての知識はかなり無いので、アルゴリズムにだけ詳しい謎の生命体になってしまいました。
具体的にどれくらい知識がないかというとプログラムを書いて他のファイルを開くやり方すら知りませんし、簡単なWebページを作成するだけで死にそうになります。
AtCode
超基礎的な動的計画法について
はじめに動的計画法ってあまり優しくなさそうですよね。
なんかナップサック問題とかに関わるらしいくらいの認識の人もいると思います。
そこで、今回はもっと簡単な例を挙げていきます。
最小値の計算さて、みなさん数列の最小値を計算するときどのような処理をしているでしょうか？
バブルソートなどでソートし先頭をとる
計算量は$${O(N^2)}$$です。
計算量が重いため、正直これをやる人はあまりいない