問題文読んで自分なりに考えてみたが、解説みたらシンプル過ぎで驚き。 atcoder.jp 解法 はまやんさんの解説より引用。 この問題はある種の構築問題である。 構築問題の典型テクとして「理論値の最大値を実はいつも達成可能」というのがある。 今回もそうで…

atcoder.jp 解法 各条件について考えてみる。 これを満たす数列の個数(ア) = 10N なるが存在する(イ)。 これを満たす数列の個数 = 10N - 9N 9Nはを満たす個数 なるが存在する(ウ)。 これを満たす数列の個数 = 10N - 9N 9Nはを満たす個数 abc178_c 問題の答え…

atcoder.jp 解法 問題文より 行を何行か選び (0行でもよい)、列を何列か選ぶ (0列でもよい)なので、選ぶ行は何行でも自由に選択できる。 1 <= H, W <= 6 なので、最大でも212 = 4096通り。 bit全探索で総当たりをかけて、答えを求める。 実装 参考 blog.hama…

ABCのD問題に高難易度問題が突如あらわれ、コンテスト参加者をザワつかせたこの問題。 多分にもれず、ワタクシも解けてませんが勉強として、解説みてやってみました。 解法 色々な解法が紹介されてますが、一番シンプルと思われる公式解説で説明されている方…

閉区間、半開区間、開区間の問題。 コンテスト中に書いたコードが、なんだか答えあわない。 「あれー？なんで？」 と思ってたらコンテスト終了。 解説みて原因知る。 あー、もーガッカリ。 D問題やろうとしたのも時間足りなくなってしもうたなー。 まぁ、し…

問題概要 atcoder.jp 解法 公式解説には、３の倍数に関する色々な考察が書いてある。 数十行にわたって難しそうなことが延々かいてあるのだが、最後の１行で驚きのどんでん返し。 Nが18桁しかないので消す桁を2進数を使って全探索でも解けます えー！それな…

AtCoder ProblemsにRecommendationって機能あって、ユーザことにオススメの難易度の問題を勧めてくれるんですよね(Atcoder Problems -> User -> Recommendation)。 茶diffやるべきだろうなと思ってたら、見事に茶の問題ばかり勧められるので、素直にやってき…

ABC206でできなかった問題をやってみる。 atcoder.jp 解説 はまやんさん解説、snukeさん放送を参考に、Union Findで解くパターンでやってみる。 入力例１の数列にUnion Findをかけて木構造を作ると次のような木構造ができる。 ABC206D 入力例1 要素は2, 3, 5…

AtCoder Problemsが茶diffと判定した問題から重点的にやっておこう。 という方針を立てました。 このレベル帯の問題が出来ないことが多いと感じるんですよ。 問題に書いてある通りに実装するとTLEで、実は数学的に計算量減らせますよ。 系の問題が多い、この…

素数系の問題っていうのがAtCoderであるみたいで、やったことないので探してやってみました。 atcoder.jp Python ACコード 基本はまやん氏の解法のコードを元にPythonで実装しました。 blog.hamayanhamayan.com エラトステネスのふるいで10**5以下の素数を、…

AtCoderで解説されてる想定解答を実装してみました。 しかしコレ、難しくない？これ茶色diffかー？ でも正解者多いから、そんなもんかなー。 atcoder.jp 想定解答の内容 AtCoder ABC205 D 入力例1の内容を元に、想定解答の内容をまとめてみました。 Aのいず…

ABC205やったらD問題でハマり。 atcoder.jp 制約が 1 ≤ AN ≤ 「こんなデカい数字なら二分探索だろ？きっと」 と二分探索で実装してみるもACならず。 「二分探索で解くでも充分高速だからイケる」 とコンテスト終了後、解説を読んだところ書いてあった。 「え…

全点対間最短路問題フロイド・ワーシャル法で解ける問題に挑戦してみました。 atcoder.jp 書いたPythonコード n_knuuさんのscipyで書かれたACコードを元に勉強がてら。 これコード見ても、何気にムズイ感じがする。 L以下の経路をばっさり切ってbooleanに変…

scipyが気に入ったので、scipyの別アルゴリズムで解ける問題を順次やっていきます。 atcoder.jp Pythonコード 解説で説明されている実装を、キレイにscipyのmaximum_flowで実装しているn_knuuさんのコードがあったので、それを元に書く。 まぁ、ほぼ一緒だけ…

scipyのダイクストラの使い方を覚えたので、ダイクストラで解けるAtCoderの別問題に挑戦してみました。 atcoder.jp 書いたPythonコード return_predecessors = True で経路が返ってくる (デフォルトはFalse) とのことで、これをつけてdijkstraを呼び出し。 i…

最短経路問題はAtCoderで良く出てますが、まだ解いたことないのでやってみることにしました。 まずは代表的な最短経路問題用アルゴリズムであるダイクストラ法から解いてみようと。 しかし、最近のAtCoderの問題だとだいぶヒネリが効いてるだろう。 なるべく…

問題概要 N 個の料理があり，それぞれ作るためにオーブンを使う時間はTiである。2つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か。 1≤N≤100 0≤Ti≤103 atcoder.jp 実装方針 公式解説の説明がわかりやすい。 atcoder.jp 2つのオーブンのど…

TLE x 1 AtCoder ABC204に参加したところ、C問題がTLE1個とれず。 くー、C問題で引っかかるとはツライ！！ 何が原因だったのか検証してみます。 atcoder.jp 解説をよんでみると実装の方針はあってる DFSなりの探索アルゴリズムで探索実装せよとのことで、自…

コンテストで出来なかった問題を復習してみました。 atcoder.jp もっとも参考にした解説 この問題は、はまやんさんの解説が一番わかりやすいと感じたので、これをメインの参考に。 blog.hamayanhamayan.com 実装方針としては、動的計画法で解く問題とのこと…

Deep Dazeで生成してみた画像一覧。 Cyber Ninja - Generated by Deep Daze Cyber Ninja。 Space Sphinx Generated by Deep Daze Space Sphinx。 a pyramid made of ice Generated by Deep Daze a pyramid made of ice perfume dancing on the mars Generate…

コンテストでは出来なかった問題を復習してみます。 問題はこちら。 atcoder.jp AtCoder Liveの解説聞けば実装方針は理解できる youtu.be チェス版でコマを動かした結果、どういう結果の組み合わせがあり得るか？という問題。 問題を読む限りは、盤面のテー…

解きました。 答えを見て…… ……まぁまぁ、ワタクシも多分にもれず解けなかった90.8%側なわけですが、解答を見せてもらいながら復習してみました。 9.2%という数字は、A問題提出者8393人。 D問題正解者775人。 775 / 8393 = 9.2% という計算です。 こちらが、…