10/26(月)
先週の週記を投稿した後布団に入り、そのまま6時間ハーメルンを読んでいた。
かなり面白い。面白いんだけど、あからさまな謎を残したままエタっていて精神が持たない。ダリアの歌わない魔法のエタり方よりはマシだけど、つらい。
ハリポタの原作を読んだのは相当昔の話なので、もう全然覚えておらず、二次創作から補完してしまっている。前半の出来事はたいていそのまま描かれるが、後半になってからオリ主の介入だったり性格改変だったりで全然違う枝分かれをする。まあそれを求めるのが二次創作といえばそうなのだが。この作品はもう全然分霊箱が見つからなくてびっくりした。原作もこんなもんだっけ……?大抵の二次創作ではあっさり見つかってるので、原作もそんなものだったと錯覚していたが、よく考えたらハリーは7年生の時はずっと探しっぱなしだったかもしれない。少なくともこの作品ではそういう描かれ方をしていて、そういえばそうだったかもといった気持ちになっている。
別の作品を読み始める。
東方project × ONE PIECE ~狂気の吸血鬼と鮮血の記憶~ - ハーメルン
20話ほど読んだところで眠気に耐え切れなくなり、寝落ちしたらしい。閲覧履歴から時刻を復元したところ、午前11時だった。
起きたら午後9時だったらしい。10/26は(すでに日時の感覚を失っている)AtCoderをプレイしていないので、スマホからちまちま提出する。その後再度ハーメルンに戻る。なろうの更新を確認して読んだりしていると、日付が変わった。
atgolferを確認したら久しぶりにやられたという感じの最短コード更新があったので、載せる。
N
とM
が与えられる。M<=N
である。1
以上N
以下の数であって、M
でないものを1つ出力せよという問題。M
から1ずらすことを考えると、M%N+1
という式が得られる。以前まではこれが最短だった。
普段は1
を出力することにして、M==1
の時だけ別の数を出力する、ということを考える。これはdc
のR
コマンドを用いると非常に簡潔に書くことができるようだ。スタックに1 N
と積んでおいて、M
でR
すると、M>1
のときは一番下の1
が先頭に来る。M==1
の時だけ一番下まで遡らずN
が先頭に来る。これで、先ほど述べた場合分けができている。
1?Rp
だ。シンプル。僕が達成していたら文句なく美しいと褒めちぎっていたが、僕のコードではないため嫉妬で言葉が出ない。
10/27の13時でリクルートの冬アルバイトのエントリーシート締め切りだ。あと10時間しかないが、1文字も書いていない。
もし向こうが競プロerに興味があるなら、僕をエントリーシートで落とす理由はないと思う。自尊心。
「自分がこれまでしてきた取り組みのうち最も成果を挙げたもの」には何を書くか、ということは最初にエントリーシートを確認した時から考えていた。結局TLのある人のツイートを受けてコードゴルフについてを書くことにする。実際に書くのは明日に回す。
昨日読み始めたハーメルンを読み終えた。いわゆる超古代スタートで、そこそこイベントを書きながら50話弱かけてようやく原作キャラが出現し始めたところでエタっている。儚い。
ほかのハーメルンをいくつか漁りつつ、5時半くらいに寝落ちしたようだ。Webページの閲覧履歴から復元。
10/27(火)
午前8時、起きる。全然寝てない。が、エントリーシートの締め切りが迫っているため、起きる。書き始める。
似たようなページに入力したときの経験から、エントリーシートのページを開いてから送信するまでに時間制限があることが予想されるため、いったん長文回答の設問を抜き出してメモ帳で推敲する。
ところでデータを扱う知識・経験の有無を問われていたが、一切ないことに気づいた。この辺りは僕の自己肯定感に結構効いてきて、いやな気持になった。開き直って全部なしと書いたら少し楽になった。
アルゴリズム系エンジニアを希望する理由、自分が競プロやってるから以外にあるか?
— こたつがめ (@kotatsugame_t) 2020年10月27日
— こたつがめ (@kotatsugame_t) 2020年10月27日
これまでに最も成果を出した取り組み
— こたつがめ (@kotatsugame_t) 2020年10月27日
プログラミングコンテストサイトAtCoderにおける問題ごとの最短コードを1300個以上保持し全アカウント中1位になる
これで勝負かけていきます
おおむねこんな感じのツイートをしていたところ、助言をもらった。
ちゃんと
— Nキチ (@freude111) 2020年10月27日
・広範な言語仕様知識を持ち、使いこなす実力を有する
・仕様を詳しく調べるノウハウを持つ
・難解なコードを読み解くことに慣れている
・計算機の挙動を熟知している
・1位を取る強い精神性、執念を持っている
・その上で上位競プロerとしての能力も持つ
みたいな具体的アピに繋げるんだぞ
こう書かれるとコードゴルフってすごいなとなる。個人的な印象としてはかなり的確で、大体間違っていないと思う。
寝ても覚めてもコードゴルフやってるんだし、これくらい自分のことを褒めちぎってもいいかなという気持ちになった。かけた時間だけその技術に対する信頼が生まれる。根拠のある自信に思えて、心強い。
書きはじめた頃は結構微妙な気分になって出すかどうか迷っていたのだが、以前にも書いたように、こういうのは一度やってみないことには何も始まらないと思っており、このことを強く念じることで、文面を完成させることができた。
午前11時ごろ、リクルートの方からSMSが来て、期限間近であることをお知らせされた。入力の最中であると返信を送る。説明会に参加した人全員に送っているのだろうが、なんとなく気が楽になる。ちょろい人間である。
いくらか文字数をオーバーしてしまったが、なんとか削減し、提出した。すぐにコーディングテストがあると思っていたが、これは別のコースに応募する場合の話だった。僕が応募したコースは、面接に進んだ人のみがテストを受ける。
beetさんのなろうオススメまとめ、かなり参考になるんだけど、普段読んでるものから厳選してるんだろうなと感じたので、ブックマークが全部見たいとツイートした。学食に行って帰ってきたら、はてなブログに投稿されていた。
僕もやる。
JavaScript
を調べながら書いたのでかなり疲れた。布団に入ってゴロゴロしていたが、20時くらいに寝落ちしてしまった。
10/28(水)
深夜、起きる。また寝落ちしてしまったことに絶望しつつ、ハーメルンを読む。午前4時半くらいにまた寝落ちしてしまう。次に起きたのは午前9時のようだ。
スマホアプリのGmailのアイコンが新しいものに変わっていた。目新しくて面白い。目新しくなくなった場合どうなるかは知らない。ほかのアプリと並べたときの視認性が悪いというツイートはよく見る。
細切れで微妙な睡眠しかしていないため、布団から起き上がる気力がわかない。しかし競技プログラミングはしたいため、布団でノーパソを開いた。
AOJ-ICPCから「論理式圧縮機」と「リボンたたみ」を解いた。論理式圧縮機は解法っぽいものは一瞬で見えたが計算量がちょっとヤバそう。多分2^16*2^16
くらいのステップ数があると思うのだが、実装してみたところ手元実行でも6sec
だったので提出した。
リボンたたみは、確か昨年の国内予選の直前に肩慣らしとして解こうとしてあきらめた問題だ。今見たら結構すんなり解けた。与えられた情報から素直に計算できるものを元に考察したところ、上手くいった。
まず、上から何番目にあるか?という情報から、i
回目の折り畳みで印をつけた部分が持ち上げられるか否かがわかる。
折りたたむ前に印をつけた部分が左半分にあるか、右半分にあるか、というのは、その部分が持ち上げられるか否かに応じてLR
を割り振ると決めることができる。最初にどこにあるかは入力で与えられているので、これを順に適用しながら場所を計算していくと、答えが得られる。
そろそろAOJ-ICPCの450点を埋めきろう。最後の1つ、「浮動小数点数」である。これは一昨年の国内予選で解けないまま今までずっと残っていたものだ。
他の人のツイートから結構ヒントは知っていて、覚えていた。それをもとに考えて、何となくわかってきたところで学食が閉まりかけたので、中断。
学食の味噌汁は最近非常にしょっぱい。人が来ないから水分が飛んでしまっているのかも。
生協で「扇物語」を見つけた。新刊なので買っておく。このシリーズは結構前の巻で読むのがストップしている。買い始めたころは中学生で、確か終物語が刊行されたくらいだったと思うが、そこから今まで一度も最新刊に追いついたことがない。
帰ってきて実装し、AC。これでAOJ-ICPCの450点以下はすべて埋まった。今解いてみたら割とあっさり解けたなと感じるが、まっさらな状態から考察を始めたわけではないので何とも言えない。
布団に転がってハーメルンを読んだりラノベを読んだりしていたら、ついにICPC国内予選の誓約書の情報が公式ページに書かれた。締め切りは……11/02!?あと6日しかない。助けてくれ。
誓約書はメールで来るようだが、僕のところには来ていない。TLを見ているとコーチに来ているらしいので、急いでSlackで連絡を取った。すぐに返信があって、誓約書となるGoogle formのリンクを共有してもらう。サークルのSlackに貼り付けて参加メンバーにメンションを飛ばした。
ICPC予選出場に関する誓約書をGoogle formで提出してください。締め切りは11/2(月)です。期限がかなり短いので、このメッセージを見たらすぐに提出してください。終わったらACのリアクションをしてください。
結構強めの言葉でお願いしたところ、すぐにいくつかリアクションがあった。うれしい。この日記を書いている今、すでに残り4名のところまで来ている。
AOJ-ICPCの500点問題をさらに1問解いて、120000ポイントを達成した。
10/29(木)
7時間半睡眠。完璧。王の睡眠。学校で学ぶちょうどよい睡眠時間は大体これくらいの気がするが、本当は足りないと思う。ちゃんと毎日9時間寝たい。別に予定があるとかではなくて、うっかり寝床でスマホを触ってしまい二度寝できなくなるのが原因。
朝、1冊本を読んだ。創元推理文庫「ヴァン・ショーをあなたに」。
途中で本を1冊読んだ。創元推理文庫「タルト・タタンの夢」で流し読み気味だが面白かった。シリーズもので続編があるらしく、把握していなかったので、とりあえず古本サイトで探してお気に入りに登録しておく。今度古本を注文する機会があれば一緒に買うだろう。
週記(2020/07/20-2020/07/26) - kotatsugameの日記
実は8/20に新刊で買っている。シリーズの3巻がちょうど文庫になったらしく、一緒に1・2巻も平積みされていたので、うっかり手に取って購入した。そのあと古本屋に行ったら2巻が安く売られていたのでちょっと残念な気持ちになった。(ここで嫌な気持ちになるのは、本読みとして良くなさそう。)
相変わらず流し読み気味だったし、相変わらず面白かった。ただ即座に3巻を読むかというと微妙。
12時くらいに学食に行く。普段より1時間早く、ちょうどお昼休みの時間帯だからか、びっくりするくらい人がたくさんいた。
多分AOJ-ICPCを埋めつつ布団に倒れこんでいたりしたと思う。途中でチラチラハーメルンを読んだりもした。特に何かを決めてずっとやっていたわけではないので、何とも書きにくい。
昨日Slackに投稿したICPCに関する誓約書は全員が回答したらしいので、そのことをコーチに報告した。1時間くらいして返信が帰ってきて、どうやらあるチームのうち1人が回答していないようだ。いや、回答していないのに投稿にACのリアクションをつけるのは意味不明だから、何か間違いがあったのだろうか。ともかく、チームの誰が間違っているかはわからないので、とりあえず3人にメンションを飛ばして確認をお願いしておく。
vector a
とvector b
のswap
について。a.swap(b)
と書くとO(1)
になることは知っているが、swap(a,b)
と書いたときにどうかを断言できない。ライブラリでswap(a,b)
と書いてある箇所があったので、念のためa.swap(b)
に直しておく。
https://t.co/kSN7cq7pxt
— 熨斗袋 (@noshi91) 2020年10月29日
定数時間です
了解!
うっかり午後8時に寝落ちしてしまい、起きたら午後11時半だった。TLを眺めているとまたすぐ寝落ちしたらしく、次に目が覚めると3時半だった。本当はもう一回二度寝するつもりだったが、結局しなかったので、ここで日記の日付も変わったことにしておく。
10/30(金)
朝から本を読んでいく。まず「わたしの幸せな結婚 四」。表紙イラストがいい。中身に関しては、かなり適当に読んでしまい、何も覚えていない。
次に「境界探偵モンストルム2」。昔イラストレーターの晩杯あきらさんが好きで、その人がイラストを担当したラノベを少し集めていたうちの1冊。シリーズ2巻だが、1巻はいつ読んだのかと読書記録を探ると、2018年3月だった。さすがに何も覚えていない。タイトルに探偵とあるが、ミステリ要素があるわけではない。足と人脈で情報を集めるタイプの探偵と言えばいいのか。
シリーズが続きそうな終わり方をしているが、シリーズ3巻は出ていない。そもそもこれを出版したノベルゼロというレーベル自体、1年半新刊が出ていない。ただまあシリーズ3巻が出るならその時間は十分にあったはずなので、やはり打ち切りだろう。
メールを確認したところ、急に12時半までのレポートが生えている。
週記(2020/10/12-2020/10/18) - kotatsugameの日記
これに関して、先週の金曜日は特に何も書かなかったが、2限の講義ではレポートが出なかった。今日はどうなるだろう、まだ出ていないが……と待ち構えていたのだが、どうやら今日は学祭の日で休講らしい。コロナウイルスで学祭も消えたので、虚無の日。別にコロナウイルスがなくても虚無の日だったと思う。
読んでいる最中、ついにHHKBが届いた。
— こたつがめ (@kotatsugame_t) 2020年10月30日
とりあえず箱を開いて、机に放置して学食に行く。休講なので営業時間がちょっと短い。
帰ってきてキーボードを使おうとするが、どうにもデスクトップPCとペアリングができない。調べてみたところ、PCにBluetoothの部品がついていないらしい。そう……。
とりあえずはUSBケーブルで接続するが、本当は別の用途で使うはずのケーブルなので、キーボード用に何かを買いたい。具体的にはUSB接続のBluetoothアダプタを買いたい。
6月あたりにAtCoderの何かのコンテストで手に入れたAmazonギフト券がまるまる残っているので、これを使おう。よくわからないけど1000円ぽっちのアダプタを買うだけで送料が無料になったので、余計なものを買おうとせず即座にレジに進み、購入。
キーボードの使い心地を試すため、つい先ほど追加された先日の模擬国内予選の問題を解いてみる。まずCtrl
とShift
の位置がこれまで使っていたものと逆になっており、かなり違和感がある。
プログラミングには関係ないが、半角/全角キーに相当するボタンが左下にあるのも結構つらい。キーを連打するときの感覚も微妙に違い(キーストロークが深くなった影響だろう)、cin>A
を連発してしまった。
まあせっかくお高いキーボードを手に入れたので、慣れるまで頑張ってみようと思う。寿司打をやってみたが、特に速くも遅くもならなかった。
禁忌「フォーオブアカインド」 pic.twitter.com/fTKrSInQNi
— こたつがめ (@kotatsugame_t) 2020年10月30日
もう1冊本を読んだ。「ブックマートの金狼」。これも前のものと同じノベルゼロというレーベルから出版された本で、しかもレーベルが創刊したときの1冊。だから何だという話だが。
著者は杉井光。この方の作品は「神様のメモ帳」と「生徒会探偵キリカ」を読んだことがあり、両方とても好き。この本も設定が好きなので買った。
裏社会のフィクサーが活躍する話結構好きなんだけど、どうしてもリンチされるシーンが挟まってそこだけ辛い
— こたつがめ (@kotatsugame_t) 2020年10月30日
「神様のメモ帳」も似た理由で好き。ほかには「池袋ウエストゲートパーク」というシリーズがある。そういえばIWGPはアニメ化している最中らしい。
今は「ブックマートの金狼」の話をしよう。確認してびっくりしたのだが、この本は表紙以外イラストがない。あとがきで「締め切りが過ぎてからプロットを作った」と書いてあったので、多分イラストを描いている時間がなかったのだろう。ほんとにラノベレーベルか?
ノベルゼロで画像検索するとわかるが、このレーベルは高めの年齢層をターゲットにしていたらしく、ラノベレーベルとしては異色の装丁がされていた。カバーは単色でかなり紙っぽく、大きめの帯が付属していて、表紙イラストはそこに印刷された。全部過去形。今はもうない。
読み終わってしばらくツイッターをしていたら、うっかり寝落ちして7時間も眠っていた。yukicoderに参加できなかった。
起きると、ICPCの誓約書を確認してもらうようメンションを飛ばしていた3人から確認したとの返答があった。僕もコーチからチームIDを教えてもらっていたのでチェックしたが、まだ直っていないようだ。考えられる原因としては、誰かがアカウント作成に使用したのと別のメールアドレスを書いているとかか。すでに深夜なので、この時間に返信するわけにはいかない。朝を待とう。
AOJ-ICPCを進める。550点を埋めていて、英語問題を優先的に解いている。英語問題は日本語問題より読解が面倒なので、先に手を付けておこうという魂胆だ。
サークルのメールをチェックすると、入部希望の方が2名いた。入部するのはいつでも大歓迎なのだが、最大のイベントであるICPCはちょうど参加登録を締め切ってしまったので、何ともタイミングが悪い。
朝を待って、誓約書に関することと入部のメール2件に返信した。
10/31(土)
昨日(というか今日の朝方)に布団に入ってから、ハーメルンを1作読んだ。
そんなことをしていたら昼ぐらいになってしまう。ICPCの誓約書は無事に全員が提出したことを確認できた。夕方に荷物が来る予定があるので、その時間に起きている必要がある。急いで寝ようとして、あんまり眠れずにTLを眺めていたら、ICPC国内予選のルールが大幅に変更されたらしく祭りになっていた。コピペ解禁!!!
かなり衝撃的。まあライブラリペタリすると解けてしまう、いわゆるやるだけ問題なんて出ないだろうし、ルール変更の前に問題は決定しているだろうから、問題の難易度的にはあんまり変わらないかな。
普段使いしているマクロをそのまま使用可能になったのも大きいだろう。それで大きく速度が変わるとは思っていないが。
午後1時に寝た。午後4時に目覚ましで起きる。午後4時から6時の間に荷物が到着する予定なので、うっすら意識を保っておきたい、と考えていたらすぐに来た。無事受け取れたので、安心して眠ることができる。ARCがあるので、それまで4時間くらいか?細切れの睡眠になってしまって辛い。
午後7時半に起きた。頑張って眠気を覚ます。部屋がとんでもなく寒い。今冬初めてエアコンを入れる。食事を摂る。コンテスト前にシャワーを浴びるか迷ったが、何となく止めておいた。別にジンクスとかはない。
ARC107が始まって、終わった。4完。Eの解説を読んだら、実験をしましょうと書いてあって、本当に絶望した。最近実験していない。
レートは17下がって2666→2649。明暗を分けたE問題の解法が実験エスパーだったので、精神がひどく傷ついた。放心状態で1時間くらい椅子に座っていた。
1と2をまとめて考えるとNANDになるので、その方向で頑張っていた。丁寧に観察した結果、おおむね0と1 or 2は交互に現れるが、たまに1 or 2が2連続する箇所があって、右下にずれていくことまでわかっていた。何のことはない、斜めに同じ数が出現していただけなのだ。
おおむね交互という点から、だいたい半分が0でもう半分が1となって、2は先ほど述べた1 or 2が2連続する箇所にしか現れないので、その分を引いておく、というような解法を投げていたが、全然通らなかった。冷静になるとそれはそうで、0と1は全然半々ではない。各行にどれだけ2が現れるかカウントして、あとは0と1のどちらが先に出現するかなど考えればできないこともなさそうだが、そこまで深く考える時間はなかった。
月曜日の講義のレポートを書いた。前回提出した課題からしばらく新しいものが出ておらず放置していたが、いつの間にかかなり進んでいてびっくりした。再履じゃなかったら死んでいた。
高級10,000円コース【普通】で、
— こたつがめ (@kotatsugame_t) 2020年10月31日
★11,080円分 お得でした!(速度:6.7key/秒、ミス:25key)
https://t.co/fueG45j1xr #寿司打
正確性に振ったほうが明らかに伸びるんだなあ みつを
できるだけミスしないように打ってみたら、初めて20000円を超えた。
ARCの問題を少しコードゴルフしていたら朝になってしまった。日曜日はチーム練をしたいのだが、まだ何も決まっていない。とりあえず練習できる時間に起床しなければ話にならない。
11/01(日)
昨日は布団に入ってからハーメルンをしっかり読んでしまって、寝たのは11時だった。日曜日の午後にチーム練をする予定だったが、何も決めずに寝た。
午後2時くらいに執念で起きる。チームメイトは僕がとんでもない時間に就寝しているのを見てゲームセンターに行っていたし、僕自身意識を保つのがつらいので、練習の時間を(ABCにかぶらないように)できるだけ後ろにずらすことにする。具体的には、午後5時から3時間ということにして、それまであと3時間眠る。
午後4時45分、起きる。30分の目覚ましでいったん意識を取り戻したが、二度寝しそうになったので、慌てて15分単位の目覚ましを再度かけなおした。
食事をしつつ練習内容を決める。今日は2017年の模擬国内のセットを解く。D以降を解いていなかったので、ちょうどよい。
ABCDFの5完だった。E問題は嫌だったので、手を付けていない。
僕はまずDを読んだ。よくわからないが、たぶん単調性があるので二分探索をする。X
がある値以下のとき条件を満たす、とするとWAだった。実際にはX=s_1
がありうる最小値で、これを下回ると敵が倒せなくて行動不能になるが、この部分は単調性から外れてしまう。二分探索の下限を修正してAC。
Cが難航しているようなので、先に僕もそれを読む。できるだけ速く4完を確保するための行動。特に問題なく通る。画面共有してコーディングを眺めていたのだけど、そこまではせずとも解法を伝えた段階で次の問題にとりかかってよかったかもしれない。
Eは嫌なのでFを読む。DAG
をパスに分解して、最大の重みを調べる。チームメイト2人も合流して一緒に考える。ゆきのんさんがフローと言ったので、その方針で考える。ちょっと迷走したが、頂点を倍加して流量1、コストを-体積
とする方針で考えることにする。
とりあえずそんな感じで実装する。最小費用流のコストに負も許すためには、内部のダイクストラを最初の一回だけベルマンフォードなどの負辺を許すアルゴリズムにすればよい。修正のしやすさを考えると、priority_queue
をqueue
に書き換えればよさそう。僕はこれがSPFA
だと思っていたが、実はキューに2回要素を入れないなどの高速化もするらしい。
まだうまくいかない。答えが小さくなっている。答えを小さくするには、倍加した頂点を通る必要があるが、流量はちゃんと1に設定しているので、どこかで通ってはいけないのに通ってしまっている。冷静になって考えると、パスの始点でありながらパスの中継点にもなってしまう可能性があるようだ。中継点になるためには倍加した頂点を通る必要があるので、こちらは必ず1回以下だが、パスの始点になるのには特に制限を設けていなかった。修正する。
計算量もってくれよ!頂点3倍界王拳だっ!!!
さっき倍加した頂点からさらにもう一つ伸ばして、そこの流量を1にする。パスの始点となるときも中継点となるときもそこを通ることになるため、これでどちらか1方しか選べなくなる。
あとはここにいくらかフローを流して最小のコストを求める。流す流量は1
からN
なので、流量を変えつつ毎回グラフを作り直して流しまくればよい。AC。
午後8時になったのでチーム練を終了する。Fにみんなで取り組んでACできたのはよかった。Eの幾何は……ナオキです
こどふぉが始まっている。ABCと被っているので、そちらを優先するため元から出る気はない。
てってれー pic.twitter.com/6JkyITDnBd
— こたつがめ (@kotatsugame_t) 2020年11月1日
10/30に注文したBluetoothアダプタが届いた。ケーブルが消えてかなりうれしい。ただ、パソコンをスリープから復帰させたときはキーボードの電源ボタンを押さないとキー入力ができないので、ちょっと不便に感じる。これまで使っていたキーボードは、キー操作をすると自動で電源が入っていた。持ち運びとか考えると、それはあまり嬉しくないのかな。
キーボードのキー配列を操作するスイッチのうち、SW2だけONにした。これで左Fn
キーがCtrl
キーになり、Ctrl
キーが英数キーになる。
まず
Ctrl
とShift
の位置がこれまで使っていたものと逆になっており、かなり違和感がある。 プログラミングには関係ないが、半角/全角キーに相当するボタンが左下にあるのも結構つらい。
10/30にこのようなことを書いていたが、両方解決された。半角/全角キーの代わりに英数キーを使っている。
ただ、今度はFn
キーが右下にしかなくなったのがちょっと不便に感じられてきた。Del
とかEnd
とか、あとF5
とかはかなり使用頻度の高いキーなので、簡単に押せるようにしておきたい。まあこの辺りはスイッチで解決しようとせずにキー配列を変更するソフトウェアを使うべきだろう。そもそもFn
キーとのコンビネーション自体全然慣れていないので、しばらく様子を見たい。
お手軽3,000円コース【普通】で、
— こたつがめ (@kotatsugame_t) 2020年11月1日
★4,260円分 お得でした!(速度:5.5key/秒、ミス:9key)
https://t.co/fueG45j1xr #寿司打
お勧め5,000円コース【普通】で、
— こたつがめ (@kotatsugame_t) 2020年11月1日
★7,660円分 お得でした!(速度:6.3key/秒、ミス:21key)
https://t.co/fueG45j1xr #寿司打
3000円コースと5000円コースもやってみたが、一発で倍のスコアが出た。うれしい。
ABC181が始まった。3位だった。
C問題は、最初N<=1000
と勘違いしていて、3乗が微妙に間に合わないと思ったので傾きをset
に入れて重複を調べることにした。O(N^2 log N)
。書き始めたところでN<=100
に気づいてちょっと残念な気分になったが、3点が同一直線状にあることをチェックする数式がパッと思い浮かばなかったので、そのまま実装する。傾きをdouble
で管理する必要はなくて、pair<int,int>
を適切に正規化すればよい。gcd
で割って、x
を正にして、x==0
のときはy
を正にする。最近のABCで似たようなことをやったな、その時はもうちょっと複雑だったような……と思っていたが、それは90度回転も許していたから。
F問題は、直感的に「釘と直線をグラフの頂点として、ユークリッド距離をコストにして辺を貼り、パスのコストを「通る辺のコストの最大値」としたときに直線から直線への最短距離÷2」が答えだと感じたので、それをダイクストラで実装したら通った。(辺の数がO(N^2)
なので、毎回全点に対して更新することにするとpriority_queue
が必要なくなってlog
が落ちるらしい。)
この値より大きな半径だと左から右へ抜けられないのはわかるが、この値以下であれば抜けられることを示せない。サンプルが合ったので提出しただけ。解説を読んでも右手法がどこで使えるのかわからず困惑していたが、kyopro_friendsさんのツイートで納得できた。
アライグマ「F問題は……「半径rの円が通れる」っていうのは、「円の中心が障害物からr以内にならない」ってことだから、逆に障害物の方を半径rの円にしちゃえばいいのだ!」 pic.twitter.com/xMAlQ7ZSph
— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年11月1日
これすごい。似たような問題がいくつかあるらしい。
コードゴルフをする。A問題はそもそも最初の提出が最短。B問題はRuby
やRaku
でrange
の総和がO(1)
になることを利用すると短いかと思ったが、dc
で普通に計算したほうが短かった。
C問題は、combination(3)
するよりも、1点固定して残りの頂点と結んだ直線の傾きに重複があるか調べたほうが短かった。点(a,b)
を固定して、(x,y)
に対して(y-b)/(x-a)
を列挙する。x==a
のときは代わりにy!=b
を値とすればよい。(a,b)==(x,y)
のとき、同じ頂点を2回カウントしていることになるので除外する必要があるが、true/false
で分けることで達成できる。
最初は三項演算子を使っていたが、(y-b)/(x-a)rescue y!=b
のほうが短くなった。ゼロ除算の例外をキャッチしている。コードゴルフにおいて初めてrescue
を使った気がする。
AOJ-ICPCを埋めようとしたが、眠すぎて動けない。椅子に突き刺さって寝てしまう。意識を取り戻してとりあえず週記を書き上げようとしたが、できず、布団に倒れこんでまた眠ってしまった。