普通の人が資産運用で 99.1 点をとる方法とその考え方
この記事は、みすてむず いず みすきーしすてむず Advent Calendar 2023 12/13 の記事です。
昨日 12/12 は中村さんのVueどーじょー1期生の感想 でした。
はじめに
これを読んでください
本記事には当該記事の 0.1/99 くらいの価値があります
あと新NISAの口座を作ってください
免責事項
本記事に記載されるいかなる情報も、投資への勧誘、特定の商品の勧誘や売買の推奨、特定商品、銘柄および株式指数その他投資対象の上昇または下落、あるいは将来の運用成果について示唆あるいは保証することを目的としたものではありません。
本記事は「現状有姿のまま」で提供します。筆者は可能な限り正確性を保つ努力を行いましたが、本記事の記述内容が現に正確またはいかなる読者の投資目的に適合することを保証するものではなく、筆者は本記事についての一切の責任を負いません。また本記事に含まれる情報もしくは内容を利用することで直接・間接的に生じた損失・損害に対し筆者が一切責任を負わないことについて、読者は本記事の閲覧を継続することで同意したものとします。
0.1 点を稼ぐ
外国ETFで99.1点になる話は本文中にもありますが、それではありません。
市場平均ってなんか言葉が弱そうなんですけど。ほんとに市場平均を目指すだけでいいんですか？もっと上を目指さなくてよいのでしょうか？
はい。
- 株式市場の取引のほとんどは「機関投資家」というプロ中のプロにより行われています。
ここです。ここに付け入る隙があります。
機関投資家は株をごっそり買います。ごっそり買ったときのリターンが最適になるのが「市場平均」なのですが、一方で我々個人は買えて単元株――日本株100株とか、です。 そのため、当該記事中でも「個別株を買うとリターンに比してリスクが大きい個別株をポートフォリオ(PF)に入れるとシャープレシオが下がる」（要約）と言われています。
では、個別株をPFに入れるリスクに相応するリターンがあればいいですね。
程よい株主優待を探しましょう。
株主優待の探し方
[株主優待 おすすめ] [検索]
↑ ばかです
基本的に、そういう検索で上位に出てくるのは大多数の人がふんわりと納得している程度のものでしかありません。
- その株主優待は本当にPFを歪めるだけのリターンがありますか？
- そのグルメ詰め合わせ（もしくは、類似の汎用性が低すぎるクーポン券・商品現物・etc.）は本当に額面相応の効用がありますか？
- そのクオカード（もしくは、類似の汎用性が高すぎる商品券・引換券・etc.）は企業の本業と関連性がありませんが、本当に株主優待は継続しそうですか？
よって考えるべきは、1, 2 番に yes と答えられて、3 番に該当しないもの。自分が日頃使うサービスであったり、小売・飲食店であったり……が 運良く やけに割のいい株主優待をしている場合のみPFに入れるべきでしょう。
具体例
免責事項をもう一回読んでください
- 百貨店系
- 大体現金 or 系列カード限定で10%引き。年あたりにその株の評価額 (いまのところ15-30万くらい) 使えば利回り10%。
- 上の「検索」で出てくる有名所と比較すると、たとえばイオンは 3% キャッシュバック。年に100万くらい使えば (イオンガチ勢は普通に使いそうだな……？) 利回り10%。
- クリスタ
- 私は使ってないんですが :twitter: でよく見た。でも買い切り版復活したらしいですね
- 鉄道系
- 自宅がターミナルから遠いほど役に立つとされる [要出典]
定額なんぼよりも何％引き/何％増しとか、利用権・全線無料とかのほうが嵌ったときに率が良いので狙い目。そういう優待は金額換算しづらいことも多く、「株主優待 おすすめ」では出てきません。ちょっとググってみたけど0円換算されているサイトばっかり。
個別株を含むポートフォリオの構築
eMAXIS Slim 全世界株式（除く日本）を個別日本株の評価額の16倍を目安に買います。これでPF構築は完了です。 本文中でも述べられていることですが、ロボアドとか銘柄を自動リバランスする包括サービスとか、まして人の温かみのある匠の技なんてものはすべてコストが余計に掛かる要因なので忘れてください。
逆に言えばリスク資産全体の1/17くらいしか日本株に手を出すべきではありません（ホームアセットバイアス）。 この割合を守っていても株主優待がある企業は to-C のサービスで稼いでいるところが多く、さて日本株全てを「そういう」株に代表させていることになるので、日本の工業株金融株なんかはPFに入ってきません。
世界全体からトヨタを抜いた代わりに国内の個人にしか使えないお小遣いがもらえるPFは、トヨタが調子良いときには相対的に損をすることになります。その分の超過リターンがもらえるか、個別株に手を出す前にもう一度考えましょう。
でも年一で送られてくる優待の封筒は「儲かってまんな」という気持ちになって嬉しいのも確か。元記事に言う「年に30分のリバランス」にもう30分だけ掛けていい感じの個別株を探すのはアリだと思います。
見つからなかったらその分TOPIX連動でも買ってください。
明日12/14はサンドリヨン鈴木さんの「多分Subsonic APIとかかもしれません」です。Subsonic は音楽ストリーミングソフトの Subsonic でしょうか？
【BPL2021】SUPERNOVA Tohoku セミファイナルへの道
この記事はセカンドステージ 10 試合目終了時点のものです。
順位の決定方法
- 勝点
- 全獲得pt
- 直対での獲得pt
- 抽選
セミファイナル進出条件
- ファーストステージまたはセカンドステージで 1 位である
- ファーストステージまたはセカンドステージで 2 位であり、ファーストステージ、セカンドステージを通してより勝ち点が高い
問題点
- 両ステージで 1 位チームが同一である場合の成文規定がない
- セミファイナル優先順位からの憶測で 2 位チーム 2 つが進出できそう
- ある 2 位チームが別ステージで 1 位を獲得している場合の成文規定がない
- 当然「ファーストステージ、セカンドステージを通してより勝ち点が高い」のは 1 位を取ってる方の 2 位チームである
- セミファイナル優先順位からの憶測でもう片方の 2 位チームが進出できそう
- 両ステージの {1位, 2位} が一致した場合の規定がない
- → この場合 3 位チーム同士で勝点の和が高いほうが SF 進出と仮定する
- 両ステージの 2 位チーム(若しくは上記の例での 3 位チーム) の勝点の和が同一の場合の規定がない
- → この場合両ステージの直対での獲得 pt の和 → 抽選 の順と仮定する
- （SUPERNOVA の勝ち点が低いのでここのケースはあまり問題にならない)
- → この場合両ステージの直対での獲得 pt の和 → 抽選 の順と仮定する
ファーストステージ
- 1位：ROUND1 (勝点 13)
- 2位：APINA VRAMES (勝点 8)
- 3位：GAME PANIC (勝点 7)
- 4位：SILK HAT (勝点 6)
- 5位：LAISURE LAND (勝点 3)
- 6位：SUPERNOVA Tohoku (勝点 2)
セカンドステージ
| ST | R1 | AV | GP | LL | SH | 勝点 | pt | 残 | |
|---|---|---|---|---|---|---|---|---|---|
| SUPERNOVA Tohoku | x | ○ 7-5 | ○ 8-4 | ● 2-10 | ○ 12-0 | 9 | 29 | 1 | |
| ROUND1 | ● 5-7 | x | ○ 10-2 | ○ 9-3 | 6 | 24 | 2 | ||
| APINA VRAMES | ● 4-8 | x | ○ 8-4 | ○ 11-1 | 6 | 23 | 2 | ||
| GAME PANIC | ○ 10-2 | ● 2-10 | ● 4-8 | x | ○ 7-5 | 6 | 23 | 1 | |
| LEISURE LAND | ● 1-11 | ● 5-7 | x | ○ 11-1 | 3 | 17 | 2 | ||
| SILK HAT | ● 0-12 | ● 3-9 | ● 1-11 | x | 0 | 4 | 2 |
実はここまで引分がない
SUPERNOVA Tohoku セミファイナル進出条件
- LL との直対に勝ち
- 12 pt なら (R1 or AV) の片方にしか負け得ないので、進出確定
- LL との直対に引き分け
- (R1△AV, R1○LL, AV○SH) 以外 ならセーフ
- ↑をやられると 1st 3 位の GP との 3 位比較で負ける、という芸術的な負け方をする
- （厳密には 7 pt 以上同士の引分をすると pt 差で勝てる可能性が微粒子レベルで存在するが無視）
- (R1△AV, R1○LL, AV○SH) 以外 ならセーフ
| ST | R1 | AV | GP | LL | SH | 勝点 | pt | 順位 | |
|---|---|---|---|---|---|---|---|---|---|
| SUPERNOVA Tohoku | x | ○ 7-5 | ○ 8-4 | ● 2-10 | △ 6-6 | ○ 12-0 | 10 | 35 | 3 |
| ROUND1 | ● 5-7 | x | △ 6-6 | ○ 10-2 | ○ >7-x | ○ 9-3 | 10 | >37 | 1-2 |
| APINA VRAMES | ● 4-8 | △ 6-6 | x | ○ 8-4 | ○ 11-1 | ○ >7-x | 10 | >36 | 1-2 |
| GAME PANIC | ○ 10-2 | ● 2-10 | ● 4-8 | x | ○ 7-5 | ? | 6~9 | 23 | 4 |
| LEISURE LAND | △ 6-6 | ● | ● 1-11 | ● 5-7 | x | ○ 11-1 | 4 | 24 | 5 |
| SILK HAT | ● 0-12 | ● 3-9 | ● | ? | ● 1-11 | x | 0~3 | 4 | 6 |
↑芸術的な負け方
- LL との直対に負けると結構細い他力条件
- 現状 R1-AV が残っているので ST は実質 2 位、というのが厳しい
| ST | R1 | AV | GP | LL | SH | 勝点 | pt | 残 | |
|---|---|---|---|---|---|---|---|---|---|
| SUPERNOVA Tohoku | x | ○ 7-5 | ○ 8-4 | ● 2-10 | ● | ○ 12-0 | 9 | <34 | 0 |
| ROUND1 | ● 5-7 | x | ○ 10-2 | ○ 9-3 | 6 | 24 | 2 | ||
| APINA VRAMES | ● 4-8 | x | ○ 8-4 | ○ 11-1 | 6 | 23 | 2 | ||
| GAME PANIC | ○ 10-2 | ● 2-10 | ● 4-8 | x | ○ 7-5 | 6 | 23 | 1 | |
| LEISURE LAND | ○ | ● 1-11 | ● 5-7 | x | ○ 11-1 | 6 | >24 | 1 | |
| SILK HAT | ● 0-12 | ● 3-9 | ● 1-11 | x | 0 | 4 | 2 |
- 勝点 9 単独 1 位
- SH - GP で GP が ST の pt 以上となるような勝利をせず、かつ R1, AV がここから 2 分け
- めちゃくちゃ細い
- SH - GP で GP が ST の pt 以上となるような勝利をせず、かつ R1, AV がここから 2 分け
- 勝点 9 で 2 位かつ R1 or AV が 1 位
- (R1△AV, R1○LL, AV○SH) でない、かつ厳し目な pt 勝負
- これも細い
- (R1△AV, R1○LL, AV○SH) でない、かつ厳し目な pt 勝負
結論
勝て。
レバナス vs QLD
はてブロはカス
何故か画像が表示されないのでこっち見て→ https://github.com/omi-key/misc/blob/master/QLD/%E3%83%AC%E3%83%90%E3%83%8A%E3%82%B9%20vs%20QLD.ipynb
.
.
.
.
.
.
.
本編
昨今のコロナ禍も目じゃなく伸びている株式インデックスにアメリカ株の NASDAQ100 がある。
だいたいGAFAMとテスラとzoomとなんかそこら辺の強そうな株が突っ込まれているので、日経平均だの S&P 500 だのを尻目にぐんぐん伸びている。
ところで ETF 界には、各インデックスに「日々の値動きの x 倍 (-3 <= x <= 3)を目指す」ような設計をしたやつが結構いる。先物取引を利用してなんやかんやするのだが、昨今の低金利でキャリーコストが下がっているせいもあってめちゃくちゃに流行っている。
当然 NASDAQ100 に正のレバレッジを掛けた商品を買いたいのだが、如何せん日本から直接は買えない。（S&P 500 のレバレッジ ETF は買えたりする）
しかしここに iFreeレバレッジ NASDAQ100 、通称レバナスなる投信があって、これはドルベースで NASDAQ100 指数の 2 倍を目指して運用されているような商品である。じゃあこれは日本で買えない QLD の替わりになるんじゃないか、ということで QLD 比でのパフォーマンスを調べてみた。
免責事項 - Disclaimer
本記事に記載されるいかなる情報も、投資への勧誘、特定の商品の勧誘や売買の推奨、特定商品、銘柄および株式指数その他投資対象の上昇または下落、あるいは将来の運用成果について示唆あるいは保証することを目的としたものではありません。
本記事は「現状有姿のまま」で提供します。筆者は可能な限り正確性を保つ努力を行いましたが、本記事の記述内容が現に正確またはいかなる読者の投資目的に適合することを保証するものではなく、筆者は本記事についての一切の責任を負いません。また本記事に含まれる情報もしくは内容を利用することで直接・間接的に生じた損失・損害に対し筆者が一切責任を負わないことについて、読者は本記事の閲覧を継続することで同意したものとします。
データ元
- Yahoo! Finance
- 大和アセットマネジメント
それぞれデータDLボタンがあるので押して適当にリネームして配置した。
方針
日本の投信のうち主に海外資産を運用する商品は、時差を考慮して
という流れになっている。つまり、日本時間で x 日の基準価額はアメリカ時間 x-1 日の終値に依存する。
まあ日米ともに祝日があるはずだけれど、今回のコードでは深く考えずに、日本時間の基準日の直前営業日における終値を用いて QLD の米ドル・日本円価格を算出した。
import pandas as pd import numpy as np import matplotlib.pyplot as plt %matplotlib inline import seaborn as sns
データ読み込み
レバナス
csv ははやく encoding が UTF-8 のもののみ valid として欲しい。
levnas = pd.read_csv("rev_NASDAQ.csv", encoding="SHIFT-JIS")
用いる終値、基準日を取り出しておく。
ついでに後ほど求める QLD 価格(usd, jpy) のカラムを用意する。
levnas["close"] = levnas["基準価額"] levnas["date"] = pd.to_datetime(levnas["基準日"], format="%Y%m%d") levnas["qldusd"] = 0 levnas["qldjpy"] = 0 levnas
| 基準日 | 基準価額 | 前日比 | 純資産総額 | 直近決算日 | 直近分配金 | 分配金再投資基準価額 | close | date | qldusd | qldjpy | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 20181019 | 10001.0 | 0 | 300033250 | 0 | 0 | 10001 | 10001.0 | 2018-10-19 | 0 | 0 |
| 1 | 20181022 | 9998.0 | -3 | 299937512 | 0 | 0 | 9998 | 9998.0 | 2018-10-22 | 0 | 0 |
| 2 | 20181023 | 10132.0 | 134 | 303965761 | 0 | 0 | 10132 | 10132.0 | 2018-10-23 | 0 | 0 |
| 3 | 20181024 | 10090.0 | -42 | 302696469 | 0 | 0 | 10090 | 10090.0 | 2018-10-24 | 0 | 0 |
| 4 | 20181025 | 9250.0 | -840 | 277496525 | 0 | 0 | 9250 | 9250.0 | 2018-10-25 | 0 | 0 |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 425 | 20200727 | 18468.0 | -1427 | 13454015575 | 20191018 | 0 | 18468 | 18468.0 | 2020-07-27 | 0 | 0 |
| 426 | 20200728 | 19227.0 | 759 | 14006937427 | 20191018 | 0 | 19227 | 19227.0 | 2020-07-28 | 0 | 0 |
| 427 | 20200729 | 18743.0 | -484 | 13900493329 | 20191018 | 0 | 18743 | 18743.0 | 2020-07-29 | 0 | 0 |
| 428 | 20200730 | 19218.0 | 475 | 14477773611 | 20191018 | 0 | 19218 | 19218.0 | 2020-07-30 | 0 | 0 |
| 429 | 20200731 | 19649.0 | 431 | 14811577362 | 20191018 | 0 | 19649 | 19649.0 | 2020-07-31 | 0 | 0 |
430 rows × 11 columns
QLD, USD/JPY
qld = pd.read_csv("QLD.txt") qld.set_index("Date") usdjpy = pd.read_csv("USDJPY.txt") usdjpy.set_index("Date")
| Open | High | Low | Close | Adj Close | Volume | |
|---|---|---|---|---|---|---|
| Date | ||||||
| 1996-10-30 | 114.370003 | 114.480003 | 113.610001 | 114.180000 | 114.180000 | 0.0 |
| 1996-10-31 | NaN | NaN | NaN | NaN | NaN | NaN |
| 1996-11-01 | 113.500000 | 113.500000 | 113.500000 | 113.500000 | 113.500000 | 0.0 |
| 1996-11-04 | 113.279999 | 113.980003 | 112.949997 | 113.879997 | 113.879997 | 0.0 |
| 1996-11-05 | 113.709999 | 114.330002 | 113.449997 | 114.250000 | 114.250000 | 0.0 |
| ... | ... | ... | ... | ... | ... | ... |
| 2020-07-27 | 105.956001 | 106.046997 | 105.121002 | 105.992996 | 105.992996 | 0.0 |
| 2020-07-28 | 105.291000 | 105.679001 | 104.958000 | 105.261002 | 105.261002 | 0.0 |
| 2020-07-29 | 105.110001 | 105.227997 | 104.800003 | 105.107002 | 105.107002 | 0.0 |
| 2020-07-30 | 105.015999 | 105.288002 | 104.912003 | 105.031998 | 105.031998 | 0.0 |
| 2020-07-31 | 104.667000 | 105.795998 | 104.198997 | 104.682999 | 104.682999 | 0.0 |
6198 rows × 6 columns
Date を key にしてマージ。
QLD の Adj. Close と USD/JPY の Close を掛け合わせることで JPY での終値を算出する。
配当などを調整した後の価格が Adj. Close らしい。
qldusd = pd.merge(qld, usdjpy, on="Date") qldusd["close_JPY"] = qldusd["Adj Close_x"] * qldusd["Close_y"] qldusd[["Date", "Adj Close_x", "close_JPY"]]
| Date | Adj Close_x | close_JPY | |
|---|---|---|---|
| 0 | 2006-06-21 | 7.940834 | 911.885664 |
| 1 | 2006-06-22 | 7.753991 | 900.083291 |
| 2 | 2006-06-23 | 7.730908 | 900.960026 |
| 3 | 2006-06-26 | 7.759483 | 901.807122 |
| 4 | 2006-06-27 | 7.469331 | 868.832582 |
| ... | ... | ... | ... |
| 3548 | 2020-07-27 | 162.600006 | 17234.461786 |
| 3549 | 2020-07-28 | 158.559998 | 16690.184267 |
| 3550 | 2020-07-29 | 162.229996 | 17051.508514 |
| 3551 | 2020-07-30 | 163.860001 | 17210.543297 |
| 3552 | 2020-07-31 | 169.679993 | 17762.610538 |
3553 rows × 3 columns
あきらかにこんなにいらないのと、現状 Date カラムが str なので datetime へ変換しておく。
qldjpy = qldusd.loc[3000:, ["Date","Adj Close_x", "close_JPY"]] qldjpy["Date"] = pd.to_datetime(qldjpy["Date"], format="%Y-%m-%d") qldjpy
| Date | Adj Close_x | close_JPY | |
|---|---|---|---|
| 3000 | 2018-05-22 | 83.026443 | 9214.108342 |
| 3001 | 2018-05-23 | 84.413208 | 9346.736700 |
| 3002 | 2018-05-24 | 84.333389 | 9265.625369 |
| 3003 | 2018-05-25 | 84.512985 | 9238.283078 |
| 3004 | 2018-05-29 | 83.754745 | 9161.847801 |
| ... | ... | ... | ... |
| 3548 | 2020-07-27 | 162.600006 | 17234.461786 |
| 3549 | 2020-07-28 | 158.559998 | 16690.184267 |
| 3550 | 2020-07-29 | 162.229996 | 17051.508514 |
| 3551 | 2020-07-30 | 163.860001 | 17210.543297 |
| 3552 | 2020-07-31 | 169.679993 | 17762.610538 |
553 rows × 3 columns
マージ
競プロ民とは思えぬ脳死 O(N2)
430 くらいなら実用上問題ないのでセーフ
for i in range(430): keydate = levnas.loc[i, "date"] j = 3000 while qldjpy.loc[j, "Date"] < keydate: j += 1 levnas.loc[i, "qldusd"] = qldjpy.loc[j-1, "Adj Close_x"] levnas.loc[i, "qldjpy"] = qldjpy.loc[j-1, "close_JPY"]
プロット
QLD(usd)
レバナスの商品設計としてはドルベースの NASDAQ100 (の 2 倍）が基準なので、まずはそのままドルベースの QLD と比較する。
だいたいここ 2 年くらいドル円が 110 円くらいだった気がするので 110 を掛けてプロットしてみる
plt.plot(levnas["date"], levnas["close"], label="leveraged_NASDAQ") plt.plot(levnas["date"], levnas["qldusd"] * 110, label="QLD(USD)") plt.legend()
<matplotlib.legend.Legend at 0x7f2ede4dd9d0>
[f:id:omi_ut:20200803000111p:plain]
よくわからないのでおとなしく比を取る。
plt.plot(levnas["date"], levnas["close"]/levnas["qldusd"])
[<matplotlib.lines.Line2D at 0x7f2ede3d6fa0>]
[f:id:omi_ut:20200803000121p:plain]
設定当初は 117 くらいだった比がコロナ前 114 までじわじわと落ち込み、その直後急に 118 程度で安定するようになっている。
これはレバナスが為替ヘッジをしているためであると考えられる。コロナ前は日米金利差がそこそこあったのでヘッジコストが発生していたが、アメリカの金利もゼロになったのでヘッジコストがほぼ無になり、この比が安定したようだ。たぶん。
じゃあなんで為替ヘッジなんてするんですかというと、先物取引の都合上ファンド資金はそのまま証拠金になり、ドルベースの差金決済取引になるので本来差金分しか為替影響を受けない中途半端な状態になってしまう。であれば、ということでいっそまるごと為替ヘッジをしているのだと思う。
たぶん。
QLD(jpy)
ところで普通にアメリカ ETF 買った時に為替ヘッジなんてしませんよね？ ということで日本円ベースで比較
plt.plot(levnas["date"], levnas["close"], label="leveraged_NASDAQ") plt.plot(levnas["date"], levnas["qldjpy"], label="QLD") plt.legend()
<matplotlib.legend.Legend at 0x7f2ede3b62b0>
[f:id:omi_ut:20200803000131p:plain]
plt.plot(levnas["date"], levnas["close"]/levnas["qldjpy"])
[<matplotlib.lines.Line2D at 0x7f2ede3833a0>]
ドル円の動きに従って結構跳ねているが、コロナ以降はQLD比 1.1 と今までよりも高値圏で安定しているように見られる。
当然円高が進めばその分為替ヘッジを行うレバナス有利な戦いになる。
ここまでのまとめ
ヘッジコスト (≒金利差) が発生しない間においては、レバナスは完全に QLD 互換と言ってよさそう。
結論
大和アセットマネジメントははやく TQQQ 互換を出して やくめでしょ
intro-heuristics AtCoder Contest Scheduling
https://atcoder.jp/contests/intro-heuristics/standings
20 位。ギリギリ1ページ目に乗った
~21:00
テンプレートの準備。
rdtsc と焼きなましテンプレはコピペして、ONLINE_JUDGE があるので input() の受け取りをするかどうかを環境で切り分ける部分も先に書いておいた。
cat /proc/cpuinfo で CPU が 3.00 GHz に上がっていることを確認して rdtsc の定数をちょっと書き換えたりした。
21:00~ 21:09
A を読んでから B を解く。
やりたいことはなんとなくわかったけど、サンプルが D=5 なせいでちょっと手間取る。こういうのは const int D=365; したくなる人間なので……。
なんとか直して提出！
毎行出力させるのを忘れていました。ちゃちゃっと直した所 B 問題にも 5 分制限が掛かっててキレた。
B問題の「毎行出力させる」のはあきらかに高速化の障害になる気がするのですがどうなんでしょうか。
21:09 ~ 21:24
思考停止で一点変更焼きなましを書く。差分計算を高速化する前にとりあえず書くものを書いて提出した。 → 98.5M
score 関数も 1 日ごとに計算する形のまま、開始温度も適当。 たしかこの時点で 40 位くらいで首を傾げながら唸ってた記憶がある。
21:24 ~ 21:49
裏で時間制限 60s とかまで伸ばすと 110M 相当 (ケース平均 1.2 M くらい)くらい出ることがわかったので高速化。ただしケースごとの分散がバカでかいのであんまり当てにならないなーとか思いながら眺めていた。
score 関数で毎回開催間隔のペナルティを引く必要はないので、開催したときと全部終わった後に c * Δ * (Δ-1) / 2 を引いてあげればよい。ちなみに 1-indexed になるのでもれなくバグ祭りが開催されており、死ぬ気でバグを取って提出！
デバッグ用の早期リターンを消し忘れてた。ついでに 1-indexed バグも取りきれてなかったので除去して再提出。 → 110.9M
21:49 ~ 22:13
ここまで差分計算が全計算の差になっているので、差分だけ軽く計算する方法を考えていく。
s_i,d はすぐだが、c[i] の絡むペナルティが面倒だった。お絵かきをすると、変更する d 日目の前後 prv, nxt をなんとか持ってきて c[x] * ((nxt-d-1) * (nxt-d-2) / (d+1-prv) * (d-prv) / 2 - (nxt-prv) * (nxt-prv-1) / 2); を足し引きすれば良いことがわかる。prv nxt は set<int> + set.lower_bound で持ってきていたが 実はこれが大間違い らしく、コンテナの中の要素数が高々 20 くらいなので普通に vector でゴリゴリやるほうが速いらしい。たしかに……。
まあなんとか実装したし、回転数も 5 倍以上、 20M くらい回るし、提出！ → 106.8M なんで？？？？？？？？
22:13 ~ 22:26
また 1-indexed でバグらせていた。 21:24 の提出 (確実に Δscore が合っている submit) と突き合わせながら必死のバグ取りをして 117.5M。
22:26 ~ 22:38
ここからは温度変化管理の時間。温度管理たのしい！！！！
dscore, prob, score, maxscore を stderr に並べながら良さげに焼ききれるかを目でなんとなく眺める作業。最終盤にスコアが伸び切らない場合は緩すぎて、中盤からそこそこの値で息切れする場合は固すぎる。
またなんかバグが残ってたのを取ったりしてパラメタ調整。 118.0M
22:30くらい ~ 22:44
今更 裏で回していたスコア検証用のコードに再現性がないことに気づく。原因としては手抜き XorShift を使っていたため seed が固定できていなかった。
ちゃんとしたものを探してコピペし直し、提出用コードにも反映した。 120.0M
22:44 ~ 22:55
裏で温度管理芸人しながら 2 点変更 (2 点 swap ではなく、 1 点変更 * 2 回) したら満遍なくならないかなーと考えているうちに時間切れ。
最終的に startTemp = 1150 という中途半端な数字で 121.5M
23:00
提出時 19 位が 20 位になっていた。
その後も抜かされることはなく 1 ページ目はギリギリで死守できた。
23:03
C 問題を見る。
「日付 $d$ とコンテストタイプ $q$ をランダムに選び、$d$ 日目に開催するコンテストをタイプ $q$ に変更する」という変形操作は実はあまり良くありません。
はい。
abc143_f Distinct Numbers
原因
列を取り出す個数の方を固定して最大の長さを考える
↑この考察がどうひねっても出てこなかった
問題
https://atcoder.jp/contests/abc143/tasks/abc143_f
$N (\le 3 \times 10^{5})$ 個の整数 $A_i \in [1,N]$ から、相異なるちょうど $K$ 個の整数からなる組を最大いくつ取り出せるか。
$K = 1, 2, \ldots, N$ のそれぞれについて求めよ。
自力考察
長さ $K$ の狭義単調増加列を何個取り出せるか、と読み替える。
$C_j$ を $A_i = j$ なる $i$ の個数、$D_k$ を $C_j \textcolor{magenta}{\le} k$ なる $j$ の個数とするまでは良かったが、$\sum D_k / K$ がダメだったため頭を抱える。（ちょっと $D$ の定義が違うけど誤差）
反例： $A=\{1,1,2,3,4,5,5\}$ （→ $D = \{5,2\}$）で $K=3$ のとき。
解説AC
$X(1 \le X \le N)$ 個の列を取り出すときの最大の長さを表す関数 $f(X)$ を考えます。
天才
$X$ 個の列を取り出すとき、各整数 $j \in [1,N]$ は高々 $X$ 回しか使えないのでそれを超える分を無視しても一緒。あとは各列に整数を満遍なく割り振ることで、各列の長さの（最小値の）最大を実現することが可能である。
以上を式で表すと
$$ f(X) = \left\lfloor \frac{\sum_{j=1}^N \min(C_j,X)}{X} \right\rfloor $$
となる。すべての $X$ について $f(X)$ を求めたあとは各 $K$ について $K \le f(X)$ を満たすような最大の $X$ を出力すればよい。
考察
解説下段の $f(X)$ の式変形が面倒（というか絶対思いつけなさそう）なので元の式 $$ f(X) = \left\lfloor \frac{\sum_{j=1}^N \min(C_j,X)}{X} \right\rfloor $$ からなんとか考察したい。
$C_j$ は$A_i = j$ なる $i$ の 個数 なので、$C_j$ の昇順にソートしても差し支えない。ここで、二分探索によって $C_j \le X$ となる最大の添字 $j = J$ を求めることで、 $$ f(X) = \left\lfloor \frac{\sum_{j=1}^N \min(C_j,X)}{X} \right\rfloor = (N-J) + \left\lfloor \frac{\sum_{j=1}^J C_j}{X} \right\rfloor $$
と求めることができる。これは予め $C$ の累積和を求めておけば時間 $O(\log N)$ で求められるので、全体で $O(N \log N)$ で解ける。
あとは $X=0$ でバグらないようにして完成。
提出コード
初AC（添字お祈りゲーをした）: https://atcoder.jp/contests/abc143/submissions/9960709
リファイン版: https://atcoder.jp/contests/abc143/submissions/9961265
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(int)(n);i++) int n,a; vector<int> c, rui; int f(int x){ auto it = lower_bound(c.begin(), c.end(), x); int i = (int)(it - c.begin()); return (n-i) + rui[i] / x; } signed main(){ cin >> n; c.resize(n); REP(i,n){ cin >> a; c[a-1]++; } sort(c.begin(), c.end()); rui.resize(n+1); REP(i,n) rui[i+1] = rui[i] + c[i]; int ans = n; REP(i,n){ while(ans && f(ans) < i+1) ans--; cout << ans << "\n"; } }
感想
解説通りにACとならないときに、こういう記事に自分の考察まとめるのこそ競プロブログって感じがする
変数の方を固定してなんとかする発想は言われてみれば頻出な気がしてきたので今後頑張ります
_ が2個あると装飾が優先されるからエスケープする
abc147_e Balanced Path
原因
bitsetがこんなに速いとは知らなかった
問題
https://atcoder.jp/contests/abc147/tasks/abc147_e
$H \times W (\le 80 \times 80)$ のマス目に $T_{ij} = \rm{abs} (A_{ij} - B_{ij}) \in [0,80]$ が書かれている。
$\left(1,1\right)$ から $\left(H,W\right)$ までマス目の下か右に移動する。このとき適当な移動経路上のマス目 $\left(i,j\right)$ について、$+ T_{ij}$ または $- T_{ij}$ の和を適切に取り、和の絶対値(:= 偏り)を可能な限り小さくする。考えられうる 偏り の最小値を求めよ。
解法
dp[i][j][k]をマス $\left(i,j\right)$ において偏りが $k$ になりうる、という真偽値で定義されるDPを考える。
この更新はbitsetを使うと非常に高速に実現でき、dp[i-1][j]とdp[i][j-1]をそれぞれ左右に$T_{ij}$だけシフトした値、合わせて4つ全ての $\rm{OR}$ をとれば求められる。初期値としてはdp[0][-1]において、偏りが0に相当する値のビットを立てておけばよい。
いま考えられうる偏りの最大値は $\max (H+W) \times T_{ij} = 12800$ だから、bitsetの幅として26000くらいを取っておけば十分。
事故
bitsetを使い慣れていなかったためmapで行けるでしょ、と考えて 1TLE。TLEの解消を小手先でやろうとして失敗、更に 2WA。
bitsetになってからもシフト幅が正じゃないとバグることを知らず1WA。ついでに無駄にDP領域をケチったため1WA。
計5ペナ。本番じゃなくて本当に良かった
対策： bitsetを細かいミスなくちゃんと使えるようになる。
bitsetでいけるって知ってたら瞬殺だったはずでは
提出コード
初AC: https://atcoder.jp/contests/abc147/submissions/9885352
リファイン版: https://atcoder.jp/contests/abc147/submissions/9887569
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for (int i=0;i<(int)(n);i++) int h,w; int table[81][81], t; // 0-indexed bitset<26000> dp[81][81]; // 1-indexed signed main(){ cin >> h >> w; REP(i,h) REP(j,w) cin >> table[i][j]; REP(i,h) REP(j,w){ cin >> t; table[i][j] = abs(table[i][j] - t); } dp[0][1][13000] = 1; REP(i,h) REP(j,w){ dp[i+1][j+1] |= (dp[i+1][j] << table[i][j]); dp[i+1][j+1] |= (dp[i+1][j] >> table[i][j]); dp[i+1][j+1] |= (dp[i][j+1] >> table[i][j]); dp[i+1][j+1] |= (dp[i][j+1] << table[i][j]); } int ret = 20000; REP(ind,26000) if(dp[h][w][ind]) ret = min(ret, abs(13000-ind)); cout << ret << endl; }
感想
こういうときの F に限って考察が詰まらずにサクサク解けたので、本番だったらとても辛かったと思う
abc149_e Handshake
原因
コーディングで派手に事故った
問題
https://atcoder.jp/contests/abc149/tasks/abc149_e
$N$ 要素の数列 $A=\{ A_i \}$ から2要素 (同じでも良い) を選んでできるペアの和からなる $N^{2}$ 要素の数列のうち上位 $M$ 個の和を求めよ。
$1 \le N \le 10^{5}$, $1 \le M \le N^{2}$, $1 \le A_i \le 10^{5}$
解法
$A$ は昇順にソートしておく。
(1) 上位 $M$ ペア目に相当する値 $x$ を、$x$ 以上になるペアの数によって二分探索する。
(2) $x$ 以上になるかどうかは各 $A_i$ について、$A$ に対して $x-A_i$ をキーとして二分探索すればよい。
(3) $M$ 個で区切れないときは $M$ を上回らない範囲で $x$ を求めておいて、$x$ の直下ペアの値を答えへ必要なだけ足す。
あとは上からの累積和で当てはまる部分を全部足してOK。計算量 $O(N \log \max A_i)$
事故
(1) x の上限を $2 A_n$ にした
2 2 1 1
など、全要素が同じ時にもれなくバグる 2WA
対策： 要素アクセスで死なないときのOK側は大袈裟に取る
(2) vector に対するにぶたんを手書きした
なんで？
個数を求めるので初期値を-1とnにして……などと無駄な思考リソースを使った。 0WA
対策： STLに慣れる
(3) 直下ペアを求める時に配列範囲外アクセスした
$x$ の直下ペアを各 $A_i$ についてそれぞれ求める際、$A_i + A_1 \ge x$ のときに存在しない $A_0$ を叩いていた。 1WA
なんかREにならなかったので気づくのが遅れた
対策： continue判定をケチらない。そもそもなんかコンパイラオプションあったはずなので調べる
提出コード
初AC https://atcoder.jp/contests/abc149/submissions/9879339
リファイン版 https://atcoder.jp/contests/abc149/submissions/9879559
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for (ll i=0;i<(ll)(n);i++) ll n,m; vector<ll> a; ll f_ind(ll i, ll x){ auto it = lower_bound(a.begin(), a.end(), x - a[i]); // (2) return a.end() - it; } ll fint(ll x){ // x 以下となるペアの数 ll ans = 0; REP(i,n) ans += f_ind(i,x); return ans; } bool f(ll x){ return fint(x) <= m; } signed main(){ cin >> n >> m; a.resize(n); REP(i,n) cin >> a[i]; sort(a.begin(), a.end()); ll ng = 0; ll ok = 2 * a[n-1] + 1; // (1) while(abs(ok-ng) > 1){ ll mid = (ok + ng)/2; (f(mid) ? ok : ng) = mid; } ll rem = m - fint(ok); ll border = 0; REP(i,n) { if (f_ind(i,ok) == n) continue; // (3) border = max(border, a[i] + a[n-1-f_ind(i,ok)]); } ll ans = border * rem; vector<ll> acum = a; acum.push_back(0); REP(i,n) acum[n-1-i] += acum[n-i]; REP(i,n) { ans += f_ind(i,ok) * a[i] + acum[n-f_ind(i,ok)]; } cout << ans << endl; }
感想
コーディングで死ぬの本当に険しい。頭がついていない。
mathjax でのエスケープはバックスラッシュ2個
ところで 「M$」 がリンクになって、対処しないと mathjax が死ぬのがあまりにも💩
