競技プログラミング

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 =…

SRM 701 Div 2 Easy, Medium

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 = …

AtCoder Regular Contest 052 B : 円錐

arc052.contest.atcoder.jp 解法 典型的なRMQ問題(足すやつもMinimumっていうんでしょうか・・・)円錐を高さ1ごとにぶつ切りした体積を配列に持たせて、 それをSegmentTreeに入れてあげて更新作業をすれば、 あとはクエリーに答えていくだけ。計算量も事前…

AtCoder Regular Contest 052 A : 何期生?

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 qual C : E - 順列辞書 / Encyclopedia of Permutations

code-festival-2016-qualc.contest.atcoder.jp予選落ちたのが大変悔しかったので、 ちょっと背伸びして普段じゃ絶対に解けないだろう、 最後の問題を解いてみた。 当初の方針 ちんぷんかんぷん 解法を見て ????自分に理解できるように噛み砕いていく。 …

CODE FESTIVAL 2016 qual C : D - Friction

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 qual C : C - 二人のアルピニスト / Two Alpinists

code-festival-2016-qualc.contest.atcoder.jp青木君が東からやってくるの見落として 問題の意味を理解するまでとても時間がかかった 当初の方針 意味分からん。間違いがあればどのデータも信用ならないし、 答えが出ないのでは? 青木くんの存在に気づき、…

CODE FESTIVAL 2016 qual C : A B

code-festival-2016-qualc.contest.atcoder.jpこの人の出す問題嫌いついでにいうと人柄も嫌い A 前からのCの位置と、後ろからのFの位置を取得してチェックSubmission #943435 - CODE FESTIVAL 2016 qual C | AtCoder B 紙に書いてみると、毎回前のとは違う、…

AtCoder Beginner Contest 033 D : 三角形の分類

abc033.contest.atcoder.jp 当初の方針 幾何は苦手意識・・・。サンプルみたいに、直角と鋭角の数をカウントして、 全体から引けばいい?(うまくだまされました)グリッド上に配置されるから、直角になるには、 x座標かy座標かが一緒になる? (大嘘。(0,0)…

AtCoder Beginner Contest 033 A B C

abc033.contest.atcoder.jp A setに突っ込んで、1つだけかどうか判定Submission #937773 - AtCoder Beginner Contest 033 | AtCoder B 言われた通りにチェックSubmission #939333 - AtCoder Beginner Contest 033 | AtCoder C 一瞬「うげっ、構文解析?!」…

AtCoder Regular Contest 053 B : 回文分割

arc053.contest.atcoder.jp 解法 回文になるには、 偶数個のみで構成される文 偶数個と、1つの1文字で構成される文 であることが分かる。なので、まず文字ごとの出現回数をカウントし、 奇数を1と残った偶数に分解してあげる。 すると、1の個数と偶数の合計…

AtCoder Regular Contest 053 A : ドミノ色塗り

arc053.contest.atcoder.jp 解法 それぞれで、長さ-1コ分が連なっており、 重複はない。タテ:w * (h-1) [コ] ヨコ:h * (w-1) [コ]この2つを足せばいい。A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder