久しぶりのAtCoder Beginner Contetだったが、全然だめ。TLEとうまく頭の中で条件分岐できず、C, Dを解けず終了。 内容 結果 どう考えたか + α A - Air Conditioner B - Distance C - Repsept D - Alter Altar おわりに 内容 Python3でやっている。 参加ログ…

木グラフにおける辺彩色の問題。色分けに必要な最小な色数とその例をだす必要があるので、色分けの仕方をきちんと書き上げる必要がある。 DFSとBFSの違いを理解した状態で取り組んだので形式的だが、どちらもdequeを使ってやってみた。 目次 目次 概要 解く…

ナイトのコマがある動きをするときに、目的の場所にたどり着けるかどうかという問題。連立方程式も使うし、高速にを計算する必要もある。結構内容としては盛りだくさんで難しい。久しぶりにモジュラ逆数について考えたので軽くまとめた。 概要 解くときに考…

単純に計算すると計算量多すぎるので、桁の条件を詰めつつ最大値を求める方法と二分探索がある。 目次 目次 概要 解くときに考えた内容 コード 条件を満たす最大の桁におけるを計算 二分探索 概要 問題 の整数を買いたい。 買うには、円必要。（はの桁数） …

当たり前だが、安い時に買って、高い時に売ればいいっていうのを実装する。条件的にはその時点で所持する金と株の範囲内で１日に何回でも売り買いができるので、翌日上がる時に買えるだけ買って、翌日上がらないなら全部売るを常に繰り返せばいい。 こんな能…

結構単純。回テストがあって、頭から個ぶんたまったら、累積積（総乗）をずらしながら考える。 この時のポイントは、出と入の大小関係できまるので実際に総乗を計算する必要はないということ。（出と入については後述する。）解説は出と入の割合を計算してい…

M-SOLUTIONSが主催する個人戦のプログラミングコンテストに参加した。前回に引き続き、企業主催のコンテストに参戦。 何回かペナルティーがあったがABCDまで解けた 内容 結果 どう考えたか + α A - Kyu in AtCoder B - Magic 2 C - Marks D - Road to Millio…

街が個あるので全部パターン数えていると計算量が大きくなってしまう。最終的に平均の距離を出すのでそこも合わせて工夫する 概要 解くときに考えた内容 コード 愚直に、全経路パターンの和を出す方法 各街同士の距離の和を出して、重複回数をかける方法 概…

このコンテストのA, Bは九九の問題であった。この問題はそれを制約の範囲でかなり大きい表をイメージする。 がと大きいので工夫して探索 概要 解くときに考えた内容 コード 概要 問題 九九のようにのマスがある。 そのマスの値はである。 2以上の1つ整数を与…

同じ文字をグループとして捉えてその切れ目を数える 概要 解くときに考えた内容 コード 概要 問題 文字列が与えられる。 例えばaabbbbaacaであれば、[aa][bbb][aa][c][a]のように隣接する文字が同じ場合は一つのグループとする。（問題的にはスライム） 最終…

半公倍数って初めて聞いた。 まぁ定義に従って計算する。 ぱっと見、複数の値に対する最小公倍数を使うんだろうな。 結果的に、最小公倍数を計算しきってから大きさの判定をしていたせいで、一部REが発生していて、そこが原因と気付かず、ひたすら原因究明の…

公約数と互いに素の問題 概要 解くときに考えた内容 素因数分解 コード 概要 問題 1以上の2つの整数を与えるので、公約数からいくつか選ぶ。 ただし、選んだもののどの2組も互いに素である必要がある。 最大いくつ選ぶことができる？ 解くときに考えた内容 …

Cにしては簡単な全探索だった。なのに変なやり方でやってしまった・・・ 概要 制約 解くときに考えた内容 コード 変なやり方でやってしまった・・・ 素直にやればこうだった。 概要 問題 は以下を満たすの組の数である。 整数nを与えるのでf(1), f(2) ... f(…

AISing Ltd.が主催する個人戦のプログラミングコンテストに参加した。企業主催のコンテストは初めて参戦。 DがTLEで死んだが、まぁ今の自分の感じではこんなもんだろう。 内容 結果 どう考えたか + α A - Number of Multiples B - An Odd Problem C - XYZ Tr…

インデックスをいい感じにずらして考えられるかの問題 こういう問題を逆順列を求める問題というらしい 概要 解くときに考えた内容 コード 概要 問題 出席番号の人が来たときの自分を含めている人数を与えられる。 どういう順番で来たのかを出席番号で答えら…

どういう時に最大値を取るのかがわかれば、実装自体は簡単 概要 解くときに考えた内容 コードに起こす時のポイント コード 概要 問題 人ユーザーがいる。 はi番目のユーザーのフレンドリーさ。 円陣をつくる。 円陣を作った時に両隣のユーザーのうちフレンド…

bit全探索をマス目に対して行う。行と列に対してbit全探索をするのでネストが深くなる。bit演算子に慣れていないとコード自体がよくわからんので、そこらへんもまとめる。さらに、itertoolsでbitの列挙はできるのでそれもやる。 概要 解くときに考えた内容 b…

内容 結果 どう考えたか + α A - Payment B - Judge Status Summary C - H and V D - Chat in a Circle おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト後に解説をみたり、少し整理したりしたくらいの内容…

リスト内のmaxの値が必要なパターン。 これをそのままやらずに、優先度付キューを使う。 Pythonのheapqは最小値をpopするので注意。 概要 解くときに考えた内容 コード 概要 問題 個商品がある。 枚商品券がある。 円の商品に商品券を枚使うと商品の値段が（…

カウントした値を持ってからクエリを処理する系っていうパターン。 別の方法もある。先に持ち点から全クエリ分引き算しておいて正解したら足す。 概要 解くときに考えた内容 コード 概要 問題 ・最初の時点で全員ポイントもっている。 ・回クイズを行って、…

いい感じに約数の個数を数える必要がある。 概要 解くときに考えた内容 N基準の約数表を考える 約数基準の約数表を考える（定数倍の考え方） 定数倍であることから等差数列の和と考える コード 概要 問題 正整数が与えられる。 の約数の個数をとする。 を か…

コンテストの最中は、探索するというか貪欲的に求めると勘違いしてしまった。heapqとdequeを駆使してごちゃごちゃやったが条件を詰められず。 けんちょんさんがこの問題は、しゃくとり法や累積和 +二分探索で考えたということをTweetされていたので、２つと…

内容 結果 どう考えたか + α A - Calc B - Minor Change C - Tsundoku D - Sum of Divisors おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト後に解説をみたり、少し整理したりしたくらいの内容。 問題の詳…

はじめに ローカルでサンプルのテスト環境の準備は以前行った。 blacktanktop.hatenablog.com ただ、実際に競技プログラミングのコードを始めて、一番最初に戸惑ったのは 標準入力からデータを受け取ること 答えができたけどうまく出力する必要があること 基…

内容 結果 どう考えたか + α A - αlphabet B - Mix Juice C - One Quadrillion and One Dalmatians D - Replacing おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト後に解説をみたり、少し整理したりしたく…

はじめに 競プロをAtCoderやAizu Online Judgeから始める際に筆者はPythonでやりたいので、過去問を解くときに、問題に用意されているサンプルのテストや自分自身で考えたサンプルををいい感じにやるローカル環境が作りたかったのでそれらの備忘録。 モチベ…

昔からやってみたいと思ってて、先々週思い立ったタイミングがちょうどコンテスト当日だったので、先々週のAtCoder Beginner Contest 169に参加してみた。 atcoder.jp とりあえず初心者用のコンテストってことだっていう認識だったんだけど結構難しい。アル…