arc051.contest.atcoder.jp 解法 円が長方形に内包されているかどうかは、 上下左右の点について、内包されているか チェックすればいい。長方形が円に内包されているかどうかは、 角の4点が円に内包されているか チェックすればいい。Submission #951238 - …
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 =…
https://apps.topcoder.com/wiki/display/tc/SRM+701 Easy シミュレート public class SquareFreeString { public String isSquareFree(String s) { for (int i = 0; i < s.length(); ++i) { for (int j = 2; i + j <= s.length(); j += 2) { String left = …
arc052.contest.atcoder.jp 解法 典型的なRMQ問題（足すやつもMinimumっていうんでしょうか・・・）円錐を高さ1ごとにぶつ切りした体積を配列に持たせて、 それをSegmentTreeに入れてあげて更新作業をすれば、 あとはクエリーに答えていくだけ。計算量も事前…
arc052.contest.atcoder.jp 解法 数字の部分を取り出してくればよさそうなので、 JavaのStream機能を利用して解く。 String ans = sc.next().chars(). filter(a -> '0' <= a && a <= '9'). mapToObj(a -> Integer.toString(a - '0')). reduce("", String::co…
code-festival-2016-qualc.contest.atcoder.jp予選落ちたのが大変悔しかったので、 ちょっと背伸びして普段じゃ絶対に解けないだろう、 最後の問題を解いてみた。 当初の方針 ちんぷんかんぷん 解法を見て ？？？？自分に理解できるように噛み砕いていく。 …
code-festival-2016-qualc.contest.atcoder.jp 当初の方針 Cが解けなくてこちらに来る 部分点解法を狙おう うーん、O(H^4)にしかならない・・・ cost[i][y1][y2]はcost[i][y1-1][y2-1]の一番下しか違いがないことに気づく 再利用すればO(H^3)になるぞ でも実…
code-festival-2016-qualc.contest.atcoder.jp青木君が東からやってくるの見落として 問題の意味を理解するまでとても時間がかかった 当初の方針 意味分からん。間違いがあればどのデータも信用ならないし、 答えが出ないのでは？ 青木くんの存在に気づき、…
code-festival-2016-qualc.contest.atcoder.jpこの人の出す問題嫌いついでにいうと人柄も嫌い A 前からのCの位置と、後ろからのFの位置を取得してチェックSubmission #943435 - CODE FESTIVAL 2016 qual C | AtCoder B 紙に書いてみると、毎回前のとは違う、…
abc033.contest.atcoder.jp 当初の方針 幾何は苦手意識・・・。サンプルみたいに、直角と鋭角の数をカウントして、 全体から引けばいい？（うまくだまされました）グリッド上に配置されるから、直角になるには、 x座標かy座標かが一緒になる？ （大嘘。(0,0)…
abc033.contest.atcoder.jp A setに突っ込んで、1つだけかどうか判定Submission #937773 - AtCoder Beginner Contest 033 | AtCoder B 言われた通りにチェックSubmission #939333 - AtCoder Beginner Contest 033 | AtCoder C 一瞬「うげっ、構文解析？！」…
arc053.contest.atcoder.jp 解法 回文になるには、 偶数個のみで構成される文 偶数個と、1つの1文字で構成される文 であることが分かる。なので、まず文字ごとの出現回数をカウントし、 奇数を1と残った偶数に分解してあげる。 すると、1の個数と偶数の合計…
arc053.contest.atcoder.jp 解法 それぞれで、長さ-1コ分が連なっており、 重複はない。タテ：w * (h-1) [コ] ヨコ：h * (w-1) [コ]この2つを足せばいい。A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder
arc054.contest.atcoder.jp 解法までの道のり 二分探索？ → 普通に違う → やざてんさんより二分探索で解けるとご指摘いただきました！ ページ下部で補足します。 3 が入力されるケースで、1e-9刻みでやってみると、下に凸な関数であることが分かる 最急降下…
arc054.contest.atcoder.jp 解法 時計回りのときの距離は、c := (D - S + L) % L反時計回りのときの距離は、cc := (L - D + S + L) % Lで、それぞれX + Y[1/s]、Y - X[1/s]の速度で移動するので、 割って上げて、小さいほうを出力すればいい。X >= Y の場合…
arc055.contest.atcoder.jp 当初の方針 ちょっと前に友達と一緒に学校で解いていた思い出が蘇る。そのときはさっぱりで、解説放送を見てもさっぱり。今もさっぱり。 解説を読んで ？？？？？？コードが書けるようになるまで丸一日費やした。他のブログでは独…
arc057.contest.atcoder.jp 当初の方針 DP？ →考えたDP:dp[N][K] Kが10^9ほどあるので無理 先頭から最小の勝利数で勝率が上がるような貪欲？ 実装中に全部使い切らないと行けないケース （）でうまくいかない。 諦め 解法を読んで のケースは特殊化して省く…
arc057.contest.atcoder.jp 解法 K = 1のときは、n回試行するとになるので、 K >= 1のときは、シミュレーションしても間に合う（O(log 2兆)=12log 20）。K = 0のときは、n回試行すると、A + nになるので、 2兆円にするためには、2兆-A回試行する必要がある(O…
abc034.contest.atcoder.jp 当初の方針 DP？ でもwが大きいし・・・。分からない。 解説を読んで 二分探索。なるほど。その通りに実装してAC。Submission #935434 - AtCoder Beginner Contest 034 | AtCoderでも、なんでそれが正しいか分からない。 なぜ基準…
abc034.contest.atcoder.jp A 比較して出力Submission #935373 - AtCoder Beginner Contest 034 | AtCoder B 偶数の人は一つ手前の人と、奇数の人は一つ後の人とペアになる。Submission #935372 - AtCoder Beginner Contest 034 | AtCoder C 整数論を用いる…
解法までの道のり DPかな？ pを出す回数はたかだかn/2 ぎりぎり10^9を下回りACできそう 試しに配列を確保してみる → メモリエラー 他にいい方法がありそう。 ここまでで、サンプルケースを紙に書いてみる。gを出した回数だけpが使えるので、 pは最大n/2回（…
abc035.contest.atcoder.jp 当初の方針 満点解法を狙いにいく。結局、どこかの節に最短で行って、できるだけ長く居て、最短で戻ってくればいい。 途中で寄った先に居る必要はない。ダイクストラ法で1から各節まで、逆順のリンクから各節から1までの最短経路…
codeforces.com A kを足していって、10で割った余りが0かrになればいい。Submission #21523193 - Codeforces B 2つを足して、足りない分を後ろに足せばいい。n = 1のケースのときは、何もしなくていいらしい。これが分からない。出したやつがそういう実装に…
abc046.contest.atcoder.jp 当初の方針 ううーん、難しそうだけど、式変形していけば良さそう。・・・詳細は省くが、整数論を持ち出してやっている途中で、 が素数でないと成立しないことに気づく。何故なら、モジュロ演算を行うときに逆元が必要になるのだ…
abc046.contest.atcoder.jp間違えてABCに参加登録をしていたみたいで、 ARCに出られなかった。けど、Cが解けなかったのである意味助かった・・・。 Dまでくらい余裕で解けるようになりたいね。 A setに突っ込んで、sizeを出力Submission #928767 - AtCoder B…
abc035.contest.atcoder.jp A 幅を4で割ってみて、その商を使って高さを割って3かどうかチェックSubmission #924362 - AtCoder Beginner Contest 035 | AtCoder B '?'のときは最大の場合、離れていき（マンハッタン距離+1）、 最小の場合、近づいていく（マ…
abc036.contest.atcoder.jp 当初の方針 DPだろうなあ・・・（定義が分かるとは言っていない2回目） 木だから、木の嬉しい性質を利用するのかな まず全探索。白か黒で遷移してチェック。これは2^10^5なのでダメ 両端が黒になるものを列挙して、残りの組み合わ…
C: 座圧 - AtCoder Beginner Contest 036 | AtCoder 解法 omuさんにJAG夏合宿のとき教えてもらったので余裕です！順序付きのSetを利用して、それをMapに落とし込む（0からカウントアップしていく）。このような典型テク（？）が出てくるのは嬉しい。Submissi…
abc037.contest.atcoder.jp 当初の方針 DPだと思うけど、きれいな（for文で書けるような）漸化式が思いつかない。PriorityQueueを使えばトポロジカル順序ソートできるかな・・・？ →重複除去とか、dp[i][j]に値を入れる方法が分からない・・・。 解説を見て …
abc037.contest.atcoder.jp A 小さいほうをたくさん買えばいい。Submission #923925 - AtCoder Beginner Contest 037 | AtCoder B 言われた通りに書いて出力。Submission #923930 - AtCoder Beginner Contest 037 | AtCoder C 言われた通りに書く。しゃくと…
