ごりちゃんがゆく

競プロをするゴリラの精進記録

Python

ARC173-B Make Many Triangles の解法の思いつき方

コンテスト中解けるべきだったのに解けなかったので自戒を込めて記事にします atcoder.jp 問題概要 二次元平面上に相異なる個の点があるので、各点を回まで使って、三角形をできるだけ多く作ってください。何個作れますか? ぐらいです こう考えればよい! …

(Python/PyPy) LowLinkを非再帰で実装しました!

お気持ち Python で LowLinkを写経してACしようとしたらTLEしちゃったんですがググって出てきたやつは大体再帰で書かれていて、非再帰のLowLinkはざっとみた感じは見つからなかったので、非再帰で書いてみました! 非再帰なので、PyPyで高速に動作すると思い…

ABC334-B Christmas Trees を場合分けもできるだけ数学的な頭も使わない解き方を考えてみる

1日に2本も記事を書くなんて珍しいな! クリスマスイブだしな! ってなわけで書いてみる! 昨日の ABC334-B ですが、ABCのB問題にしては「数学」をしましょうって感じでつらかったと感じた人も多かったのではないでしょうか ゴリもそこそこ混乱しました そこ…

ABC330-E Mex and Update を無思考で解けるライブラリを書いた

ごり〜 こんばんは 先日のABC330-E を無思考で解けるライブラリを書いてみたので、紹介させていただきます! 問題概要は、 配列Aと、クエリとして i と x が与えられるので、 クエリのたびに A[i] を x に変更し、配列AのMEXを出力してください といったもの…

QuizKnockの鶴崎さんが解いていたパズルのプログラムを自分も書いてみた

QuizKnockのこちらの動画が競プロerの間で話題になっていましたね! まだ見てない方はご覧ください! 鶴崎さんはクイズ王しながら黄コーダーだったんですよね... やばすぎ 憧れます パズルの概要はこんな感じです! 3,4,7,8 を使って四則演算で 10を作れみた…

ABC307-C Ideal Sheet の激ヤバコーナーケース

ゴリはABC-Cが解けませんでした。ぐぬぬ atcoder.jp 問題概要 グリッドAとグリッドBを平行移動して重ねた結果、黒いマスがグリッドXと一致させることができるか? グリッドA,B,X の縦横の大きさは最大10。 最初考えた方針 (WA) 30*30 の領域を用意して、(10,…

ABC296-D M<=ab の解き方

先日コンテスト中に緑diffの問題が解けなくて悔しかったので、久々にブログ書いてみます! どういう思考をたどれば解けた可能性があるのか振り返っていきます。 問題概要 問題のリンク * 正整数 が与えられる。 * 以上 以下の整数 を選んだとき、の積が以上…

ARC111-A Simple Math 2

Simple (笑) とは... コンテスト中に解けなかったので、どうやったら自然に解けるようになるか整理してみます 問題リンク A - Simple Math 2 問題概要 を求めよ ( は の整数部分) M=10で題意を理解してみる まずは題意を感覚で理解しようとしてみます maspy …

Pythonで各要素にO(1)でランダムアクセスできるdeque(両端キュー)を書いてみた

表題の通りなのですが、まず何が嬉しいかを説明します Pythonで、from collections import deque とすると、 deque モジュールが使えます これは、両端キューと呼ばれていて、両端の要素への追加や取り出しがいずれもでできるリストのようなものです これは…

Pythonでheapqから大きい順に取り出したいときにもバグらせにくいやつを書いた

表題の通りです。 お気持ちを説明すると、ご存知 heapq は優先度付きキューと呼ばれていて、適当に要素を追加したり取り出したりしても常に取り出す値は最小を保っている便利なやつです。 しかも追加・取り出しはともにO(logN)でとても実用的! しかし欠点が…