ととりにゃあの日記

これはなに?ととりにゃあの日記です。

今日も朝からお酒を飲んでいます。
今日のお昼ご飯は、チキンラーメンの焼きそば風を食べました。美味しかったです。
夜ごはんはコンビニで買ったチキンカレーとサラダを食べます。これも美味しいはずです。
明日は早起きして、学校に行きます。そして授業を受けます。そのあと競技会に出ます。頑張ります。
おやすみなさい。

とりにゃあの一日 おはようございます。
昨日は飲み過ぎて頭が痛いです。二日酔いというやつでしょうか。
でも今日は学校に行かなければなりません。頑張っていきましょう。
朝ごはんは、インスタント味噌汁とお米です。いつも通りですね。
午前中の授業を終えて、昼食の時間になりました。
今日は、カツ丼定食(揚げ物)を選びました。とてもおいしくいただきました。
午後からは競技会の会場に行ってきます。
会場ではたくさんの人がいました。私と同じぐらいの学生さんが多いようです。
私はC言語の問題を解き始めました。
問題を解くことに集中していたので、あまり周りのことは覚えていません。
気が付けばもう夕方になっていました。
急いで帰らないといけません。
帰り道の途中でスーパーにより、晩御飯を買いました。
家に帰ったらすぐに食べます。
晩御飯はとてもおいしいです。
ごちそうさまでした。
それではまた明日。

とりにゃあの一日 おはようございます。
今日は競技会がある日なのですが、会場まで行く途中にある道を歩きながら行きたいと思います。
でも今は梅雨の時期で雨が降っています。
傘を差しています。
とても暑いです。汗が出て来ます。
会場に着く前にどこかで休憩したいです。
休憩できる場所を探していると、公園を見つけました。
ベンチがありました。そこで少し休みます。
自動販売機があったので飲み物を買うことにしました。
お茶を買って飲みました。
しばらく休んだ後、会場に向かいました。
会場に着いた頃にはすっかり晴れていました。よかったです。
さっそく問題を解き始めました。
問題を解くことに夢中になっていたため、周りが見えなくなってしまいました。
気づいた時にはもう夜になっていて、帰る時間になってしまいました。
早く家に帰って晩御飯を食べないといけません。
急ぎ足で帰宅します。
今日も充実した一日だったと思います。
それではまた明日。

とりにゃあの一日 こんにちは、とりにゃあです。
今年も夏がやってきましたね。
暑くて外に出る気力がありません。
今日も家でだらだらと過ごしてしまいました。
でもこんな日があってもいいと思っています。
夜に友達から電話がきました。
一緒にゲームをしようということです。
もちろんOKを出しました。
どんなことをするのか楽しみです。
ちなみに、今日も外には出ませんでした。
とりにゃあは引きこもりではありませんよ。
それではまた明日。

とりにゃあの一日 おはようございます。
今日は友人と一緒に映画を見に行きました。
銀魂」の映画を見てきました。面白かったです。
その後、食事をして遊んできました。楽しかったです。
とりにゃあは普段は一人で過ごすことが多いのですが、たまには誰かと遊ぶのもいいですね。
そろそろ一人でいる生活にも飽きてきましたし、新しい出会いを求めてみようかなとも思います。
まぁ、しばらくはこのままの生活を続けていくつもりですけどね。
それではまた明日。

とりにゃあの一日 おはようございます。
今日は雨です。梅雨だから仕方ないよね。
ということで、今日も一日部屋の中で過ごそうと思います。
お昼ご飯はカップ麺を食べました。とても美味しかったです。
その後はずっと録画していたアニメを観ていました。とても楽しい時間でした。
あっという間に時間が過ぎて夕方になりました。
夕ご飯は何を食べようか迷っていたところ、近所のスーパーでセールをやっていたので、それに決めました。
今日は鶏肉を使った料理を作ります。唐揚げを作る予定です。
とても美味しい夕食ができました。
ごちそうさまでした。
それではおやすみなさい。

とりにゃあの一日 こんにちは、とりにゃあです。
今日は久しぶりに外出することにしました。
電車に乗って、本屋さんに行ってきました。
欲しい本がたくさんあったので、いろいろ買ってしまいました。満足です。
そのあとは、カフェに行って、ケーキセットというものを頼みました。
甘いものが好きなとりにゃあにとっては至福の時間でした。
とても幸せな気分になれたので、明日からも頑張れそうです。
それではまた明日。

さいごに

この日記はAIのべりすとにより生成されました。
私(くれそん)が書いたのは最初の一行(これはなに?ととりにゃあの日記です。)と日をまたいだときの改行だけです。

俺のchokudai Searchが遅すぎる

chokudai searchをするときに余裕を持ってTime Limitを設定してもTLEしてしまう話と解決法

問題

先日AHC002がありました.そこでchokudai seachを実装したのですが,TLを1600msにしてもTLEになってしまうことが多々ありました.

f:id:qlethon:20210426101339p:plain

次のような実験をしたところ,関数のreturn直前ではTLくらいの時間しか経っていないにも関わらず,return直後ではTL + 数100ms経っていることが分かりました.

void chokudai_search(){
    /* メインの処理 */
    
    時間の計測  // 1630ms
    return;
}

int main{
    /* 前処理 */
    
    chokudai_search();
    時間の計測  // 2030ms
}

時間はテキトーですが,だいたいこんな感じです.

このことからchokudai searchで使った大量のキューの後処理が関数から返る時に走っていて,それが重いのだと予測しました.

解決法

関数から返る前に出力を済ませexit()を使う.

せや!関数から返る時の処理が重いんだったら返らなければええんや!と思い,次のようにしました.

void chokudai_search(){
    /* メインの処理 */
    
    答えの出力
    exit(0);  // ここでプログラムを終了する
}

int main{
    /* 前処理 */
    
    chokudai_search();
}

すると,だいたいTLくらいで終わるようになりました.

f:id:qlethon:20210426102600p:plain
TLは1700ms

さらに,ドキュメントを見るとexit()より早いquick_exit()があることが分かります.しかし,実験をするとなぜかexit()より遅いです. TLは1950msです.

さいごに

exit()が早い理由,quick_exit()がexit()より遅い理由,abort()が遅い理由すべて分かりません!!!!有識者HELP!!!!!!!!!!!!!

qLethonの提出 - https://atcoder.jp/contests/ahc002/submissions?f.User=qLethon

ICPC2020アジア地区大会参加記

私qLethon(@pu__Ne)、totori(@totori_kpr)、binくん(@5bin101)の3人で チームATELIERで出ました。

結果は7完16位でした。良い結果だったと思います。 f:id:qlethon:20210318045528p:plain

1日目

一週間続いたAHCにより生活が壊れていて前日(?)朝7時に寝たため、かなりギリギリまで寝ていました。 受付は13:30までです。

なんとか受付を済ませ(全体的に確認作業は押していたっぽい)開会式を済ませます。

ログインに手こずりコンテストに若干遅れて参加したため、通話に参加したときは既にととりとbinくんがそれぞれABを読み始めていました。
私はチームメイトにテキトーにやっていいことを確認した上でCを読む宣言をしDを読み始めます。 Aを通したととりにゃあがDを読んでいたらしく、私が黙ってDを読んでいたことに若干キレていました。
Dは普通に分からないのでCを読んだあと、Bを通したbinくんに問題概要を説明します。 2人で考えて、binくんが2つの集合をマージしていく方針を考え、私がある点集合を取ったときにすべて同じ傾きにできるかという判定部分をO(N2)でできるという主張をしました。 方針をbinくんに伝え、私はやばかった大学の書類に少し手を付けた後実装に加わりましたが、間に合いませんでした。ととりはいつの間にかDを通していた。

コンテストが終わると冷えたAHCのレートが来ていました。思ったより高くて安心です。

ここからが本番です。
ICPCには早寝早起き部門というのがあり、1日目は早寝フェーズです。 しかしここは生活崩壊のプロ。開会式前に無理やり起きたおかげで今日は十分に眠いです。なんと22:30に寝ます。

2日目

まずは早起きフェーズです。00:30に起きます。優勝です。(絶望)
その後結局3:00くらいまで起きた後なんとか寝直して、なんと余裕を持って8:00に目覚めます。(開会式は8:45開始)

あまりの芸術点の高さに農工大メンバーからは歓声が上がりました。

余裕をもって目覚め、朝の心地よい空気の中意気揚々と開会式のzoomに入ると、迷子案内所にたどり着きました。

運営の方は我々のことをとても良く分かっていると思います。

前日までICPC本番であることの実感が全く無かったのですが、朝の清々しい空気と開会式により徐々に実感を得ます。気分は部活の試合時の朝集合です。高校では科学部でした。

チームミーティングが始まり今日の作戦を決めます。私はABをバグらせるので後ろを担当しろとととりに言われました。素晴らしい作戦だ。

コンテスト

ぞいの鳴る音と同時に私は一番後ろのKから読み始めます。難しそうなのですぐに飛ばしてJを読み始めます。 Jは簡単そうです。既に数チームが解いていて、問題も単純です。Bを通したととりにゃあにJKの報告をして、Jは通せそうなので他を任せます。まもなくJが通ります。通りました。(0:46)

Aは手こずっていたようで、ととりにゃあが介抱に行っていました。しばらくすると通ります。(1:12(+1))

C, E, G, H, Iあたりが次に解ける候補に上がっていて、私はIを少し考えたのですが、私の解く問題ではないと感じGを考えます。

しばらく考えると、ととりにゃあがGを分かりかけているらしいので私が今まで分かったこと(必要十分条件(未証明))を伝えて他の問題に行きます。
必要条件は連結成分を圧縮して二部グラフを考えるとすぐに分かります。二部グラフに必要な最小の辺を引いたあと、良い感じに接続し直すと制約を満たすように辺が貼れて、十分っぽい感じがします。

IはやりたくないのでHを考えます。素因数ごとに考えると、GCDのLCMは小さい方からk + 1番目を選ぶ操作であることが分かります。素数は大体105個あるのでこれだと間に合わないのでなんとかします。なりませんでした。 一応いろいろ考えたので後ろに書いておきます。

途中でととりのGは通ります。(証明: AC) (2:09(+1))

さらにbinくんと介抱のととりがIを通します。天才。(3:15) ここで私はHを諦めCとEの問題概要を聞きます。どう考えてもCが一番おもしろそうなのでCをやります。

制約にスタートとゴールは壁に接していると書いてあります。この制約は右手法を使わせるための制約です。6行で右手法を書けることをととりに報告すると、6未満手数全探索でいけそうとの返答がありました。それで解けそうですが、問題はシミュレーションを書かなくてはならないことです。厚い信頼により実装を任されます。

通話をスピーカーミュートし黙々と書きます。大体60分くらいで実装とデバッグが終わり通ります。(4:51)
通話に戻るとEのコードがバグっているようでした。ととりとbinくんの環境でサンプルの結果が違うらしく、2人は未定義動作を疑っていました。ととりが投げるとなぜか通ります。(4:57(+1))

ラスト10分で2完した勢いでととりがD, F, H, Kも投げます。
ここでATELIERに全完2位WF出場の可能性が芽生えます。

閉会式

1問ごとにCMが流れる解説を聞き流し、まもなくするとYes/Noが始まります。ICPCのメインイベントです。
eat_iceが潜伏作戦を取っていて、凍結後の順位表で全11問提出確定0ACの異常になっており、非常に盛り上がりました。少しでも会場の盛り上がりに近い雰囲気を感じたいと思い、Gatherで近くの人間の反応を盗み聞きしていました。Gather唯一の有効活用法です。

ATELIERもそこそこの盛り上がりを演じて16位に着けました。
同じ農工大のチームnowcowの2つ下です。

懇親会

閉会式が終わると懇親会の時間です。社交性のない人間にとってはないのと同じなので夜に開かれるであろうボドゲ/Among Usに備えて寝ます。

懇親会-夜の部-

起きると公式懇親会は既に終わっていました。
競プLoLボドゲ大会が開催されていたのでそれに混ざり、その後はAmong Usをやりました。ここでかなり知らない人とお話ができたので良かったです。ゲームはコミュ障を救う。

感想

前日まであまり実感もモチベもなかったのですが、やってみるとかなり楽しく今までで一番短い5時間コンテストでした。(後から振り返ると、何をやっていたんだ?という気持ちになる)。
開会式などではかなり社会性がない人間競プロer向けの配慮がされていました。また、閉会式の進行などを聞いていても運営側の競プロへの思いが伝わってきました。非常に丁寧な対応で、今まで出場したコンテストの中で一番雰囲気が好きでした。スタッフも競プロ関係者[要出典]なのがそういった心象を与えたのかな。ICPCサイコ~~~ 来年も出ます。

Hの考察

TODO: 書かない

数列に含まれる素因数の数はO(NlogA)なので、素数ごとにいくつの要素で使われているか((2, 2, 6)なら2は3つの要素で使われていて、3は1つの要素で使われている)を持っておき、逆に$i$個の要素で使われている素数のリストも持っておきます。そうすると、クエリの範囲が多いときは$R - L$ - 1個

CodinGame Fall Challenge 2020に参加しました

結果

世界113位 日本33位でした。
レジェンドに行けなくてとても悲しいです。
f:id:qlethon:20201123191527p:plain

学校別では世界6位 日本5位でした
f:id:qlethon:20201123210337p:plain

バグがやばかったり何も分からない時期が続いたりして終始HELP!って言ってた

やったこと

  • 最初の8ターンは一番下の呪文を取る
  • 10手読みのchokudai search
    • そのターンの評価 = 今までに作ったポーションの評価 + 0.9 * 現時点でのインベントリの評価
    • ポーションの評価: そのまま
    • インベントリの評価: tier 0-3に1-4を割り当て、その和
    • 盤面の重複はZobrist Hashで弾く
  • 探索に含めているもの
    • ポーション作成
    • 呪文キャスト
    • 下から4つまでのLEARN
    • REST
  • 終盤は相手の手をchokudai searchで4手読む(10ms)
    • 条件は自分か相手の作ったポーションが5個になったら
    • 各ターンの相手のスコアのmaxを記録して、自分がゲームを終わらせるときにbrewによって到達するスコアがmaxを超えてたらbrewするみたいなことをした
    • 相手がゲームを終わらせられるターンにポーションを作れるなら作って一番スコアが高い状態にする
  • 最終日まではdfsで4ターン全探索だった(これでも全体100位代だった)

試したけど採用しなかったこと

  • 最初に呪文取るフェーズを探索に組み込む
    • ターンごとに線形で減衰するボーナスをかける
    • まだ貼ってない辺(e.g. tier 0 -> tier 1)にボーナスをかける
    • 貼れる辺の組み合わせはいろいろ試した
    • tier 0, 1, 2からtierが上がる方向の辺とtier 3からtier 0, 1, 2にボーナスをかけるとか
    • chokudai searchにしてからは試してないのでもしかしたらうまくいったかも
    • dfsだと4ターンしか読めないのでそれでうまく行かなかったのかも
    • 素材の評価を1.41tierにする
  • ポーションの価値をターン数によって減らす
    • 途中までターン数で変えてたけど、運用効率の方が大事なことに気付き辞めた

思いついたけどやらなかったこと

  • 初ターンに全呪文のグラフを作ってなんか良さげなループを見つけ出して、tomeから構築できそうなのを取る
  • 絶対に取らない呪文を決める
    • 取る呪文を決めるのは難しいので、逆に絶対に取らない呪文を決めてやったほうがうまく行くんじゃないかと思った

全体の流れ

repeatableに対応した時点で最強になって調子に乗る(38位)
この時点でdfs 4-6ターン読みだった

なんか何もしないで19位とかになって更に調子に乗る

3日くらいバグが発見できず何もできない
180位とかに落ちる
この時、かなり精神状態が最悪だった

直したら70位くらいまで持ち直す

そこからAmong Usにハマってさらに3日間何もしない

いつの間に最終日になっているのでchokudai searchを実装するも、いろいろ間に合わずレジェンド未達

秋分コンテスト2020参加記

追記: PCで見ると画像と文字がぐちゃぐちゃになっている。なに?hatena blogなにも分かりません。(許して)
追々記: スマホで見ることを推奨します。
追々々記: たぶん直った

秋分コンテストにととりにゃあ(ととり (@totori_kpr) | Twitter)と出ました。ほとんどRをやっていました。吐きそうです。

初手の感想
f:id:qlethon:20200923005000p:plain

とりあえずくそなぞなぞから解き始めるも、全然わからない。
f:id:qlethon:20200923005133p:plain

ととりにゃあがなんか色々やる
f:id:qlethon:20200923005249p:plain

開始12分にして地図問題を引き当ててしまう。すべての終わりは、ここから始まった――。
f:id:qlethon:20200923005453p:plain

とりあえず建物群のなかで特徴的なものを探すが、何もわからない。
f:id:qlethon:20200923005553p:plain

駐車場マークは見えるけど、それだけじゃ何も分からない。

BでWAが出たらしいので、なんかテキトーを言う。
f:id:qlethon:20200923005651p:plain

石の素材でぐぐろうとするも失敗。京都っぽいけど近場なのかな?と思い住所を探る。問題文的に家の近くかと思っていたが、しばらくしたら完全に忘れていた。
f:id:qlethon:20200923010209p:plain
f:id:qlethon:20200923010302p:plain
f:id:qlethon:20200923010323p:plain

tozanさん周りを調べて、翻弄される。タイムズではない。
f:id:qlethon:20200923010403p:plain

ととりにゃあがCをやっていて、4とか分からなかったっぽいのでとりあえず一瞬見て椅子取りゲームを当てる。10点。

あみだくじは嫌なので、すべてをととりにゃあに任せてひたすら川の画像を眺める。まだ正気を保っている。
f:id:qlethon:20200923010648p:plain

よく見たら既に吐きそうになっていた。Google Mapsストリートビューはめちゃくちゃ酔うので、長時間使用できる技ではない。

私が川に詳しくなっている間にととりにゃあがあみだくじを終わらせる。ついでにO: 沖縄も解いてくれる。

f:id:qlethon:20200923010941p:plain
シークヮーサーだろって何……?(問題を見ずにテキトーな発言をしている)

ここでととりにゃあがEがウミガメであることを発見する(ウミガメではない)。川を見るのに飽きたのでウミガメは得意なので、やる。
f:id:qlethon:20200923011125p:plain

ととりにゃあが嘘の撤退宣言をする。チャットの相手がbotであることに気づく。
f:id:qlethon:20200923011251p:plain

絶対にウミガメではない。
f:id:qlethon:20200923011351p:plain

Cが通る。
f:id:qlethon:20200923011422p:plain

ととりにゃあが日本語を使えないので、シークワーサーは私がやることになりそう。
f:id:qlethon:20200923011506p:plain

hosさんがAを通していて面白そうなので、一瞬やるけどもちろん通らない。想定なに?
f:id:qlethon:20200923011604p:plain
f:id:qlethon:20200923011617p:plain

f:id:qlethon:20200923011655p:plain
まだ諦めてなかったんだ。

ととりにゃあのウミガメがうまい。私はへた
f:id:qlethon:20200923011808p:plain
f:id:qlethon:20200923011836p:plain
f:id:qlethon:20200923011855p:plain

上限→これは……6か?いや、上限……それは、66か?何故……どうして66という値が……。そうか、これは■■■■に記されし限界の……。

OEISをエスパーする。
f:id:qlethon:20200923012041p:plain

このあとも66がProject Eulerの問題番号か?とかOEISのA6, A66か?と言ったりする。全部はずれ。

ととりにゃあ、二度目の嘘撤退。
f:id:qlethon:20200923012222p:plain

WAになるあみだくじ。ついでにAも落ちる。
f:id:qlethon:20200923012257p:plain

Yが通らない。メッセージにキレて書き直す。沖縄は通った。頂点番号を振って辺を貼った。

f:id:qlethon:20200923012408p:plain
この後もう一度キレることになる。

絵しりとりをやり始める。1つ目は葉じゃない。83点が返ってくる。
f:id:qlethon:20200923012530p:plain
f:id:qlethon:20200923012556p:plain

気が付いたら朝の6時になっている。
f:id:qlethon:20200923032025p:plain

Nが分からないでいたらととりにゃあに唐突に煽られる。
f:id:qlethon:20200923032137p:plain

提出を一部変更してスコアの変化で合っている部分を割り出していたら、実は提出欄で見れることが発覚する。
f:id:qlethon:20200923032325p:plain

11がまったく分からない。
f:id:qlethon:20200923032508p:plain

私が枯れ葉と領海と一周とミームを埋める。一周とミームはキーなだけで正解じゃないの??
f:id:qlethon:20200923032736p:plain

11の帳尻を合わせようとするけど、何も分からず。結局私のほうが早く寝ることに。
f:id:qlethon:20200923032901p:plain

結局ととりにゃあは7:30までやっていた。撤退宣言をしてから6時間もやってること、ある?
f:id:qlethon:20200923033058p:plain

15:09 目覚める。ウミガメ(ウミガメではない)が下手すぎてGをやるけど8が通らない。通せよ。
f:id:qlethon:20200923033233p:plain

Nで絶対値を出力した時に数ケースあっていたので、とりあえず入力をそのまま出力して何ケース通るか見ようとしたら全ケース通った。は?
f:id:qlethon:20200923033320p:plain

またRを見ると、画像が追加されていた。

f:id:qlethon:20200923033555p:plain
京都ではありません。

頑張ってストリートビューで川沿いを下ったりする。めちゃくちゃに酔った。
f:id:qlethon:20200923033700p:plain
f:id:qlethon:20200923033836p:plain
f:id:qlethon:20200923033856p:plain

EでととりにゃあがOEISとか秋分とかを聞き出す。もうほとんど解けた。(解けなかった)
f:id:qlethon:20200923034133p:plain

A000922 - OEISかと思って投げるも、WA。秋分は昼と夜が12時間ずつだからA000012 - OEIS!とかやるも全然違う。

f:id:qlethon:20200923034404p:plain
?????

Rに画像がまた増えていた。

https://pbs.twimg.com/media/EifmBHGU8AEtVz9?format=jpg&name=large

お ま た せ い つ も の 。 君 の 名 は 。

実際には駅名が思い出せなくてワイドビューひだ(列車名は特定した)が停まる駅を片っ端からストリートビューで見ていくという泥臭い作業が一時間ほどあったが、なんとか特定に成功。初ACをもぎ取る。ここまで19時間21分40秒。

f:id:qlethon:20200923035154p:plain
めちゃくちゃに感動した

8番はめちゃくちゃに頑張って画像を見ると、8番線が岩瀬浜方面であることが分かる。よって「8番線 岩瀬浜方面」とかでぐぐる富山駅が出てくる。AC。
最初は京都駅か?とか言ってた。京都しか知らない。線路と同じ高さにホームがあって不思議な感じの駅だね。行ってみたい。
f:id:qlethon:20200923035233p:plain

ととりにゃあがLをAC。草
f:id:qlethon:20200923035723p:plain

この頃になってRの写真が時系列になっていることに気づき始める。未だに京都だと思っているし、tozanさんの草津ツイートに踊らされている。
f:id:qlethon:20200923035754p:plain

この気付きにより7と6を立て続けにAC
f:id:qlethon:20200923040231p:plain
f:id:qlethon:20200923040304p:plain

7は画像に写っている隣の駅名に注目して解いた。(車両から路線を特定したかったが無理だった)。最初は"??なら"駅だと思って探していたが、5枚目の飛騨古川から富山までの駅に楡原(にれはら)駅があることに気付く。隣の駅を調べて、ストリートビューで確認してAC。
6は京都市内かと思っていたけど、時系列的に飛騨古川で降りて観光したのかなあと思って近くの寺を調べると簡単にAC。だんだん分かってくる。

f:id:qlethon:20200923041216p:plain
ここでようやく京都でない可能性が頭をよぎる

京都から飛騨古川を経由して富山に行くルートを検索すると6時間くらいかかることに気付き、時系列的にちょっと時間かかり過ぎかなあと思ってきた。もしかして岐阜か?と思い3の市場を調べるとそれっぽいものが出てきて、AC――。

f:id:qlethon:20200923041621p:plain
このコンテストで一番テンションが上がった瞬間だった

3は結構罠で、「岐阜 市場 川沿い」などで調べると宮川朝市が出てくるが、宮川沿いをストリートビューで見るとそれっぽい場所はない(けど川や景色はそれっぽい)(特に橋がない)。
新しくできたのか?と思い「宮川朝市 橋 工事」で調べるとドンピシャで「行神橋」が出てくる。あとは景色と川の石などを合わせてAC。
この罠に引っかかった人もいたらしく、すぐにストリートビューが古い可能性に気付けたのは良かった。(まあ橋とか街灯とか明らかに新しかったしね)

ととりにゃあがくそなぞなぞを埋める。(けどRがアツかったので正直どうでも良くなっていた)
f:id:qlethon:20200923042000p:plain

朝市なんだからホテルも近くだろうと思い「飛騨高山 ホテル 二段ベッド」で独房っぽい似てるベッドを画像から探すと、スーパーホテル飛騨・高山がそのままの画像を上げていた。楽天トラベル助かる。
f:id:qlethon:20200923042108p:plain

f:id:qlethon:20200923042207p:plain
2そのまま

これは2
https://pbs.twimg.com/media/EifAxN1UwAAU7Zp?format=jpg&name=large

いつの間にかコンテストが終わるまで3時間となっていて、最終画像が上げられていた(9,10)。簡単そうなので飛ばす。
f:id:qlethon:20200923042420p:plain

頑張って川を上っていると、画像1にある例の駐車場マークを発見する。位置を調整してAC。
f:id:qlethon:20200923042555p:plain

1-8の中で残るは4のみだが、これがかなり辛かった。朝市の帰りに近くで撮ったことは分かるが、高山までの道のりを見ても、周辺を探してもなかなか見つからない。そもそも川と違い道は無限にあるのでかなり辛かった。というか酔った。
f:id:qlethon:20200923042714p:plain

諦めて9,10をやる。2秒でAC。簡単すぎる。
f:id:qlethon:20200923042915p:plain

ととりにゃあがincludeできなくて積んでいた。それっぽい記事を貼るが、よく見てない。どうだったんだろう。
f:id:qlethon:20200923043026p:plain

4が本当に辛くて、泣きそう(吐きそう)になっていた。
f:id:qlethon:20200923043130p:plain

画像に電柱が写ってないから無電柱化されてる区画かな〜と思いぐぐってみると一番に大新町1丁目が出てくる。でもそれっぽい場所はない。よく調べてみると、高山市は多くの区域が無電柱化されているようだった。詰んだ。
吐きながら高山駅までの道を何度も辿ったり、赤い建物を探すもまったく見つからず。側溝を頼りに半ば諦めながらストリートビューで徘徊していると、突然見たことのある赤い建物が出てきた。めちゃくちゃテンションが上がった(n回目)。位置を調整してAC。

f:id:qlethon:20200923043704p:plain
Rが終わった瞬間テキトーなことを言い出す

tozanさんのツイートでQも同系統なことを知る。泣いて喜んだ。

ととりにゃあがSをAC。
f:id:qlethon:20200923043902p:plain

Qは簡単なやつを4問取って終了。2,4,5,9を解いた。順番は4→2→5→9

  • 2: どう見ても南の島なのでGoogle Mapsで空港にピンを立てて片っ端から見る
  • 4: どう見てもスカイツリー。影が写ってるのはtozanさんのツイートを見るまで気が付かなかった。
  • 5: 荒れ果てた島。「日本 無人」とかで画像検索したら出てきた。
  • 9: 「日本 平らな島」とかで画像検索したら出てきた。

f:id:qlethon:20200923044402p:plain
お疲れ様でした

$\mathbb{Z}/p\mathbb{Z}$ での原始根を$O(\sqrt{p})$で求める

@square10011さんと@noshi91さんに教えてもらったので,メモ

方針

$2 \le k \lt p$をランダムに選んで,原始根がどうかを判定する.
1. p - 1を素因数分解 $O(\sqrt{p})$
2. p - 1の素因数$a_i$すべてに対して$k^{\frac{p - 1}{a_i}} \not\equiv 1 \pmod{p}$ならkは原始根 素因数の数を$d$とすると$O(d\log p)$
3. 原始根の数は$\phi(p - 1)$で,これはそんなに小さくならないから全体で$O(d\log p) + O(\sqrt{p}) = O(\sqrt{p})$

$p > 2$です.

正当性

2.について

$\mathbb{Z}/p\mathbb{Z}$での原始根は1つ以上存在する(原始根定理). そのうちの1つを$r$と置くと,$p$のすべての原始根は$rm (m \perp p - 1)$とかける. 逆に,原始根ではない$\mathbb{Z}/p\mathbb{Z}$の要素は$rm (m \mid p - 1)$とかける. よって,$k$が原始根でなければ,$a_i \cdot n = m$なる$a_i$が存在して, $$k^{\frac{p - 1}{a_i}} \equiv (r^{m})^\frac{p - 1}{a_i} \equiv r^{n(p - 1)} \pmod{p}$$ となる.

フェルマーの小定理から,$r^{p - 1} \equiv 1 \pmod{p}$だから, $$k^{\frac{p - 1}{a_i}} \equiv r^{n(p - 1)} \equiv 1 \pmod{p}$$ となる.

逆に,原始根であれば$m \not\equiv 0 \pmod{p}$,$\frac{p - 1}{a_i} \not\equiv 0 \pmod{p}$なので,原始根の定義($n \not\equiv 0 \pmod{p - 1} \Rightarrow rn \not\equiv 1 \pmod{p}$)から, $$k^{\frac{p - 1}{a_i}} \equiv r^{m\frac{p - 1}{a_i}} \not\equiv 1 \pmod{p}$$ となる.

3.について

正確なことは何もわからないが,wikipedea(ja/en)をみると,数分の一くらいはありそうな気がする. $\frac{6n2}{\pi2 \sigma(n)} \lt \phi(n)$らしく($\sigma(n)$は約数関数),$\sigma(n) < e^{\gamma}n\log \log n$らしいので,$\frac{6n}{\pi2 e^{\gamma}\log \log n}$.よって,原始根を見つけるまでにかかる判定の回数の期待値の下限は,$\frac{\pi2 e^{\gamma}\log \log n}{6}$.なので,乱択パートには$O(d\log p\log \log p) = O((\log p)2\log \log p)$くらいかかりそう.しかし結局は前処理の素因数分解が支配的で,全体として$O(\sqrt{p})$

ちなみに,$e^{\gamma} \approx 1.78$,$\log \log (10^{18}) \approx 3.72$なので,$n = 10^{18}$のときでも$\frac{\pi2 e^{\gamma}\log \log n}{6} \approx 10.54$で,実質定数!w