読書記録
7月
- 20日
天久鷹央の推理カルテⅤ - 22日
エロマンガ先生7 アニメで始まる同棲生活 - 23日
エロマンガ先生8 和泉マサムネの休日 - 24日
エロマンガ先生9 紗霧の新婚生活 - 25日
エロマンガ先生10 千寿ムラマサと恋の文化祭 - 29日
お隣の天使様にいつの間にか駄目人間にされていた件5 - 30日
エロマンガ先生11 妹たちのパジャマパーティ
エロマンガ先生12 山田エルフちゃん逆転勝利の巻
8月
- 2日
甦る殺人者 天久鷹央の事件カルテ - 3日
火焰の凶器 天久鷹央の事件カルテ - 6日
魔弾の射手 天久鷹央の事件カルテ - 16日
神話の密室 天久鷹央の事件カルテ - 18日
亡羊の嘆 鬼籍通覧 - 24日
池魚の殃 鬼籍通覧 - 28日
幼馴染みが絶対に負けないラブコメ 8
9月
- 8日
三角の距離は限りないゼロ7 - 14日
俺の妹がこんなに可愛いわけがない17 加奈子if - 21日
りゅうおうのおしごと！15
10月
- 3日
久遠の檻 天久鷹央の事件カルテ - 5日
南柯の夢 鬼籍通覧 - 8日
天使の囀り
11月
- 1日
月とライカと吸血姫 - 28日
変人のサラダボウル
AtCoder Heuristic Contest 001参加記
真面目にマラソンに取り組むのは初めてでしたが、やってみると結構楽しいですね。 留年が決まって何もする気が起きず、とにかく暇だったので集中して取り組めました。 留年の話は気が向いたら書きます。
先日開催されたAHC001に参加し、最終スコア989,360,207,620点、順位は32位でした。 コンテスト中に考えていたこと、やったことをだいたい時系列順に書いていきます。
問題概要
やったこと
まずは正の得点を得る（823,090 点）
大事です。
入出力形式を理解できているかの確認は重要なので、簡単な解で試します。 ちなみに私は、初回の提出で配列の長さが足りずにREを出しました。
愚直に埋めてみる（41,047,354,846 点）
入出力形式の確認ができたので、スコアを伸ばすことを考えます。
スコアが大きくなるように広告を大きくする、という操作を広告一つずつに対して行いました。
山登り
愚直解を初期解として、これを改善してスコアを伸ばしていきます。
近傍の取り方
大きな方針としては、「単純な近傍を何万回でも回して、良い近傍を引くまで待つ。無理に賢い近傍は考えない。」ということを念頭に置いていました。 下手に賢い近傍を試そうとすると、実装が複雑になりがちで、大変バグりやすいので、これでもし「スコアが改善しませんでした」とでもなるとモチベに関わります。
近傍ではスコアが大きくなっていることが望ましい（はず）です。 周りの広告を縮小して広告を拡大することによってスコアが改善する場合、一度スコアの悪い状態を経由しなければいけないことになります。 これは嬉しくないので「縮小したら周りの広告を拡大」をワンセットで近傍とします。
近傍その1（48,464,922,569 点）
- 広告を一つ、1辺選んでランダムな幅で縮小させる。
- 周りの広告を愚直に拡大する。
- 最初に縮小した広告を愚直に拡大する。
スコア遷移を見てみると、ほとんど頭打ちになっているのが確認できたので、焼きなまし法に移行することにしました。
焼きなまし（48,493,434,096 点）
人生で初めて焼きなまし法を書きました。
スコアは改善しませんでした（悲しいね）。 とりあえず近傍を大きくすることにしました。
近傍その2（49,384,176,962 点）
- 広告を一つ選んで、その広告とその広告に接する広告を最小化する。
- 最初に縮小した広告を愚直に拡大する。
- 周りの広告を愚直に拡大する。
これはかなり効きました。 スコアが低い広告ほど優先的に、また温度が高いときにこの近傍を取りやすいように設定しました。
近傍その3（49,483,045,560 点）
- 広告を一つ選んで、その広告とその広告に接する広告の全ての辺をランダムな幅で縮小させる。
- 最初に縮小した広告を愚直に拡大する。
- 周りの広告を愚直に拡大する。
近傍その2とほとんど同じですが、494億点台に安定して乗るようになったので多少の効果はあったと思います。
これ以降はアイデアが無かったのでちょこちょこパラメータ調整をして最終提出としました。
高速化
焼きなまし法は試行回数が重要らしいので、高速化も多少行いました。
拡大する時は大きい幅から試す
最大で幅だけ拡大したいときは、
というように
ずつにしながら試します。
この高速化は結構効いた気がします。
重なる可能性のある広告のリストアップ
現在の大きさから最大で幅だけ拡大する、というように拡大するときの幅を制限しておきます。
ここで、幅
拡大したときに重なる広告を事前に調べておきます。
こうすることで、広告を拡大する時に重複判定をする広告を減らすことができます。
ただ、これはあんまり速くならなかったです。
隣接する広告のリストアップ
ある広告を縮小したときに、拡大できるようになる広告は隣接していた広告（のみ？）です。 事前に広告同士の隣接関係をリストにしておきます。
隣接する広告の数は一つ当たり平均で3個程度だったのでやった方がいいと思います。 そこそこ速くなります。
スコア計算
差分だけを計算するようにしましょう。 今回の問題だと比較的簡単にできて有効な高速化だと思います。
最後に
真面目にマラソンに取り組むのは初めてでしたが（2回目）、9日間飽きずに楽しめました。 あまり難しい事はできませんでしたが、そこそこのスコアが出てくれたのでよかったです。 最後の2日はパラメータをガチャガチャしてましたが、最初以外スコアが伸びずほとんど無駄な時間でした。
また、今回はkenkooooさんのビジュアライザに頼り切りだったので、次回からは何とかしたいですね。 次回は短時間のコンテストになると思うので、効率的な分析の方法をしっかり用意しておきたいです。
第二回全国統一プログラミング王決定戦参加記
第二回全国統一プログラミング王決定戦本選に参加してきました！
予選
A:はい
B:まあ、はい
C:これ本当に難しい。DE解いた後に考えたけど無理だった。
D:遅延セグ木で殴れそうなので殴ります→AC
E:小さい方から個の和が大きい方から
個の和より小さい、というのが明らかに必要条件。どうせこれが十分条件でしょ、と適当な直観を信じて実装→AC
ABDEの4完で157位でした。 まあまあ余裕で予選通過しました。
当日
遅刻しました（は？？？）
日経コン遅刻しない？遅刻だね
— 濃い紅茶 (@koi_kotya) 2019年12月15日
コンテスト開始2分前くらいに会場に到着。 Wi-Fiの接続あれこれは間に合いませんでした。
ぞい！（遅刻）
— 濃い紅茶 (@koi_kotya) 2019年12月15日
そんなこんなで数十秒遅れでコンテストに参加しました。
本選
A:
わたわたしながら問題を読みます。
真ん中を固定して考えるとで解けそう。
→AC
B:
上位互換をこれで見た。
atcoder.jp
IKを固定すると残りの部分の分け方が全部決まると気づく。
Z-Algorithmで前処理すると判定はでできそう。
IKの全探索はでできるので、解けます。
C:
とりあえず前処理として、上下右下に何個連続して黒マスがあるかを調べておく。
Nの左上の点を固定して、構成できる最大のNがくらいで分かれば解けそう。
斜めに見たときに直線状に並ぶ各点について、(上に連続する黒マスの数)-(列のindex)をセグ木に乗せる。 セグ木上で二分探索を行って、条件を満たす最大値を求める。
計算量はで間に合うはず！と信じて実装するも実装のバグが取れずWAのままコンテストが終了……。
解法のお気持ちは公式解説とほぼ同じだと思います。
（ACコード）
ABの2完で128位でした。 Cが通せなかったことが悔しい。
懇親会など
- 今まで会ったことのある人には大体挨拶して回れたと思う。懇親会に参加するのも数回目なので懇親ムーブが多少上手くなってるのを実感した。
- FFの人に話しかけられたけど全く認知してなかった。申し訳ねえ。
Brainf*ckにおける非破壊if文と呼ばれるテクについて
この記事はBrainf*ck Advent Calendar 2019 12日目の記事です。
「非破壊if文」のお気持ち
そもそもif文って？
多分こんなやつのことです。
[**ifの処理**[-]]
ここで重要なのは、対応する[と]でポインタの位置を同じにしておくことです。
でないと、if文の処理を行ったときと、そうでないときでポインタの位置が異なる、といった事態になります。
これの帳尻を合わせるのは面倒なので、対応する[と]でポインタの位置は合わせておくことが基本だと思います。
よって、全ての処理が終わった後で、条件分岐に使われたセルの値は必ず0になっていることがコードより分かります。
でも、これだと条件分岐に使ったセルの値を再利用したい場合に困ってしまいます。
ナイーブな解決策
セルの値を事前にコピーしておくだけでいいです。 ほとんどの場合、これで済むと思います。
ただ、あるセルの値が0か否かを調べるためだけにセルの値をコピーするのは大袈裟な気がします。
また、（処理系による最適化が無ければ、）コピーする分の実行時間がかさむという欠点もあります。
非破壊if文を使う
さて、この問題を解決するのが非破壊if文です。 読んで字の如く、条件分岐に使うセルの値をコピーも破壊もせずにif文を書くテクニックです。
実はこのテクに関しては、分かりやすい記事がいくつかあるので、本記事ではいくつか例を挙げてお茶を濁そうと思います。
実装例
以下のいずれの方法でもメモリの配置は次のようになっています。
{x}{0}{0}
ポインタは0番地にある状態からスタートし、0番地の値xで条件分岐します。
1,2番地は0で初期化されています。
方法1
[>>+<**ifの処理**] >[<]>- [+**elseの処理**]
私がよく使うのはこれです。 後に示す方法の方が優れていそうですが、手に馴染んでいるのでこの方法を使っています。
方法2
>>+<< [>**ifの処理**] >[<]<
elseの場合の処理も入れようと思えば入ると思います。
参考：brainfuck 入門：非破壊 if - 三流プログラマの戯言
方法3
>+< [>-**ifの処理**]> [->**elseの処理**]
個人的にはこの方法が一番無駄がないと思います。
参考：Brainf**k講座(6) 非破壊的条件分岐 - ange1のブログ
まとめ
ほとんど役に立つことのないテクですが、プログラムを高速化したい、コードを短くしたいときには覚えておいて損のないテクだと思います。
2019年の目標
AtCoder黄色になる
簡単ではないけどギリギリ現実的な目標だと思う。 黄perfはなかなか出ないので自分の地力の限界が青なんだなあと感じる。 冷えることも多い一年になりそうだけどめげずに地力を伸ばしていきたい。
オンサイトコンテストに出る
去年はCODE THANKS FESTIVAL 2018に参加できた。 当時はまだ競プロ初めて半年くらいだったので参加できただけでもとても嬉しかった。 ただパーカーを得られなかったのは本当に悔しいので、今年こそは（開催されれば）CODE FESTIVALの方に参加してパーカーを得たい。
2019年はTシャツ3着くらいは欲しいなあ。
毎日新規ACを取る
AtCoder Problemsで確認できるCurrent Streakが180日を越えたのでこれを切らさないようにしたい。 毎日自分の実力にあった問題を解くのは重いけどできるだけ虚無埋めをしないようにする。
チーム参加可能なコンテストに誰かと一緒に出る
誰か一緒に出てくれる優しい人を探しています。
早寝早起きをする
競プロをすると生活習慣が破滅しがちなので健康的な生活を心がけたい。 コンテスト終わった後にTwitterを1時間くらい見てることが多いのでそれを止める。 Codeforcesには無理して出ない、出る前に仮眠をとるなどの対策をしたい。
早朝のゴリラジにもできるだけ出る。 最近は寒くて起床が難しいので休みがちだった。 あと早起きできる自信がついたので朝にタスクを後回しにしていたせいで出られないことも結構多かった。
労働をする
無職なので。 ぬるま湯で養殖されているので現状お金には困っていないけど、無職でいるのも落ち着かなくなってきた。
競プロしかできないけど誰か雇ってください。 三食昼寝付きがいいです。
駅メモとか
称号「確かに感じるアサとの絆」を取得する（あとお仕事12000回くらい）。 北海道を再履修する。 どっかの都道府県のマスオブ称号を取得する。
相変わらず適当なプレイスタイルですが、ご近所の皆様どうぞ今年もよろしくお願いします。
愛着の無い名前をどうにかする
濃い紅茶って誰ですか。
Brainf*ckを書かない
無限に時間が溶けるので。
AtCoderで青になるまでにやったこと
AGC029で青コーダーになりました！
わーい。
始めて1年以内に水色になれればいいかな、くらいの気持ちで始めたのでここまで到達できて正直驚いています。
「AtCoderで青になるまでにやったこと」というタイトルで自分語りがしたかったので、競プロを始めてから青になるまでを振り返りたいと思います。
AtCoderを始めたきっかけ
駅メモという位置ゲーを知っていますか？ 私は知っています。 競プロを始めたのはこのゲームを効率的に攻略する方法を探るするためだったりします。 もっとも、競プロが楽しすぎたので駅メモの攻略はもう割とどうでもよくなってます。
大学の講義でほんの少しだけRubyを触ったことがあったので、プログラミングに対してあまり抵抗はありませんでした。 青になるまで、AtCoderのコンテスト中に通した問題はほとんどRubyで書きました。
水色まで
水色までは2ヶ月で割とすんなりなれたので、プログラミング以外の地力は緑くらいあったんだと思います。
水色になった時点で総AC数は300強、ABCのCD問題を中心に埋めていました。 使った知識は全探索、累積和、UnionFindくらいだったと思います。始めてからずっと水色目指して頑張ってきたので今本当に嬉しい pic.twitter.com/Aexd0Cm7To
— 濃い紅茶 (@koi_kotya) 2018年5月20日
ここまでの使用言語は全てRubyです。 Rubyで実行時間が厳しい問題はそもそも考察が無理だったので、水色適正の実力ならRubyでも普通に戦えるかなと思います。
水色から青
青になった時点で総AC数は750くらい、ABCのCD問題埋めや、400~500点問題埋めを中心にしていました。
初期のABCは結構難しめの問題があるのであんまり埋まってないですね。
企業コンの400~500は詐称が多いので埋めてないのがいくつかあります。
ARCのC問題やAGCのA問題を早解きできるとレートが上がることが多いので、このくらいの難易度の問題に慣れていたことはよかったと思っています。 500点以上の難しめの問題も、コンテスト中に通せるとレートが上がって嬉しいです。 難しめの問題をハマってでも通しきる力も大事なのかな、と思います。
また、水色になるとratedなコンテストが減るので、モチベの維持のために他の人が立てたバチャやCodefoces、LeetCodeのコンテストに出るようになりました。 Codefocesに出ると生活習慣が壊れます。 気をつけましょう。
実行時間制限の厳しさを感じていたのでC++の勉強も始めました。 結局C++をコンテスト中に使う事はほとんどありませんでしたが、実行時間お祈りゲーになるよりはマシなので勉強しておいてよかったと思います。 青になるまでならRubyでも割とどうにかなります。 ですが、流石に実行時間の厳しさを感じるので、上を目指すには速い言語が必要だなあと感じています。
これからの事とか
ここまでは大きな冷えや停滞をすること無く結構順調に来られたんじゃないかな、と思っています。 ただ、黄パフォ以上はなかなか出ないので青とは長い付き合いになりそうだなあという気がしています。 水色から青になるまでは7ヶ月、青から黄色までは何ヶ月掛かるか見当もつきませんが、つべこべ言わず精進していきたいと思います。
いつか黄色になりました記事も書けるといいなあ。
CODE THANKS FESTIVAL 2018 参加記
CODE THANKS FESTIVAL 2018に参加してきました。
予選
予選Aは不参加で、予選Bは136位でした。 当時は微妙かと思いましたが、そこそこ余裕で通ってたみたいです
本戦
11:30からの開会式の後、昼食のお弁当を受け取りました。 のんびりお弁当を食べてたら、12:00からの本戦が始まりそうだったので昼食を切り上げて問題を解き始めました。 パーカーは上位50人だそうです。
A - Two Problems
えーこれ難しくないですか、と思いながら適当にif文を書きました。 この時点で3分溶かしてしまい非常に厳しい気持ちになりました。
B - Colored Balls
一度見てよく分からなかったのでDを解いた後に手を着けました。 それっぽく条件分岐をしてやったら通りました。 この問題で20分溶かし、これ本当に200点か？と思うなどしました。 randを使っても通るらしいです。
C - Pair Distance
一度見てよく分からなかったのでBの後に手を着けました。 ソートして累積和を使えば解けるとすぐ気付けたので5分で片付けられました。 よく考えてみれば累積和使わなくてもシンプルに解けましたねこれ……。
D - Concatenation
Aの次に簡単な問題だったと思います。 先頭から貪欲に見ていくだけですね。
E - Union
問題文の読解が難しかったです。 制約と剰余を取る計算が必要である事からDPだとエスパーしました。
dp[i][j] = 整数iまで見たときにiがj個余る通り数
とまでは検討がついたのですが……残りの2時間半近くは椅子を暖めることだけをしました（悲しいね）。
dpの遷移をバグらせまくったのはもちろんなんですが、計算量が見えてなかったために、複雑に考えてしまったのが本当に痛かったです。 jが高々600で抑えられることはちょっと考えれば分かったはずなんですけどね……。 そのせいで累積和を使って高速にならないかなあ、などということを延々とやってました。
結果
ABCDの4完86位でした。
流石に苦手セットだったと思いたいです。
懇親会
connection bingoという自分の好きな言語やアルゴリズムなどが同じ人を探すイベントがあったので、前半は適当に他の人と話しながらビンゴを埋めつつ料理をつまんでました。 ビンゴを一列埋めた人先着30名が景品としてレポートパッドが貰えたらしいです。 これパーカーを得るより難しくないですか。
それからけんしょーさんからAtCoderステッカーを頂きました！ 初めてTwitterで見たときから欲しかったので本当に嬉しかったです。
後半は余った料理に手をつけつつ、他の方と競プロトークをするなどしました。 ちゃんと懇親できたので偉かった(?)と思います。
感想とか
パーカーを得られなかった事が本当に悔しい！ オープン参加したCODE FESTIVAL 2018ではパーカー基準超えたのでいけると思ったんですけど、惜しいところまでもいけませんでした。 まだ来年も出られるので、今度は余裕で予選突破して次こそはパーカーをゲットしたいと思います。
それから、青coderも黄coderも一応人間の外見を取っているんだなあということが分かったので、私も早く青になれるように頑張りたいです。
