NF

地方で働くプログラマ

ABC154速報

AtCoder Beginner Contest 154 - AtCoder

コンテスト中に雑感を書いてやるぜ。(公開は終了時点まで待つけど)

最近のABCはDまで知識なくても何とかなるんだけど、そういう場合は他の人も解いてるのでスピード勝負になる。これはABCなら全完できる人でも同じで、全完までの早解ゲーになってるらしい。

という訳でCから着手したけど、割とすっと解けて3分台。A,Bを片付けてDへ。あれ、Dも解けそうだ…ってことで色々調べて累積和ってやつですね。考え方自体はまんまWebで見つかりました。これ。
累積和を何も考えずに書けるようにする! - Qiita

あとは実装するだけ、有効桁数を間違えたりしたけど結果30分キリでDをAC。この時点で1600位ちょっと。自分にしては最高順位がでたかも。しかし、さすがにE/Fはどうにもならなそうなので早めに諦め。あとは他の作業しながらランキングがどれくらいまで落ちるかを見守るのみ…
ちなみに残り30分で1900位下回ったので2000以内は厳しいかな…


(22:40追記)
うおお、ギリギリ2000位台に落ちた…まぁいいんだけど
あと最終順位はABC143で1600位台出してたし、1000位台もちょくちょく出してた。E解けてるのが1200人位なので、Dの速度でもうちょい何とかなったかも。

劇場版 ゴブリンスレイヤー –GOBLIN’S CROWN-


2020/2/2(日)、映画ゴブリンスレイヤーの舞台挨拶(トークショー)に行ってきました。

上映開始が昨日。今日の朝一はキャスト全員、それからメンバーが分かれて自分はすみぺ・唯ちゃんがいる横浜に参加しました。杉田さんと絡む二人も気になったけど、重複なし第3希望制でこの回しか当たらなかったので。

トークショーは上映後なのでまずは鑑賞。トークショー狙いの人が多いのか空席はそれなりにあり。あと主演の人目当てが女子も多い。前列の方の女性たちは映画終了後に一斉に化粧を直して?ました。内容は1時間くらいで、まぁアニメの1エピソードをちょっと長くした感じ、特にストーリー本編との関係もなさそうなのであまり映画館で見るほどではないかも。でもゴブスレ本編として面白かったし、映画ならではの迫力もありました。あとすみぺのやられ声が凄かったので、好きな人は楽しめたかも。自分はりょな系苦手なのであんまり…

本編終わって司会の人と3人が登場。3人とも移動してきて寝起きらしく。すみぺは役の令嬢剣士っぽいという衣装。主演の梅原さんに合わせてるのか、最初の方は割と真面目系のトークでしたが、後半はすみぺが色々ふざけ始めて会場も盛り上がってましたね。他の回では杉田さんがすみぺ衣装をDTスレイヤーと名付けたり、すみぺが唯ちゃんと箱根旅行を取り付けたりしたそうです。

ちなみに席は6列目の端寄りだったので、割と前の方で見れたと思います。唯ちゃんも可愛かったです。後から気づいたけど、唯ちゃんはリリイベが当たらないのでよく考えたら貴重な近くで見れた経験かも。

なお、一週目入場者特典は女性陣CDでした。比較的当たりらしい。


www.instagram.com

はじめてのXXX(外伝)

ちょっと書くのが躊躇われるので、ぼかして書きます。ソフマップとは違いますがそれ系(?)です。でも知ってる人は分かっちゃうけど。何のことは分からない時はこの日のカメラロール見て。>未来の自分
ちなみに前回の日記
久々にソフマップ - NF

続きを読む

2019アニメ新番とか

今3,4話位ですが、見てるのを列挙。
 
継続視聴したい
・マギアレコード 魔法少女まどか☆マギカ外伝(面白い)
・群れなせ!シートン学園(面白い)
・虚構推理(割と面白い)
・ソマリと森の神様(割と面白い)
・恋する小惑星(声優好きで見てる)
 
割と継続視聴したい
・異種族レビュアーズ
・へやキャン△
・ネコぱら
 
継続視聴諦めた
・痛いのは嫌なので防御力に極振りしたいと思います。
・インフィニット・デンドログラム
 
気になる(まだ見てない)
・映像研には手を出すな!
・推しが武道館いってくれたら死ぬ
はてな☆イリュージョン
魔術士オーフェンはぐれ旅(3話までは先行上映で見たので)


と言う感じで、割と見てます。確実に最後まで見そうなのはマギアレコードでしょうか。シートン学園はゆかりんが出るという事で見始めたけどいい声声優が揃ってるし話も面白い。ハイエナネタが異種族レビュアーズと被ってたのは笑いました。
虚構推理は気になってて3話見たら面白かったので。主人公の鬼頭ちゃんが良い感じだし、すみぺがすみぺらしい役で出てるので。ソマリは全然見る気なかったけどたまたま見た3話が結構良かったので、継続しようかと。恋する小惑星は今の事話にはあまりハマれてないですが、声が良い(特に指出ちゃん)ので見てます(というか聴いてる)。中盤からハマれたらイベントも行きたかったり。




ーーー
あとついでに、春にかけて結構見たいアニメ映画がありそうなのでメモ。基本、ゴブスレ劇場版の番宣で気になったものです。
ゴブリンスレイヤー GOBLIN'S CROWN(観た)
デジモンアドベンチャー LAST EVOLUTION 絆(不安だが)
・劇場版 SHIROBAKO(懐かしい)
・劇場版 ヴァイオレット・エヴァーガーデン(観たい)
・劇場版 Fate/Grand Order -神聖円卓領域キャメロット-(観たいがついていけるか不安)
・さよなら、ティラノ(石原夏織さんが主演)
・どうにかなる日々(気になる)
・シン・エヴァンゲリオン劇場版(ほんとに放映するのか)


定期的に映画館に足を運ぶことになりそうです。今って一般1,900円・レイトでも1,300円か。まぁ見ても月2本くらいなのでいいか。

コロナウイルスとかなんとか

なんか散々な一日だった。いやそうでもないけど。
早く帰りたかったのに仕事積もってくるわ傘ぶっ壊れるわ。傘ってあんな壊れ方するんですね。コンビニに駆け込んでびしょ濡れだし、そのせいか体調悪い気がする。あとビニ傘は骨とビニール部分を分けてゴミ出しする必要があると知った。地域によって粗大ごみじゃないんだね。考えてみれば当たり前だけど、傘使えない程ぶっ壊れたの初めてなので…

ーーー
全然関係ないが、最近大空直美さんの声が好きすぎる。(sweet café time見ながら)

ーーー
今日のすみぺ
次のニュータイプ写真集に収録されるかな…
www.instagram.com

ーーー
なんか、いろんなイベントあるんだなって。書けないが。

ABC153

もう遅いので記録だけ。
ABC153参加しました。4完でギリ3000位内、茶色上位パフォでレートは微増。

今回はかなり簡単な部類(TODO:通常のABCと数字で比較する)で30分以内でDまで解けた訳ですが、Eが最後まで解けずでした。もう少しだったような気がしましたが、解説見てたらDPとかナップサックとか未理解の概念が出てたので全然もう少しじゃなかったです。でも、サンプルが最後まで通らかった作成中のコードを記録のため提出しといたらsample_03除いて全てACでした。なんかコーナーケース踏んでるのか…

ちなみに、4完組では最速5分で解いた人が2000位ちょい(パフォ1000)、遅い人で時間切りで5000位ちょっと。今回Eが壁だったので、4完でもかなり時間で差が出てます。仮想ライバル1号の人もD解くのが自分より20分位遅れて4000位内)。パフォ300位違うが、レートは全然縮まらないのねー


いつもと難易度設定が違うので上位勢?からは不満出てるみたいですが、個人的には茶色勢としてはトライする問題が普段より多かったので楽しかったです。あと、問題設定が全問似せてあって問題理解で躓くことがなかったのも良かったです(ツイッターでもこれ言ってる人いました)。今回のライターの人がけもフレなりきり勢で、大丈夫か(失礼)と思ってましたが
、今後も担当して欲しいですね。


BGM:Born Legend、READY→⇒→GO、Wonder Girl_マジック3

ABC152-D復習

ABC152 - NF

ちゃんとお休みなので先週のABCの復習。今回Dを飛ばしてEを解いてる人が多かったのでEもやりたいですが、取り合えずDまで。リアルタイムでは愚直に実装して2/3がTLEでした。
以下、ACまでの取組結果ですが、やりながら書いたので非常にまとまってないです。

ーーー
■ 解説を読む
目標は解説ACなので、まずは解説PDFを読むが全然分からず。次に解説動画(実装前まで)を見るけど、やはり良く分からない。動画はPDFよりは分かりやすいしやってくれるのは有難いんですが、C以上を解説動画見て理解できたことが一度もないです。自分は茶色中位だけど、おそらくもう少し上のレート(または頭いい人)を対象視聴者として設定されてるっぽいです。同じ位のレートの人でも「解説動画でACできました」「凄いわかりやすい」という人もいるので、慣れの問題もあるかもしれない。

という訳で解説サイトを探します。前回の日記で解説サイトさんをリンクしましたが、Dについて詳しい説明を書いてる方が中々おらず。まぁ万人向けに解説している訳ではないし、自分用メモって方も居ると思うので。そんな中、一番わかりやすかったのは下のブログでした。この方は結構上のレートの人みたいですが、かなり下のレベルにもわかりやすい解説を書いてくれるので、大変ありがたいです。
AtCoder ABC 152 D - Handstand 2 (400 点) - けんちょんの競プロ精進記録

これで回答にたどり着いた訳ではないけど、方針が理解できたので、再度実装にトライしました。ここまで前振りで以下解法メモです。

ーーー
■ 実装してみる
最初にやったとおり愚直に計算するとO(N2乗)、Nが2×10の5乗なので時間が間に合わない(後述しますが、この条件だと間に合わないって皆さん何を以って判断してるのだろう…)。という訳で工夫が必要。

最初と最後の数字に注目します。例えばN=10000のとき、Aが1234、Bが401の場合は条件に合致する。あとAが1みたいな一桁の場合、Bが1221の場合とかと一致します。よって間の数は関係ないので、桁数とかも関係ない訳ですね。


そこで、まずAについて最初と最後の数字のペア(以下、[X, Y]と記載)を数えます。N=100の場合、[1,1]はA=1、11の場合が該当するので2回、[1,4]はA=14の時だけなので1回。これをmapとかに持っておく。これを作るのはO(N)の計算でできるみたいです。

次にBについて、今度は逆に最後と最初の数字のペア([Y, X])に対して、[X, Y]があるか探すわけですが、すべてのAについて探すと先の通りO(N2乗)になります。ただし、先にAの[X, Y]の組み合わせは登場回数をカウント済なので、1つのBに対して99通り試せばよいだけです。これはオーダでいうとO(N)ですね。例えばB=11の場合、全てのAについて探すと結果A=1とA=11がヒットするわけですが、[1,1]の登場回数が2回なのを知ってるので、これを回答用の引数ansに足しこんでいきます。
これでAC出来ました。

ーーー
■ 計算量について
今回に限らないんですが、どこの解説でも「Nが2×10の5乗で、愚直実装だと計算量がO(N2乗)なので間に合いませんよね」って書いてますが、何故そうなのかに触れてる人がいないので、未だに理由が良く分からず。経験則なんでしょうか?

例えば最内ループで1[ns]掛かる計算をする場合、単純に2×10の5乗を2重ループにすると40,000,000.000[ns]=合計40[sec]。大抵、実行時間制約が2[sec]なのでこれだと確かに間に合わないですね。これが10の4乗だと合計0.4[sec]になりますが、そもそも1[ns]の処理とか無理なので、係数次第ってことになるんでしょうか?

ーーー

そんな感じで記録を書いてみました。この後Eに取り組みます。

上でも書きましたが低レベル向けの解説不足に困っているので、灰色・茶色向けに解説書いてますって方がおられたら教えてください。こっちからできる事は何もないですが…