イノたまごラボ・あのぶる の「こんなの作ったよ!」

「イノたまごラボ」はひとり同人サークルのようなものです。今のところ同人誌は作っていませんが、ソフトウェアからイベントまで、心惹かれたものを細々と。

1日1ACチャレンジ 2022-08-14の週

ルール(?)

  • AtCoder ProblemsでRecommendされた問題のうち、Moderate以上の難易度*1のものを1問以上解く
  • 日曜日スタート、土曜日はABCがあるので基本お休み(3ACできるよね、という自分への圧)
  • 眠さに負けてStreakが切れてもめげない。また次の日やればいいじゃないの精神

今週のおすすめレート: 692

要するに日曜に問題を解こうとしたらリストの一番上にあった問題のレート(自分のレートに依存するのでABCにRatedで参加する度に変わるはず)

土曜のABC264でRated参加10回目にして初4完🎉🎉🎉

既に緑目指したくなっているのでこの調子でぼちぼちやっていこうと思います。問題見る感じ緑くらいまでは地道にやっていけばリアリティあると思うんだよなー、水色はちょっと頑張らないといけない感じがするけど。(まだ解説でUnion-Findっていう文字を見てそっ閉じするくらいだし)

やった問題

2022/08/14

眠すぎてできませんでした😇

2022/08/15

熱中症がヤバくて出来ませんでした😇

2022/08/16

😇

2022/08/17

atcoder.jp

  • 自力AC? 🙅
  • 所要時間: 1時間20分

3日間のサボり休憩を経てようやく今週の1問目はRubyだと典型的に不利な問題。 走査範囲の調整が出来そうで出来なくて多分1時間くらいかけてそこそこ納得いくコードがTLE起こしたところで解説を読む。が、説明されていた解法がまんまこの時点での暫定解答コードだったので困惑しつつRubyのACコードを読む。

TLEを解消した差分はこんな感じ。

github.com

多分この辺の調整をしてやっとACする感じ。Rubyの良さが潰れてしまっているのはルールなのでしかたない……

  • 平方根・立方根をあらかじめ出すのではなくて二乗・三乗したものを都度nと比較していく
    • 都合、Range#eachが使えなくなる
    • べき乗の演算子も使うとなんか時間がかかる
  • Floatの計算は最小限にする
    • ループ1回ごとに2回やってたのを1回にするだけでそれなりに違うっぽい

2022/08/18

atcoder.jp

  • 自力AC? 🙅
  • 所要時間: 30分

23分やってみて諦め、解説読んで追加7分。 最初は変に凝って渦巻状に値を埋めてみてダメだったものの、なんか数学的にうまいことやるというよりはほどよく値をばらけさせるのにどうしたらいいかを考える感じ。

ちなみにそういうことなら案外ランダムに値を作ってやってもうまくいくんじゃないかと思って試したら普通にダメでした。

2022/08/19

atcoder.jp

  • 自力AC? 🙅
  • 所要時間: 44分

C++だとどうやらO(N3)のごり押しで行けるらしい、解説読んでちょっとビビった。 さすがにRubyではそこまでのゴリ押しは厳しくcombination作ったりなんだりと一通り迷走して、2辺を全探索しつつ3辺目は久しぶりの二分探索でAC。

使える道具が少なかった始めたての頃の方がむしろこういうのサクッと解けてそう。

2022/08/20

atcoder.jp

  • 自力AC? 🙅
  • 所要時間: 1時間5分

ARCだったので今日も1問、と意気込んだものの1時間弱TLEと闘った末にギブアップ、そのあと解説読みつつ7分でAC。 2人が落ち合う場所っていうかcからdへのhop数が偶数か奇数かで決まるよね、というところまではすぐに分かったものの、適当なところから1回だけ全走査して2つに塗り分けるだけで全部解決するとは思わなかった……

っていうか今週自力AC全滅なのね、手も足も出ないとかではなくTLEで諦めてるパターンなのであんまり気にしてないけど、この辺がいまの限界って感じ?

*1:もしくはそれに近い難易度