ABC 017 D サプリメント
考えてもよくわからなくて解説を見ました. 見て理解した気になって脳死実装したものの, サンプル以外WA（！）. なんでよ〜とかいいながらあちこちのブログを回ると, 自分の考察の穴がわかり, それを改善するとACできました. にしてもこれかなり難しいと思います...
解答
DPを考えます（どんなDPができるのか, それが思いつきにくいところですが...）
こんなDPができます.
こんな1次元DPで大丈夫なの？？？と思ってしまいますが, 遷移を考えてからそれを検証しましょう.
遷移および基底は,
例えばに対応している場合の数は,
番目までのサプリを前日に飲んでおり, 次の日に
番目のサプリを飲むという事象に対応しています. これを, 同じ日に飲むことができないサプリの番号まで足しあわせていっています. なんとなく遷移の形はよさそうです.
しかし, DPをこの実装で提出すると, なんとサンプル以外すべてWAになります（！）.
実は, 上のの設定が非常にまずい場合を含んでいます.
具体的には, 下のような場合です.
サプリの種類が
1 2 1 1 1 2
となっているとき, 6番目の"2"に対して上のルールでを計算すると,
となります. しかし, サプリの番号が3,4,5のものは同じ種類なので, 一日で一度に食べることができません. よってDPは不適当なことがわかります.
上のルールを改善するには, を拡張する必要があります. 具体的には, 以下のようにします.
は, しゃくとり的に右側にスライドしていくような感じになります.
は単調に増加し, 常に
と比べて大きいものを採用するので, 同じものが2つ以上重複するようなことにはならないことがわかります.
これで部分点が獲得できます.
dpを累積和しておくと, 満点解法になります.
感想
いやーむずい
Ｎａｒｃｉｓｓｕ & Ｎａｒｃｉｓｓｕ -SIDE 2nd- 感想とか
はじめに
フリーゲームの『Ｎａｒｃｉｓｓｕ 』および『 Ｎａｒｃｉｓｓｕ -SIDE 2nd-』をやりました.
『Ｎａｒｃｉｓｓｕ 』はこの執筆の3年前にプレイ済だったのですが, 淡路島に行く機会があったので, 無印, SIDE 2ndとリプレイとプレイをしました.
とても良い作品だと思い, 感想を書き連ねたいと思ったのが執筆の動機です. (ErogameScape内で初めて100点をつけました.)
この記事は『Ｎａｒｃｉｓｓｕ 』および『 Ｎａｒｃｉｓｓｕ -SIDE 2nd-』のネタバレを含みます.
概要
『Ｎａｒｃｉｓｓｕ 』,『 Ｎａｒｃｉｓｓｕ -SIDE 2nd-』は同人サークル『ステージなな』様が製作した全年齢向ビジュアルノベルソフトです[1]. 公式ページから無料でダウンロードして遊ぶことができます.
このナルキッソスシリーズにおいての特徴は, 物語における情報量の少なさにあります.
そもそもビジュアルノベルゲームとは,
電子画面上で読む小説であり、画面に表示される文章に絵や映像、音、選択肢、画面効果などを加えたものである。[2]
と定義されるようなものです. 要するにいつもやっているエロゲやらギャルゲやらのことです. エロゲギャルゲで音声と画像はなくてはならない要素となっています. (えっちシーンのないエロゲ、ボイスのないえっちシーン、物足りない・・・）
ナルキッソスでは, 表示される画像は上下の狭い背景画像のみで, イベントCGは数枚のみしかありません. さらには一度に表示される文字数もかなり少なく設定されています. （だいぶバックログのお世話になりました）
作者様は『情報量の少なさによって物語体験がどのように変化するか』というコンセプトの元でこのシリーズを作っており, 設定でボイスの有無を選択できますが, 公式[1]では以下の見解から, ボイス無しを推奨しています.
ボイス「有り」と「無し」…どっちが上なのか？
上という概念が微妙ですが「無し」が上だと思います。理由はボイスが無いと、脳内イメージ力によって、
無限の理想形を受け手の方が想像できるからです。
仮に数値化すると最高で「∞」の状態だと思います。しかし、もしもイメージ力の弱い人だった場合は、
（時間とかに追われて、そんな状態にあった人も含む）
数値化すると最低で「０」の状態も有りえると思います。結果として最高も無限大だし、最低も０って感じでしょうか。
これに対して、ボイスありの場合は、
脳内イメージする余地がありませんので、
全ての人に均一した数値を与えられると思います。それならば…もしかしたら、
「絵」に関しても同じことが言えるのかも？
（実はシナリオに関しても同じかも知れません）
しかし、絵の無いようなモノは商業では商品価値的にも、
許してもらえません。なので今回は同人で試してみました。
このように, 『Ｎａｒｃｉｓｓｕ 』および『 Ｎａｒｃｉｓｓｕ -SIDE 2nd-』は「受け手」にあらゆるイメージを委ねる手法をとっています. CGやメディアのある場所にはそれだけこだわりがある, ということの裏返しでもあります.
この記事では, 各『Ｎａｒｃｉｓｓｕ 』および『 Ｎａｒｃｉｓｓｕ -SIDE 2nd-』についてそれぞれ感想, 考察や考察メモをまとめます.
Ｎａｒｃｉｓｓｕ
概要・物語
病院の7Fのホスピスにいる男女2人が病院を抜け出し, 死に場所を求めてドライブするお話です.
感想
ゲームをスタートすると, 年間の自殺者数の統計が表示されて, いろいろ予感するものがありました. ちなみにナルキッソスは普通の英語ではNarcissusですが, タイトルの『Ｎａｒｃｉｓｓｕ』において最後の「s」が欠けているのは, 自殺を意味する「suicide」の頭文字を取り除いたものである, とされています[3]. 最終的にはセツミもその統計の一人となりました. オチが見えていても, それが最善の終わり方だとわかっていても, やはり悲しいです. 内容の感想に関しては2ndの方でいろいろ語ります.
システム面で, ゲームの視覚情報の少なさが, よりリアリティを補強していると感じました. コインランドリーで服を物色するシーンや, パチンコ屋の盗み未遂の場面等の生々しい場面では, プレイヤーの想像力が最大限まで掻き立てられたと思います. また, タイプRインテグラのクーペの内装, 外装を写実的に描いています. これらの演出によって, 2次元の物語を3次元に引き上げるような, 現実感を醸し出していました. このリアリティこそが, 今作の独特な読後感を演出しているように思えます.
考察・メモ
物語のモチーフ
セツミは, 「自らの意志」で普通の女子のように水着を着ること, ここではないどこかに行くこと, 死に場所を選ぶことを達成しました.
作中のナルシスとエコーの逸話によると, ナルキッソスはものを言えないエコーの意志の賜物でした. （呪いという形ですが. ）このアナロジーで,
- エコー ←→ セツミ （作中でも言及）
- 呪い ←→ 意志
- ナルシス ←→ 世界（作中において逸話と違って「セツミが呪わなかったもの」として言及）
の対応が成り立ちそうです.
エコーは呪いの代償で, なくなってしまいます. セツミもまた同じく, なんですがセツミは「自らの意志」で死ぬ選択をしているところが大きく違います.
また, 地図を広げて「ここではないどこか」を夢見ていたセツミは世界に恋い焦がれていたとも言えなくないと思います. ここでも, セツミは世界を呪わなかったことが異なっています. なぜ呪っていなかったかというと, 諦めていたからです（作中言）.
（余談 : 原作のギリシャ神話ではエコーが心痛で亡くなったのを見て復讐の女神ネメシスがナルシスに呪いをかけるという話らしいです. )
Ｎａｒｃｉｓｓｕ -SIDE 2nd-
概要・物語
『Ｎａｒｃｉｓｓｕ』の6年前の話で, セツミがまだ7Fではなかったとき, 病院で出会った人たちの物語です.
感想
姫子さんが最初にCGで登場したとき, 思ってた感じと全然違っていて驚きました. 自動車いじりが趣味の姉御肌ということで, なんとなく茶髪でセミロングのヤンキー風な女性を想像していたんですが, CGを見ると清楚系お姉さんでして, 軌道修正せざるを得ませんでした. ん～でも僕のイメージだと物語とマッチしない感じもするので仕方ない気もします. そもそも僕のイメージに偏見がありそうです...
お話としては前作『Ｎａｒｃｉｓｓｕ』でよくわからなかった部分がすべて説明される過去編となっています. セツミがどうして5万円持っていたのか, 車に詳しかったのか, 道に詳しかったのか, 7Fのルールなど, いろいろな謎が明らかになって, 設定がよくできていると感動しました. 前作の発表から今作のリリースに2年かかっているようですが, 整合性が取れているので, 前作を作った時点でこの辺りの設定は存在していたのかもしれません. 後付けであっても好きです.
前作と比べると, 音楽, 登場人物, CGなど, 情報量が増えています.（それでもCGは少ないです） その分, 前作のような独特な作品体験の味は薄くなっています. それでも, 作中のイベントCGはここぞというときに使われているし, OPはeufoniusが歌っているしで, やはり演出面では前作とも劣っていないと思います. 特にCGの美麗さが印象に残りました. 僕は姫子さんがベッドの上で地図を広げているCGと, 姫子さんが祈るCGが好きです. 姫子さんが好きです.
考察・メモ
無印の設定の回収
2ndで回収された設定をまとめてみます.
- セツミが地図, 5万円を持っていた ← 姫子さんから贈られた
- セツミが車に詳しい ← 姫子さんの影響
- 「何よ年下のくせに」← 姫子さん
- 7Fのルール（"友達を作らない"が存在しない） ← 姫子さん（無印の設定というかは微妙）
ほかにもいろいろあると思います. 公式では2→1のプレイ順が推奨されているのは, こうした設定があるからでしょう.
姫子さんはどうして富士山で自殺しようとしたのか
これ, 初見ではちょっとよくわからなかったので.
姫子さんは7Fのヘルパーとして働いていたことがあり, そのときになにもしてあげることができなかった少女に対して負い目を感じていました. 神にいくら祈っても, 何も状況は好転することはありませんでした. ここで描かれているのは, "見送る"アロアの無力さです.
･･･もし･･･私が聖者ならば･･･
･･･もし･･･私の言葉が･･･只の気休めでも、おまじないでもなく･･･
･･････本物の魔法ならば･････････今こそ、奇跡を起こすのに･･･ - 姫子
恐らく神さまはいる…
でもね、どうやら多忙らしいのよ、神さまとやらは
それとも…只、無関心なのかしらね… - 姫子
そこで, 「死ぬまでにやってみたい１０のこと」の最後に, 神に聞こえるように高い場所で, 禁忌を破り, 神へと抗議するという項目があるのでしょう.
飛び降り自殺で神へと到達せんとす, というのは『素晴らしき日々』を思い出します. （結果をみても, その意味合いは全く異なっていますが.）
姫子さんはどうして富士山で自殺しなかったのか
上の考察と対になっています.
最初見たときはここで姫子さんが自殺したら, 姫子さんが大切にしているセツミが帰れないな...とか思っていましたが, おそらくここは本質的ではないので, 別の切り口を考えます.
姫子さんとセツミでこんな会話があります.
「もし、あなたのとても親しい人が、
少しずつ弱っていったとして…」「あなたは傍で、ずっとその姿を見ていたい？」
「………………」
「それとも、自分の知らぬ間に、
いつのまにか亡くなっていて欲しい？」「…わからない」
「私は、ずっと傍に居てあげたいと思うわ」
「でも、自分が去る立場ならば、逆…」
「傍には、誰も居て欲しくない…」
「…矛盾しているわ」
「その通りよ」
「去る者と、残される者は…決して交わることはないのよ」
姫子さんが言う, 「傍には誰も居て欲しくない」というのは, 自分が死ぬことで周りを哀しい思いをさせたくないことを意味しています. そのポリシーがあったからこそ, 親友の優花と妹の千尋に冷たく接したのでしょう.
どうして姫子さんが自殺しなかったのかは, セツミが「哀しい」と感情をあらわにしたことにあると思います.
自分の痛みには耐えれても、相手の痛みは耐えれないから。
去る者が哀しむことは…残される者も一番辛いから… - セツミ
これは, 姫子さんのポリシーに反しているので, 姫子さんは自殺ができません. また, おそらく姫子さんは, 千尋さんや優花さんが同じように哀しんでいることに気づいたのではないでしょうか.
何もできない存在として描かれてきた残される者"アロア"（セツミ）の"祈り"によって自殺を止めることができた, という点から, 「死ぬまでにやってみたい１０のこと」の最後の目標である"神への抗議"は聞き入れられたと解釈することもできます.
物語のモチーフ
今回の物語では, 去る者と残される者の対比として, 『フランダースの犬』のネロとアロアが象徴的なモチーフとして用いられています. また, それに付随して「神」や「祈り」といったの観念的な言葉がクリスチャンの千尋さんや姫子さんの口から語られます.
「祈り」に対しては, 「呪い」が対比として用いられています.
祈りがあるなら･･･呪いもあるってことよ - 姫子
「呪い」の意味するところは, 禁忌を犯し神へと抗議すること, として語られました.
「神」と「祈り」はかなり解釈が難しいところです. 祈りの対象が, 「神」であるとして考えてみます. それを鑑みると, 祈りの対象はあらゆるものすべて, つまり「世界」です. 『素晴らしき日々』っぽい考察ですが, もう少しそっちに寄せていくと, 「祈り」とは『Ｎａｒｃｉｓｓｕ』で語られた方の「呪い」、つまり「意志」です. 今作の「呪い」は, 対比から「世界」の外側（世界にはないもの）への祈りを表しています. 『終ノ空』ですね.
- ネロ ←→ 姫子さん
- アロア ←→ セツミ
- 神 ←→ 世界
- 祈り ←→ 意志
- 呪い ←→ 世界の外側への意志
前作と同じ言葉でも, 意味合いがかなり異なっていることがわかります.
セツミの逆上がり
作中でセツミはたびたび病院付近の学校で, セーラー服を着て逆上がりをします. この行為は, セツミがまだ自分が「健康な人間」であることを確かめるためにやっていることが作中で語られています. この「健康な人間」, あるいは「普通の人間の生活」への執着, というか憧れは, 前作のラストの水着のシーンに繋がるところだと考えられます. 最期に人並みの幸福を手にしたセツミは, 笑うことができたのだと思います. だからこそ, 自分の意志で最期の選択ができたのだと思います.
自分の痛みには耐えれても、相手の痛みは耐えれないから。
去る者が哀しむことは…残される者も一番辛いから… - セツミ
姫子さんがセツミと友達になった理由
作中では, "年下の友達を作ること"が「死ぬまでにやってみたい１０のこと」の一つに入っていることが理由の半分として語られ, もう半分は"予感"と濁されていました. このもう半分とは何だったのでしょうか.
ワンピースを選ばなかったセツミに地図と"5万円"が, 千尋さんの手によって贈られたことを考えると, 姫子さんはやはりセツミが7Fの住人となることを予期していたと考えられます. 憶測ですが, "ネロ"になる前のセツミに, "アロア"の気持ちを伝えたかったのだと思います. ここのワンピースは「セツミが望む日常」のシンボルだったと考えられます. しかし, それを千尋さんに返すことで, 日常を諦めることを示しているのではないでしょうか. しかし, それでも姫子さんの最後の「魔法」はしっかり効きました.
最後に
既プレイ者といろいろ語り合いたくなります. 語り合いましょう.
参考文献
[1]ナルキッソス(公式)
http://stage-nana.sakura.ne.jp/narcissu.htm
[2]岡嶋裕史「日本国内の電子書籍出版にかかわる契約の実情とその問題点に関する考察」,『関東学院大学経済経営研究所年報』第35号, 関東学院大学経済経営研究, 2013年, 83-96頁
[3]narcissuとは (ナルキッソスとは) [単語記事] - ニコニコ大百科
narcissuとは (ナルキッソスとは) [単語記事] - ニコニコ大百科
[4]ギリシャ神話｜ヘーラー：エコーとナルキッソス
ギリシャ神話｜ヘーラー：エコーとナルキッソス
CODE FESTIVAL 2016 Grand Final C - Cheating Nim
解法
まず, Nimなので与えられた数列のXOR和を考えます.
Nimについておさらいしておくと,
- 山のXOR和が0のとき, 後手必勝
- 山のXOR和が0でないとき, 先手必勝
です. 山, 石が0のとき負けのこと, XOR和が0でないときは必ずXOR0の状態に遷移できること, XOR0の状態からはXOR0の状態に遷移できないことを示すことで導かれます.
各山から一個石が取り除けることについて考えます.
具体的に11(=00001011(2進数))個あるものを考えると, 選択肢としては
- 何もしない(11個=00001011(2)のまま)
- 1つだけ取り除く(10個=00001010(2)になる)
の2つの操作ができます.
ここで1つ取り除いたとき, XOR和をとり直すと, 元のXOR和の0ビット目(0-indexed)が反転したものが得られます.
11でなく, 16でこれを試すと,
- 何もしない(16個=00010000(2)のまま)
- 1つだけ取り除く(15個=00001111(2)になる)
これで上と同じようにXORを和をとり直すと, 元のXOR和の0~4ビット目までが反転したものが得られます.
これで法則性が見えました. それぞれの山について, 1つ取り除いたときに最後に1が立つビットより下位のビットをすべて反転させることができます.
アルゴリズムを考えます.
この問題の目的は, XOR和を0にしてやることです. そこで, まず初期のXOR和を計算します.
それぞれのについて, 1が立っている最も下位のビットを記録します.
XOR和のビットを上位から見て, 1が立っているビットがあれば, そこのビット以下を反転させる要素が存在するかどうか調べ, 存在すればそのビット以下をすべて反転させ, カウントを加算します.
ここで, 反転させることができない場合, これ以降どのビットを反転させてもそのビットを0にすることはできないため, -1を出力します.
無事XORを0にすることができれば, カウントを出力します. 上記のアルゴリズムから, このカウントは32より小さいことが示せます.
感想
石を一つ取り除いたときのXOR和の動きに気づいた後は, 蟻本の牛を回転させる問題が参考になります(少なくとも必ず行わなければならない操作を最も損なく行う方法).
AGC 028 B - Removing Blocks
解法
まず, とても愚直な方法を試すと, おそらくの計算量になると思います(next_permutationを用いて取り出す順番を決め,(O(N!)), 一つ取り出すごとに隣接するブロックのコストを合算する計算(O(N))をO(N)回ほど繰り返すので.). 制約をみると, とても愚直な方法は間に合いそうにありません.
そこで, 『あるブロックのコストが何回足されるか』に着目してみます.
ある位置のブロックのコストが何度足されるかだけを考え, 後で掛けあわせます.
あるブロックというものを番目のブロックとしておきましょう.
このブロックのコストが合算されるときは, ある番目のブロックを抜いたときの, 次のような場合のときです.
番目のブロックを取り除くとき.
番目(
)のブロックを取り除いたとき,
~
)のブロックを取り除いたとき,
~
以上の3つの場合があります.
それぞれの場合が, どれだけに含まれているかを考察します.
まず, 1の場合を考えてみましょう.
この場合は簡単で, どの取り除き方にしても 最終的にすべてのブロックを取り除くことになるため, 通りの場合が存在することがわかります.
2の場合を考えてみましょう.
ある番目のブロックを取り除いたとき,
番目までブロックが取り除かれていない, ということは『
番目から
番目までのブロックの中で, はじめて取り除くのが
番目のブロックである』ということと同値です.
そこで,
『通りある取り除き方のうち,
〜
までの
個のブロックの中で初めて取り除くのが
番目のブロックである場合の数はいくつか？』を考えることができます.
取り除き方が一様であることを加味すると, この場合の数はとなることがわかります.
言い方を変えると, 『通りある取り除き方のうち,
〜
までの
個のブロックの中で初めて取り除くのが
番目のブロックである取り除き方の割合は
である.』とも言えます.(公式ではそのような解説でした.)
2がわかると3も同様で, こちらも場合の数はとなります.
以上により, 各について1,2,3を合算すると
の解法を得ることができます. 具体的には, ある
について,
を
まで回してブロックの足される回数を数えたあと,
を掛けあわせ, 答えに足し合わせる, ということします.
計算をする際は, フェルマーの小定理で逆元を計算して掛け算をしましょう.
を
にするには, ブロックの足される回数の割合が規則的であること(単純に分母が1ずつ減ったり増えたりしています)を利用して,
でブロックの足される回数を数えることができるように逆元の累積和(
)を取っておけばよいです.
答えはMODをとっているので, あくまで逆元の累積和であることに注意してください (割り算を掛け算で実装する必要があります. )
感想
えーおもいつかない
数え上げの問題で割合を利用するってのは新鮮ですね
座標圧縮を学んだ(情オリ2008 ペンキEを解きました)
問題から
解法
まず, 与えられる座標がグリッドマスの座標ではなく, 座標平面上の格子点の座標であることに注意しましょう. これをグリッドのマスに変換するためには,
長方形左下の座標・・・そのまま
長方形右上の座標・・・それぞれ-1
をする必要があります.
ここから本題で, 制約をみるととても二次元配列にお絵かきをすることはできそうにありません.
そこで, 与えられる長方形の数が小さいことを利用します. 長方形の端点の座標さえわかっていれば, その他の何もない場所を省くことができます.
そこで, まずx方向について,
- 長方形の左端とその左側の縦軸
- 長方形の右端とその右側の縦軸
これを記憶しておけば, 情報としては十分になります. y座標については
- 長方形の上端とその上側の横軸
- 長方形の下端とその下側の横軸
を記憶しておけば十分です.
また, 盤面の端点も記憶しておく必要があります.
このようにしてまず, 圧縮の際に残す軸を決定します.
これをvectorにいれてソートし, 重複を除きます.
ソートするというのがポイントで, この座標圧縮において, この時点で長方形の各点の座標の位置関係（大小関係）は保存されます.
この大小関係の保存を利用して, 記憶したvectorから,
座標圧縮後の長方形の各端点の座標を復元することができます.
これをx,y座標それぞれにおいて実行すると, あとは連結成分の数え上げの問題となるので, DFSをすると答えが得られます.
それでもなかなかグリッドは大きいので, imos法などを使ってグリッドを埋めると時間的には安全です.
提出
Submission #3440558 - 第７回日本情報オリンピック 本選（オンライン） | AtCoder
(再帰だとMLEしそうだと思って再帰を使わずに書いたらqueueに突っ込んでいて, BFSしちゃってます)
感想
昔蟻本で読んだときはソースコードの意味がわからなかったんですけど, 今読むとわかって成長を感じました.
AtCoderのレートが水色になるまでにやったこと
水色になったので自分語りをしたくなりました.
自分にとってはそこそこの到達点なのでここでだけはいろいろ言わせてください().
はじめてのコンテストのおもひで
2018/06/16に初めてのコンテストは30分ぐらい遅れての参加だったことを覚えてます.
Twitterやってたら今日やってんだ〜と思って参加しました. プログラミングが趣味でB2のときにたまーにAtCoderの問題を見ていたのでIDは持っていました. そのときはアルゴリズムのアの字も知りませんでしたが.
B問題のコーナーケースが通らずA,Cの2完という微妙な結果でした.
このときに大学の講義でアルゴリズムについてやっていたので, ある程度勉強すれば競プロもできるかもしれないと思い, 本格的に勉強をはじめました.
そのときに, ぼくの競プロは始まりました.
今までのレート
競プロを始めてから今に至るまで, 時系列順に成績を振り返ってみます.
(右下の時計君の自己主張はゆるしてください)
6月半ばに競プロをはじめ, 3回目のコンテストで茶色(2018/07/01)になり, 6回目のコンテストで緑色(2018/07/21)になっています. そこからさらに7回のratedコンテストを重ね, 水色(2018/10/13)となっています.
ここで, 過去のAtCoder過去問埋め精進記録を見てみましょう. 
軸がおおざっぱですが, 夏休み中の8月に猿のように精進を重ねていたことがわかります.
しかし, 実を言うと8月辺りで猿精進を重ねた後のコンテストの成績はあまり良くなかったです. ABC105とABC106, ARC102辺りではC問題が解けていなかったり, パフォが伸びなかったりで, (ABC105は運良く(?)unratedになりましたが...)正直メンタル的にだいぶ厳しかったです. グラフを見てみても, この辺で停滞してる感じです.
しかし, 来る9月中頃, 予定も立て込んでいて精進もできていなかったのですが, ABC110で初めて上限パフォを出すことができました(これは運悪くunratedになりました). おそらく, この辺りでやっと8月中の精進が効いてきたのかなと思います.
精進の効果が現れるのには時間がかかることを意識するのは個人的に重要だと思っていて, 成果がでなくてもしゃーないかーとか思いながら気楽にできる点が精神にいいと思います.
ABC112では, WAを重ね続けてしまってパフォは微妙なものの全完を成したので, なかなか成長を感じました.
そしてAGC028のA早解きで青パフォを出して水色になりました(ABCで1600出してなりたかった気もします.)
水色になるまでにやったこと
本題です.
その前に, 自分の経歴(?)を紹介しておきます.
わたし
- 競プロ開始時点で地方旧帝情報系学部のB3
- 講義や趣味で軽いプログラミング経験あり(Haskell(趣味), C(講義でよく使ってる) , SML(講義でちょっとやった), Python(Twiterのbot作ったぐらい))
- 微妙な高校を出ていて, 特に数学やら算数が得意でもなんでもない
- 中古のPC屋で15kのThinkPadにubuntuを突っ込んで環境を整えたもので競プロをやっています(emacs使い)
特に, いつでも気軽に起動できるノートPCがあって, ubuntuでCtrl + Alt + Tでいつでもターミナルが開けて, コマンドちょちょいと打つとコンパイルできたりemacsが開けるというのがだいぶ大きかったように感じます. ものぐさで, ささっとできるものでないと続かないんです.
CをやっていたのでC++もすんなりわかったような気がします（わからない）.
隙あらば自分語りをしてしまいました. この辺を前提にして読んでください.
蟻本
競プロを始めるとともに, amazonでポチりました. しかし, 新品が高かったので第1版の中古を買ってしまったんですね. この前本屋に行って蟻本を見かけたら, 第2版というものがそこそこ厚くて驚きました... 幾何やらなんやらの追加コンテンツができていたみたいですね. うーん安物買の銭失い...
蟻本でやったこと
やった項目は
2-1 すべての基本"全探索"
2-2 猪突猛進！"貪欲法"
2-3 値を覚えて再利用"動的計画法"
2-4 データを工夫して記憶する"データ構造"
2-5 あれもこれも実は"グラフ"
3-1 数学的な問題を解くコツ
3-2 値の検索だけじゃない！"二分探索"
3-3 厳選！頻出テクニック(1)
は一通りはやりました.
蟻本はぶっちゃけわかりにくいです. わかりにくいんですが, 競プロの問題がテクニック別にカテゴライズされているので, テクニックの辞書として使えます. コンテスト中に詰まったらとりあえずペラペラして使えそうなものないかなーって探すこともできるので, 持っておいて損はないです.
蟻本がわかりづらいと感じたら, けんちょんさんのQiitaのAtCoder蟻本（大変お世話になっています）とか見てみるといいと思います. いい問題がたくさん集まっていて, 解説もネットの海を探せばいろいろあります.
蟻本に関しては以上です.
yukicoder 埋め
8月の終わりぐらいにyukicoderをやり始めました. AtCoderとは毛色の違う問題が多いですが, 解くのが面白い問題が非常に多いです. 緑のときは★2 , または★2.5ぐらいを埋めていました.
AtCoder過去問埋め
こんな進捗です.
D問題がわりかしたくさん埋まっていますが, 水色を目指すのならC問題を埋めたほうがよかったかなーと思います.
コンテスト中にDが解けずとも, Cの早解きでパフォが十分とれることがかなりありました.
ABC-C埋めが終わったらARC-A埋めもいいと思います. A,B問題が埋まっていませんが, やってもいいと思います. 虚無埋めなどと言われてますが, ACとれるのは楽しいですからね.
過去問を解くときは, 20分ぐらい考えてわからなかったら解説を見る, の繰り返しです. そして, 重要な問題だと感じたら記事を書く... という感じです.
こういう過去問埋めのときに知らないテクニックが解説に出てくると萎えるので, 埋める前に蟻本（中級までで簡単なところ）をやっておくことをおすすめします.
ブログ
あなたが見てくださっているこれです.
解説ブログを書くと, 意外と自分理解してないなーとか思うことがよくあって, いろいろ発見があります. 解法の言語化っていうのは大事だと思います.
8月の終わりぐらいだったか競プロ垢を作りました. 強い人やレートが同じぐらいの人をフォローすると, 憧れやら, 自分もがんばんなきゃなーと思ってがんばれます. あと, コンテストの情報が入ってきたり, 新鮮な解法情報がコンテスト後に流れ込んでくるので, 作っといてよかったと思います.
これからの目標
とりあえず青を目指してがんばりたいです.
まずは蟻本を進めて, セグメントツリーなるものをがんばって作りたいです.
まだまだこれからですね.
