んーなんかF,G,Hよりは本番中にできる可能性のある問題だったなぁ。 今回も解説スライドがわかりやすいのでみちくり。 座標が1e9までだが、高さの上下関係しか興味がないから1~Nに落とせる。 最終的にvの高さを超えるものは根本で切れ！ つまり求めるのは0->…

なるほどーなるほどなるほど。 chokudaiさんがトークセッションで言ってたように、やっぱり必ずグラフというのは疑ったほうがいいですね。 これをdpで解こうとしていた自分が悲しくなります。それにしてもCodeFestival解説がとてもわかりやすいのですべてそ…

むーーーこれは難しい。 Euler Tourという考え方で、行きがけ順の配列で木を表すというもの。 まぁそれをもとに今度は木を構成しなおすという話だが、解説スライドでは木と森という考え方を使っている。 実際にはまぁ仮想的な根を考えることで木の考え方だけ…

CodeFestival本戦行ってきました… んーなんというか、まぁ普通に本戦5問解いて、他も無難な感じで、実力相応という感じでした。 ただ、あんなにオタクたちが集まってる中で、みんな知り合いとしかしゃべろうとしませんよね。 "繋がる"とか言ってた割には知ら…

発想が思いついたのは良かった。ただ、実装が…この問題って、単純に前から走査して最終的な部屋割り、また、各々が部屋に入るとき、何人部屋に入るかを知ることができる。 そうしたら最終的な部屋割りから最初の方に向かっていって走査していく。 そのときに…

もとにある文字列でしりとりしていくゲーム。足りない単語数は？というのが問題(適当)今回、単語の最初と最後を使ってグラフを作るというのはすぐに気づいた。 問題はこれを一筆書きするのだが、オイラー閉路なんてもの知らなかった…これめっちゃ有名なやつ…

考え方は簡単。というより一瞬で気づいた。 ただ、この問題、二重辺連結成分分解、まぁつまり橋の検出と、LowestCommonAncesterの実装をしないといけないのでライブラリとか持ってないと地獄…つらかった…。 まず、a,b,cという始点,中継点,終点が与えられたと…

これは難しい…難しすぎる…1e6オーダーの家に1e3オーダーの家族(1~100人)を適当に入れて、住民の距離(任意の二人の組み合わせの距離の総和)をMAXにせよ、という問題。スライドが神がかるほどわかりやすいのでこれだけ見ればおｋ AtCoder Regular Contest 043 …

今までで一番WAを出したかもしれない…つらい…ある数列A,Bが与えられて、それらから転倒距離が同じになる数列Cを出力する問題。今回はバブルソートと関連づけられるが、あまりバブルソートのイメージで数字の大小を考えるとすごいわかりづらくなる気がする…。…

ちょっとずつ残ってるD問題を潰していきますね。1~25の数字が5x5のマスに並んでいて(0で少し隠れている)、それから連続する3つをとってきたときに昇順または降順にならないように0で隠れているところを埋める方法が何通りあるかを計算する問題 難しい…でも気…

難しかったが解説を見ればまぁギリギリ理解できた。 参考にしたのは AtCoder Regular Contest 045 解説 と 橋と関節点, lowlink - Lilliput Stepsxy座標系に点が奇数個あって、それらはxまたはyが同じ座標なら仲良くなれて、ちゃんと全員ふたり組にできるか…

もう毎回忘れてほとんど使えないのでメモ lower_boundはvalue以上で最初のiteratorを返す upper_boundはvalueより大きい最初のiteratorを返す binary_searchはvalueがあるかどうかを返す; どれもソート済みに使ってね。最後に比較関数を入れたsampleを貼って…

久しぶりに問題解いた気がする。 a xor b = cのとき、a xor c = bであることを使うとまぁ簡単にいく。 と思いきや、オーバーフローで2つほど落ちてた。はぁ。 vector<P> G[100001]; map<ll, ll> mp; void dfs(int now, int pre, int cost) { mp[cost]++; for(auto v : G</ll,></p>…

すごい面白い問題だった。 ビームがx, y方向に打たれるので頑張って最小の動きで逃げようという問題。 ビームがx方向に打たれるものとy方向に打たれるものがあるが、結局動きのコストはマンハッタン距離なのでx,y独立に考えてもいいよね、というのが根幹とな…

うーむ くだらないミスを2つしていて随分と時間がかかってしまった…解き方は簡単で、グラフと言えども、距離順に上から決めてしまえばよい。 同じ距離の頂点に関しては結んでも結ばなくてもよい。(ここの式が少し間違ってて悩んだ) あと、無意味にmapを使っ…

久しぶりに暇だったのでやってみた。 桁DPなるものを初めてやったのでメモdigitDPはこのサイトが驚くほどわかりやすいtatanaideyo.hatenablog.com考え方はいわゆるdigitDP dpの配列を、dp[何桁目を見ているか][今見ている桁までで1が何回出ているか(桁の数以…

M,+,-の3文字の列が与えられて、Mごとに数直線上のどちらかに移動し、+,-で点数を+,-していく。最後に原点に戻ってくる条件の元、最大の点数を考える問題。dpは一瞬で思いついたけど、それじゃあ絶対len(S) == 1e5という制約は満たせないのは明らかだった。…

天下一プログラマーコンテスト予選A、難しすぎて意味がわからなかった。 ただ、この問題は気づけば一瞬で解けるので、発想が出なかったのが悔しい。高さH, 横Wの白と黒で表された絵、A,Bがあり、Aの一個の白or黒を反転させる、または隣り合った白と黒を交換…

幾何系の問題。線分がいっぱいあってそれを原点から半直線で全て貫くときの最小の貫く回数を求める。 端点だけ考えればいいというのはこういう問題の常套手段。 角度でソートしてあげてあとはなるべくたくさん貫くように貪欲に。 ただ、貫きをはじめる場所に…

天下一プログラマーコンテスト2015の予選がもうすぐだったので練習がてらやってみました。 C問題以降はどれも難しかったし、解説なかったから辛かったですね…。文字列に'*'が入った集合がわたされて、それらを全て満たす最小の集合の大きさを求める問題です…

これはできなかったのが悔やまれる…。 N人(身長がバラバラ)が並んでいて、i人目に関して、その人が前を見た時に見える人の数を出力する問題。問題を簡単化する。 普通に考えるとi人目に関して、それより前のj人目を見て、そのiとjの間に二人より大きな人が存…

ある文字列を作るために回文を組み合わせるのだが、その回文の長さに応じてコストがあり、そのうちで最小コストの組み合わせをもとめる問題。普通にやるとdpでO(N^3)。 その文字列が回文であるかどうかを判定するテーブルを、文字列のcenterから広げていくや…

多分自分初めてリアクティブ形式の問題やりました。すごいデバッグしづらい…。問題は、50個以内の頂点がある木(辺はわからない)を与えられるので、100回以内の質問(こことここの長さは？)で木の直径を出力せよ、という問題。いや木の直径の求め方なんて知ら…

1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数を求める問題。 これって冷静に考えれば重複組み合わせだからcombination(n+k-1, k-1)じゃん… なんかちょっとむずかしいことしてみたけど結局求めているものは一緒です…はぁ… const ll mod = (ll)1e…

最短経路の組み合わせの数を求める問題。 完全に発想が凝り固まっててすごい時間がかかった…。頭の中で考えてるうちは、普通に始点からつながっているところの組み合わせを更新していくだけじゃ無駄に数えてしまいそうだなぁとか考えていたけど、手を動かし…

dpなんだけど、かなり上手くやらないとTLEする難しい問題。dpは現在の状態を上手く簡単に表すことでいろんな場合を統合して扱うものなので、今回も現在の状態をより簡単に表す方法を探さないといけない。'0'を-1, '1'を+1としてグラフにして見ると、これって…

初期点群が与えられ、平行移動、回転、拡大をしたあとの最終点群が与えられたときの拡大率を求める問題。最近、こういう問題にはこれを考える。こういう問題にはこういうアプローチが多い。みたいに頭の中でカテゴリ化していた自分としてはイレギュラーで、…

風船が上がっていくのを撃ち落としてなるべく撃ち落す風船の最大の高さが最小になるようにする問題最近こういう問題多く見る気がする。 最大、最小を求める系の問題である程度値が大きくて時間足りないよぉ> ある高さ以内で撃ち落とせるかを判定して、それを…

盤面のある行とある列を足してKとなる組み合わせの数を出力する問題。 すごい簡単そうなんだけど、普通にやろうとするとO(R*C)でR,Cが10^5なのでTLE どう考えるかというと、盤面ではなくて、飴のあるマスに関してだけ注意を配る。 単純に足し合わせがKになる…

頂点1からその頂点にもどるとき、同じ道を使わない最短経路の最小コストを出力する問題。ダイクストラとかを変形して使えないかなぁと考えたけど無理。 なんとかして最短経路問題に落ち着かせられないか。頂点0に直接つながっている頂点を2つ選んで、その2つ…