APRIL18B VAIMIN : April Challenge 2018 Division 2 - Vaibhav and Ministers

問題リンク https://www.codechef.com/APRIL18B/problems/VAIMIN 概要 組合せをO(1) で求められるように前計算をし、 障害点を考慮しながらゴールまでたどり着く経路の総数を求めます。 for 文DPで書き、 O( (p + q) log MOD + M^2 ) 考察 経路について repu…

AOJ 2511 : 沈みゆく島

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

YQL で html を読み込む方法が変わった(html table is no longer supported.)

algon-320.hatenablog.comid:algon-320 さんのウィジェットを使わせていただいて、 rating を取得していたのだけれど、ある日AtCoderのratingが 取得できなくなっていた。返ってきたjsonを見てみると html table is no longer supported. See https://polici…

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 2747 : カーテン

カーテン | Aizu Online Judge素直に実装しても良いが大変そう。 どうしても頂点の数に左右されてしまうので、 どうせだったら座標圧縮をして1x1の正方形について考える。 すると一気に楽になる。例えばサンプルケース3つ目(問題文に図として紹介されている…

AOJ 2631 : Clique Coloring

AOJ

Clique Coloring | Aizu Online Judgeなんとも微妙な方法で解いてしまった。まずaを降順にソートしておく。 前2つの要素においては(a[0] - 1) + (a[1] - 1) + 1個の点が どうしても必要になることが考えると分かる。 一番最初のサンプルのように、1つの頂点…

AOJ 2748 : 夏合宿の朝は早い

夏合宿の朝は早い | Aizu Online Judge確率は苦手…。システムの稼働率みたいに考えるのかなと思ったけど、 サンプルが単純な例で複雑なグラフになったとき結果がどうなるか分からず。 あきらめて解説を見る。2016/Practice/模擬国内予選B/講評 - ACM-ICPC Ja…

yukicoder No.528 : 10^9と10^9+7と回文

No.528 10^9と10^9+7と回文 - yukicoder愚直に頑張って数えました。文字列をs、長さをnとします。 前処理として、[1, n)桁までの回文数を数えます。 これは一番左の桁が[1, 10)、他が[0, 10)の個数を数えれば良いです。次にn桁ある場合、 左からi番目の桁がd…

AOJ 2612 : Phutball

Phutball | Aizu Online Judge状態数は少なそうなので普通にDFSをすれば良さそう。 同じ状態にたどり着くケースはなくはない。 少し心配なのでメモ化してみる(2^20 * 19 * 15)がMLE。 メモ化部分を消して提出する。WAは~?! 考えても分からなそうなので…

AOJ 2643 : AI

AI | Aizu Online Judge構文解析。ループの判定をどうするかだが、 命令のindex、x, y, 向いている方向を持てば良い。http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2360572#1横着してTreeSetで到達済みの状態を管理していたらTLE。 logはバカにな…

AOJ 2297 : Rectangular Stamps

Rectangular Stamps | Aizu Online Judge盤面の状態を2bit * 16の32bitで表現できるなあ、と考えたが 大きすぎてメモ化はできない。A*などで頑張るが無理。検索する。d.hatena.ne.jpああ~確かに1bitだけで十分だった。 そうすれば到達済みのところは行かな…

AOJ 2438 : YAML

YAML | Aizu Online Judge構文解析。一発とは行かず結構debugした。 debugの際、どこを今指しているかをビジュアライズすると楽。 例えばSample Input 1の場合 name: shimeji

AOJ 2425 : 全探索お姉さんの休日

A Holiday of Miss Brute Force | Aizu Online Judge最大何回無視すれば答えがわかるのか、tの上限は? などと考えて解けないと思っていた。しかしよく考えてみるとtは6で割った余りだけ保持していれば良いことに気づく。 ある場所にt%6で辿りついたとき、今…

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

codeforces.com A bの数列に出てくる数字の種類が2種類以上であれば答えはYes。 それ以外の場合、1種類の数字をaが0のところに置いてみて、 ソートした結果がaと異なればYes、同じだったらNo。http://codeforces.com/contest/814/submission/27633554 B 数列…

AOJ 1169 : 最強の呪文

The Most Powerful Spell | Aizu Online Judge嘘解法くさいです。ダイクストラに見えるけど違うのかな・・・? と思ったらダメになるケースがある。あらかじめ幅優先探索をして各ノードからゴールまでの最小文字列を求めておき、 これをヒューリスティックス…

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 ちょっと考えた。 一番…