競技プログラミング

ICPC 国内予選 2017 参加記

できるだけポエティックにならないように気を付けます… (が自分視点で展開しており十分ポエム)。 思うところは色々ありますが今までの日々は味のあるものだったので 日記として残しておきたいと思いました。 書いたあと見直しましたが酷いです。自戒。 概…

AOJ 2511 : 沈みゆく島

Sinking islands | Aizu Online Judge一番最初のサンプルケースを見ると、 沈む時刻が最後の方から最小全域木を構成していくと良さそう (座圧して、時刻が同じものはグルーピングしておく)。一番最初に沈むところまで終えて、 Union-Findが全部同じ親を持…

JOI 2012-2013 予選 問題4 : 暑い日々 (Hot days)

JOI 2012-2013 予選 問題4D: 暑い日々 (Hot days) - 第12回日本情報オリンピック 予選(オンライン) | AtCoderid:keidaroo さんのblogに触発されてどんなもんじゃろと解いてみました。 JOIの問題は解いたことがないので…。keidaroo.hatenablog.com 解い…

AOJ 2510 : 双子の読書感想文

Twin book report | Aizu Online JudgeDPだと思うけど大変そう。 最初rを2つ分けたときの大きいほうの最小値を求め、 余った時間に感想文を詰め込もうとしたが 無限にWAを重ねた。 半日頑張ってダメだったので諦めて解説を見る。2013/Practice/模擬国内予選/…

AOJ 2333 : 僕の友達は小さい

My friends are small | Aizu Online JudgeDPだろうなということは目星がつく。 ただ 僕は、入れられる友達がまだ残っている限り、入れるのを止めない。決して止めない。 この条件を満たすようにするにはどうするか を考える必要がある。ここで、リュックに…

AOJ 1196 : 橋の撤去

橋の撤去 | Aizu Online Judge ICPC諸島には島の数 n に対して n-1 個の橋があり,どの島から島へも, 橋を何回か渡れば到達することができるようになっている. つまり木になっている。それが分かればあとはやるだけとなる。 すべての頂点(島)を根と見な…

AOJ 1145 : 全宇宙生命ゲノムデータベース

The Genome Database of All Space Life | Aizu Online Judge構文解析の問題。 一つ困るのが繰り返しの処理。繰り返したときの文字列の長さを持っておいて、 それよりiが小さければ中の長さでmodを取って遷移し、 そうでないときはiから文字列の長さを引いて…

AOJ 2200 : Mr. リトー郵便局

Mr. Rito Post Office | Aizu Online Judge船をどこに置いておくかで結果が変わっておきそうなので、 これを状態に持ってDPするのが良さそう。あらかじめ陸路と海路で分けてワーシャルフロイド法で 各町村間の最短経路を求めておく。DPするときは船は放って…

AOJ 2444 : Substring

Substring | Aizu Online Judge制約がnもmも10^5あるので愚直解はまず通らなそう。 Suffix Arrayを合ってるか分からないけど言葉だけ思い出したが、 実装できる自信はない・・・。少し悩んだらローリングハッシュというものを思い出した。 前処理O(n)、区間…

AOJ 2441 : FizzBuzz

FizzBuzz | Aizu Online Judge大変そう・・・。問題を分割すると、 ある数字までのFizzBuzz String の長さを高速に計算する ↑の数字を[0, s)の間で二分探索 というところまで分かる。 なぜ二分探索が出てくるかというと、 ある数字までのFizzBuzz Stringの長…

AOJ 1157 : 大玉転がし

Roll-A-Big-Ball | Aizu Online Judge直方体を直方体の底面を表現する線分4つ(反時計回り)と高さhで表現する。コースも線分として捉えると、各直方体への距離が求めることができる。 このときの距離を d とすると、h >= d のとき、そこを通過できる最大半…

AOJ 1140 : Cleaning Robot

Cleaning Robot | Aizu Online Judge巡回セールスマンライクな問題。汚れの数が最大10なのでbitDPで解くことが予想できる。bitDPが分からない場合、以下の資料が大変参考になる。プログラミングコンテストでの動的計画法あらかじめ汚れにインデックスを振っ…

AOJ 1176 : 輪番停電計画

Planning Rolling Blackouts | Aizu Online Judgeまず長方形を考えたとき、全体の和 - 長方形内の値の和が 抑制需要になり、s - 抑制需要が予備力となる。 予備力が0より小さいときは、それ以上分割しても結果は同じなので、 遷移する必要はない。 2つに分割…

AOJ 2741 : インビジブル

インビジブル | Aizu Online Judgeゲーム系の問題。困るのはスタックで配列で持っていたりすると解けない。 しかしよく考えてみると「最後に-1を出したのはいつか」 を持てばスタックの状態を表現できる。 (これだけでは不十分で最後にパスしたインデックス…

Codeforces Round #380 (Div. 2) A B C D

codeforces.com A めっちゃ実装に時間がかかった。どう書けばスマートか分からない。 ogoにhitしたらgoが続くまでfor文内のindexを増やす方式にしてAC。Submission #22346247 - Codeforces B actorがいないマスで上下左右に一つでもactorがいればカウントア…

AtCoder Beginner Contest 023 C D

abc023.contest.atcoder.jp C 図に書いてみると、行と列にどれぐらい点があるか着目すればよさそう。 このとき、 i行にある点がc[i]個のとき、k-c[i]となる列の中から点そのものでない(クロスしたところ)を数える i行にある点がc[i]個のとき、k-c[i]+1とな…

AtCoder Beginner Contest 024 D : 動的計画法

D: 動的計画法 - AtCoder Beginner Contest 024 | AtCoderぼくも動的計画法好きだけれど解けなかった。 愛が足りない。 当初の方針 えーどうするんだろう。愚直にはできないし・・・。諦め 解法を見て はい。こういう風に式をいじくってみる心意気というか …

AtCoder Beginner Contest 024 A B C

abc024.contest.atcoder.jp A 一回割引なしで計算しておいて、 あとから割引適用できたらするSubmission #985021 - AtCoder Beginner Contest 024 | AtCoder B imos法Submission #985031 - AtCoder Beginner Contest 024 | AtCoder C ちょっと考えた。 一番…

AtCoder Beginner Contest 025 D : 25個の整数

abc025.contest.atcoder.jp 当初の方針 分からない・・・。 全体の数(0の数の階乗)からルール違反のものを引いていくのかな。 でも重複があるし、それを取り除けなさそう・・・。諦め 解説をみて 1から置いていく、という発想が大事だったっぽい。 すでに…

AtCoder Beginner Contest 025 A B C

abc025.contest.atcoder.jp総じて文章が長めだった。 A 全探索したものをリストにつめておき、 与えられたインデックスに含まれるものを返す。Submission #983773 - AtCoder Beginner Contest 025 | AtCoder B シミュレートする。Submission #983782 - AtCod…

Codeforces Round #379 (Div. 2) A B C D

codeforces.com A mapっぽいもの(int[256)を用意して数えて出力Submission #22227451 - Codeforces B 256を貪欲に選んだあと、残ったもので32を生成する。 怖いのでlongにした。Submission #22231261 - Codeforces C c, dが昇順になっているので、二分探索…

AtCoder Beginner Contest 026 D : 高橋君ボール1号

abc026.contest.atcoder.jp 当初の方針 単調な関数じゃないから、二分法は使えないだろうなあ。g(t) = f(t) - 100とおけば、0となる点を見つければ良さそう。 じゃあニュートン法だなWAは? なんで? サンプルすら合ってないし。 手元じゃ誤差は1e-12らしい…

AtCoder Beginner Contest 026 A B C

abc026.contest.atcoder.jp A 全探索Submission #983055 - AtCoder Beginner Contest 026 | AtCoder B 便宜上一番内側の半径を0とすると、 2ずつ飛んでいきながら i番目の円の面積 - i + 1番目の円の面積 を足していけばいい。Submission #983058 - AtCoder …

AtCoder Beginner Contest 027 D : ロボット

abc027.contest.atcoder.jp 当初の方針 DP解法はすぐに思いつく。でも満点解法はどうすれば・・・?いろいろ考察してみるが甲斐なし諦め 解説をみて >, 確かに。頭いいなあ。じゃあ>を選んだからそれより右側で 一番大きい Segment Treeかなあ。ソートするだ…

AtCoder Beginner Contest 027 : A B C

abc027.contest.atcoder.jpむずかしめに感じた A int cnt[11]のような配列を用意して cnt[ni()]++とする。したら配列に入っている奇数のときの インデックスが答えSubmission #960459 - AtCoder Beginner Contest 027 | AtCoder B 島の合計人数がsなら、 1つ…

yukicoder No.443 GCD of Permutation

嘘解法でコンテスト終了後に落ちました。 あとで書き直します。 何回か再提出したらACするクソ解法が出来上がりました。精神が不安定になるので放置します。 記事を消すのは卑怯な気がしたので、 歴史として残しておきます。

yukicoder No.442 和と積

No.442 和と積 - yukicoder 解法 BigIntegerを使うとgcdが使えて楽http://yukicoder.me/submissions/129409

yukicoder No.441 和か積

No.441 和か積 - yukicoder 解法 BigIntegerを使うと何も考えなくていいhttp://yukicoder.me/submissions/129392

DDCC2016 予選 A B C

ddcc2016-qual.contest.atcoder.jp A 問題文みて頭が真っ白になったが、冷静に考えたらkを求めればよかった。Submission #968467 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder B 言っていることがわからなかった。落ち着…

AtCoder Beginner Contest 028

abc028.contest.atcoder.jp恐ろしく簡単なセットだった。サンプルケースも確認しないで出したら 添え字のタイプミスでRE出してしまった。 A 授業でよくありそう。Submission #960426 - AtCoder Beginner Contest 028 | AtCoder B "ABCDE"のStringを持ってお…

AtCoder Beginner Contest 030 D : へんてこ辞書

abc030.contest.atcoder.jp 当初の方針 見たことある。arukuka.hatenablog.com置換の累乗を使うんだな!N log Kで死亡うーん、ループがあるのかなあ。 でも今の実装だとうまく書けないし・・・。諦め 解法を見て 落ち着いて考えてみれば、閉路でループするま…

AtCoder Beginner Contest 030 : A, B, C

AtCoder Beginner Contest 030 - AtCoder Beginner Contest 030 | AtCoder A 計算式通りに計算する。 doubleでやったらやばそうだけど、大丈夫だった。 絶対に通分したほうがいい。Submission #959910 - AtCoder Beginner Contest 030 | AtCoder B 360度のう…

AtCoder Beginner Contest 031

abc031.contest.atcoder.jp A 2通りを試して大きいほうを出力Submission #959337 - AtCoder Beginner Contest 031 | AtCoder B 場合分けを丁寧に書くSubmission #959348 - AtCoder Beginner Contest 031 | AtCoder C 青木くんが最善の手を尽くしたときの、高…

Codeforces Round #378 (Div. 2) A B C D

codeforces.com A 母音間の距離の最大値を求める。 初期indexを-1にして、末尾に番兵の'A'を置くと楽Submission #21920570 - Codeforces B 全体のsumを取っておいて、列iを右左入れ替えたときに 最大値を更新できるか舐めていく。Submission #21924549 - Cod…

AtCoder Beginner Contest 032

abc032.contest.atcoder.jp A 最小公倍数を求めて、n以上の倍数を出力Submission #959151 - AtCoder Beginner Contest 032 | AtCoder B setに突っ込んで、サイズ出力Submission #959158 - AtCoder Beginner Contest 032 | AtCoder C しゃくとり法。バグりや…

AtCoder Regular Contest 044 B : 最短路問題

arc044.contest.atcoder.jp 解法 まず、深さについて分けて考えると、 前段(個数n)と次段(個数m)の組み合わせの数について考える問題になる。前段は、完全グラフのように辺を取りうる。 その辺の中で自由に選んでいいので、となる。次段には、前段から辺…

AtCoder Regular Contest 044 A : 素数判定

arc044.contest.atcoder.jp 解法 言われた通りにやるだけ。なのに他の人の解答を見なければACできなかった。 最悪。Submission #958472 - AtCoder Regular Contest 044 | AtCoder2が素数じゃない扱いされるSubmission #958485 - AtCoder Regular Contest 044…

AtCoder Regular Contest 046 B : 石取り大作戦

arc046.contest.atcoder.jp 解法とその道のり どこかで見たことある問題だぞ・・・。arukuka.hatenablog.comでもそのときとは違って、変なルールがないし、 とる数がそれぞれ違うこともあり、 その数なんと10^9せっかく分けられているので、分けて考える。 A…

AtCoder Regular Contest 046 A : ゾロ目数

arc046.contest.atcoder.jp 解法 9ずつのループになっているので、 9で割った数(桁数) 9で割った余り(index) を用いると楽になる。1-indexed と 0-indexed の変換に注意して提出。Submission #958384 - AtCoder Regular Contest 046 | AtCoder

AtCoder Grand Contest 006 C : Rabbit Exercise

agc006.contest.atcoder.jp 当初の方針 えーわからん。 解説を見て 非常に丁寧に書かれている解説なので、 分かりやすかった。 行列累乗の要領で置換の累乗をすると ここがパッと分からなかった。 置換と置換の積は行列で表すと、置換の積このようになる。上…

AtCoder Regular Contest 048 B : AtCoderでじゃんけんを

arc048.contest.atcoder.jp 解法 ある意味、やるだけという問題。リストにレーティング、手をつっこむ。 同じレーティングの勝ち負けは、そのリストから サイズを取ってくるとして、時間がかかりそうなのは、 自分より低いレーティングの人の数 自分より高い…

AtCoder Regular Contest 048 A : 階段の下

arc048.contest.atcoder.jp 解法 引き算。a 0のケースは-1する。Submission #953048 - AtCoder Regular Contest 048 | AtCoder

AtCoder Grand Contest 006 A B

agc006.contest.atcoder.jp A 後ろからつなげられる数を見て 全探索Submission #953779 - AtCoder Grand Contest 006 | AtCoder B 10WAした。xを真ん中にして、x - 2, x + 1, x , x - 1x + 2, x - 1, x, x + 1にしてあげると、上にxの列が2列できて それが連…

AtCoder Regular Contest 049 B : 高橋ノルム君

arc049.contest.atcoder.jp 当初の方針 全然分からない・・・。 解法を見て 今さっき二分探索したのに、 なんで二分探索が思いつかないんだ・・・。Submission #951841 - AtCoder Regular Contest 049 | AtCoderはークソ

AtCoder Regular Contest 049 A : "強調"

arc049.contest.atcoder.jp 解法 for文で回して、iがABCDに一致したら ダブルクォーテーションを出力。 最後にダブルクォーテーションが来るケースに注意。Submission #951686 - AtCoder Regular Contest 049 | AtCoder

AtCoder Regular Contest 050 B : 花束

arc050.contest.atcoder.jp 当初の方針 分からない・・・。貪欲? → 違う諦め 解法を見て 頭いいなあ・・・。 俺はいつになったら頭よくなるんだ・・・。提出 → WA Submission #951662 - AtCoder Regular Contest 050 | AtCoder死。r - mid か b - midが負に…

AtCoder Regular Contest 050 A : 大文字と小文字

arc050.contest.atcoder.jp 解法 'A'との差分を取ってもいいが、 String にtoLowerCase関数があるので、 それを利用する。Submission #951641 - AtCoder Regular Contest 050 | AtCoder

AtCoder Regular Contest 051 B : 互除法

arc051.contest.atcoder.jp 当初の方針 ええ・・・分からない・・・。aをでかい数で固定してあげたら、 bを見るだけでいいのでは?Submission #951511 - AtCoder Regular Contest 051 | AtCoder→ K=30ぐらいまでが限界無理です。 解法を見て フィボナッチ数…

AtCoder Regular Contest 051 A : 塗り絵

arc051.contest.atcoder.jp 解法 円が長方形に内包されているかどうかは、 上下左右の点について、内包されているか チェックすればいい。長方形が円に内包されているかどうかは、 角の4点が円に内包されているか チェックすればいい。Submission #951238 - …

SRM 701 Div 2 Hard : ThueMorseGame

TopCoder Statistics - Problem Statement通せなくてめちゃくちゃ悔しい。 当初の解法 DPだなって思ってしまった。 public class ThueMorseGame { boolean[][] dp; boolean[][] done; int n; int m; public String get(int n, int m) { this.n = n; this.m =…