SRMの練習会に参加できなかったので後からひっそり練習しました。chokudaiさんの解説で有名な回ですね(僕はeasyしか知りませんでしたが)。問題:TopCoder Statistics - Problem Statement解法:やっぱりdiv1 medはたいてい2つくらい良い思いつきをしないと解け…

問題:Programming Problems and Competitions :: HackerRank解法:dp[n][mode] = (mode=1のとき,残り日数がn日のときに首輪をつけた小さいウサギが1匹いるときの首輪の付け方, mode=0のとき,残り日数がn日のときに首輪をつけていない小さいウサギが1匹いると…

UnKoder #03に参加。2完です。うーん。最近あんまり調子よくないですね。問題:Programming Problems and Competitions :: HackerRank解法:左側からのaの累乗の和と右側からのaの累乗の和が都会度の値となる。このように左側からの和と右側からの累乗の和を分…

Codeforces Round #300に参加。結果はBCD通しただけであんまりよくない。一応レート上がったけど。 戦略としてはあとEかFのどっちかも解くつもりだったけどDで時間食いすぎて間に合わなかった。問題:Problem - 538D - Codeforces解法:よく似た問題がこちら。…

方針は結構すぐ立ったけど実装にものすごく時間かかりました。問題:TopCoder Statistics - Problem Statement解法:写真を参照。 vとuが写真のような関係になっていれば(図にかかれている頂点は隣接している必要はない), (A)vの子でuに繋がっていないもののう…

TCO Round 1Bの練習です。easyは全探索するだけっぽいので省略。問題:TopCoder Statistics - Problem Statement解法:それぞれの人が見つかる確率を考える。ある人iが見つかるのは, プレイヤーが自力でaさんを見つける->bさんがaさんの情報で見つかる->cさん…

問題:D: Big Bang - AtCoder Beginner Contest 022 | AtCoder解法:問題のような変換をしても重心から最遠点までの距離の比はPのままであるのでそれを計算して比べる。 以下ソースコード const int MAXN = 100100; int Ax[MAXN], Ay[MAXN], Bx[MAXN], By[MAXN…

ABC #022に参加。途中で抜けたとはいえABしか解けなかったのはひどい。問題:C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder解法:0から出発して0に帰ってくるような閉路は, 0->a->...->b->0 というように0からaに出て行って何かを経由してからbに来…

前の記事(SRM 499 div1 med:WhiteSpaceEditing - mayoko’s diary)では貪欲法で解いてしまいましたがdpに慣れたほうが明らかに成績が安定するのでそっちも練習してみました。解法:topcoderの解説(Login - TopCoder Wiki)を参考にしました。 区間DPというDPを…

本番「あってる気がするけどどうなんでしょ」と思いながら出したら通った。このときはよく考えてなかったがこのコード考えを非常に簡潔にまとめていてすごい。dpでやった方が安定するよね。問題:TopCoder Statistics - Problem Statement解法:とりあえず10,2…

SRM練習会に参加。結果はeasyとmed通してgood job!という感じでした。なんか昔のSRMは今より簡単な気がするしhardにトライしてみるのもありかもしれないです。問題:TopCoder Statistics - Problem Statement解法:問題の性質上,同じ数を主張しているウサギは…

気づかなかった…問題:Programming Problems and Competitions :: HackerRank解法:例えばひとつの列で0のビンゴがあったとすると,もう1が行でビンゴを作ることはありえなくなる(下図(0列に0のビンゴができている)のようになるので)。 0111 0111 0111なので,ビ…

最初もっと高速なアルゴリズムにするつもりだったけど,なんかWAが出るので方針を変えた。問題:Programming Problems and Competitions :: HackerRank解法:メモ化再帰を使う。問題の性質上,パーティーに招待される動物は イヌ->ネコ->イヌ->ネコ->... ネコ->…

UnKoder #02に参加。コメントが日本語に入っていると提出不可能になることに気づかず提出ができませんでした。ただそのあと提出できるようになってからも結構試行錯誤があったのでもしかすると提出できても1完くらいしかできなかったかも。問題:Programming …

どうでもいいけど最近朝が早いせいでめっちゃ眠い。問題:No.189 SUPER HAPPY DAY - yukicoder解法:いわゆる桁DPを使う。dp[n][sum][flag] = (今n番目の数を見ていて,フラグ(まだ与えられた数そのままになる可能性があるか)がflagの状態になっていて和がsumに…

ぐぬぬ。性格悪い。問題:No.186 中華風 (Easy) - yukicoder解法:1つ目と2つ目を満たす制約を全探索で見つけ,それと3つ目を満たす制約を全探索で探す。性格悪いというのは正整数でないといけないということ。 0 2 0 3 0 5 という入力で0を出力するとWAです。 …

問題:TopCoder Statistics - Problem Statement解法:下の写真参考。各状態(1:1が上を向く 2:1が右を向く 3:1が奥を向く etc)からx方向,y方向に動かした時どう状態遷移するかを考える。最後に1になれば良いので,写真に書いてあるように赤,青,緑,橙のいずれか…

SRM 489の練習会に参加。結果はeasyだけ解いて(110ptくらい)うーんと言った感じです。なんか変わった問題(良い問題だとは思う)で慣れてないなぁと思いました。問題:TopCoder Statistics - Problem Statement解法:問題文の通り解釈してはいけない。実際にはど…

これも良い問題だよなぁ。こういうの解けるようになりたい。問題:TopCoder Statistics - Problem Statement解法:めぐるさんの説明(因幡めぐる@競技プログラミング(@meguru_comp)/2015年04月17日 - Twilog)が非常にわかりやすいのでそれを参考にしました。 以…

良い問題だなぁ。TopCoderのMedに出題されそう。問題:D: Chaotic Polygons - AtCoder Regular Contest 037 | AtCoder解法:kmjpさんの解法(AtCoder ARC #037 : D - Chaotic Polygons - kmjp's blog)を参考にしました。の定義の仕方は同じです。 とりあえず場…

ARC037に参加。Bでバグらせてちょっと時間食いましたがいつも通りCまで通してまぁOKという感じでした。「いつも通り」とか言ってるけど最近Cが簡単だからじゃないですかね…問題:C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder解法:まずAとBをソート…

本番TLEしたやつ。こういうの慣れてないのでこれから慣れていかないと。問題:Problem - F - Codeforces解法:全探索すると間に合わないのは明らかなので,いろいろと工夫する。 まず第一の工夫が,左右に分けて探索すること。これによって探索量が大幅に減る。 …

SRM 656に参加。結果は190ptくらいでeasyを提出できて自分にしては良い感じのスコアで終了。レーティングも1524と黄色に上がれて個人的な最低限の目標も達成できて結構嬉しいです。問題:後で貼ります解法:まず「i番目のケーキを選んだらもうi+1番目以降のケ…

考え方はあってたけどランクの実装でバグってた。問題:No.184 たのしい排他的論理和(HARD) - yukicoder解法:bit的な意味で線形独立なものの個数を考えれば良い。そのためにランクを計算することになるが,通常と比べてxor演算して0と1を入れ替えるだけなので…

Codeforces Round #298 (Div. 2)に参加しました。結果はABCDが通ってくれて,div2とはいえ20位という好順位をとれ結構満足でした。問題:Problem - 534D - Codeforces解法:戦略としては,たくさんの人と握手したと主張する人がなるべく矛盾しないようにするため…

典型っぽいけど解けてよかった。問題:TopCoder Statistics - Problem Statement解法:まず制約からなんとなくbitDPな感じがします。ということでbitDPに落とし込みたいんですが,よく考えるとあるところまで映画が眠ることなく見終わったとすると,その時のJohn…

SRM469の練習会に参加しました。結果としてはmedだけ通ってやっぱりそこそこといった結果でした。easyのミスはボケすぎな感じある…問題:TopCoder Statistics - Problem Statement解法:予約している人が誰もいなければn行おきにm-1通りの座り方があるのでn*(m…

多分本番中は問題分の意味がわからなかったと思うのでまぁやらなくてよかったかな。問題:TopCoder Statistics - Problem Statement解法:ホールの結婚定理というのがあるらしいです->(Hallの結婚定理とその証明 | 高校数学の美しい物語)。 この定理により,あ…

解説を読んで解いたんですが,さっき汚いコードと言ったコードは上手く書けば普通のコードになるっぽいですね。問題:TopCoder Statistics - Problem Statement解法:基本的にはさっきの(SRM 655 div2 hard:NineEasy - mayoko’s diary)に似ている。先程は各桁に…

こっちのほうがmedより難しくないですか…問題:TopCoder Statistics - Problem Statement解法:LからRのすべての数について,0〜9のどの数が現れるかをbitmaskで管理する。(例えば21という数は「1」「2」「1と2」という数が出現するのでbitでは2,4,6になる)で,…