問題概要 step k でx方向かy方向に3k進む stepは0から始まる xとyが与えられるのでその座標にちょうど到達できるか判定せよ 制約 0≦x≦109 0≦y≦109 解説 319 = 1162261467なので高々19ステップで制約の座標には到達できるかどうかわかる。 各stepでx方向に行…

TopCoder Statistics - Match Overview 問題概要 要素数が偶数の配列Aが与えられる Aの要素2つを選んでペアを|A|/2個作る ペアの積がX以上となるようなペアの最大数を求めよ 制約 |A| % 2 = 0 -109≦A≦109 -109≦X≦-1 解説 Xが負であることがポイント。 偶数偶…

やり直し B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder 正三角形中の光の経路の長さを求める問題。 解法 f(a, b) := 辺の長さがaとbの平行四辺形の中を光が、2回反射するまでに進む距離とする。 2回反射する時点でまた平行四辺形ができる。 a …

D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder 解説 最小値をx[m]以下にできるかどうかで二分探索。 tを風船iがx[m]を超えない時間とすると、 H_i + t * S_i = xより、 t = (x - H_i) / S_i となる。これが風船iを割らなければいけない制限時間である…

やり直し B: Reverse and Compare - AtCoder Grand Contest 019 | AtCoder 問題概要 英小文字からなる文字列A(|A|≦200,000)が与えられる Aの英小文字2つを選んでそれを両端とする文字列を反転させることを1回まで行う 何通りの文字列ができるか 解法 A = abc…

Differential Pulse Code Modulation | Aizu Online Judge 解説 dp[i][j] := i個目の信号まででyがjのときの最小値 コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include </vector></string></stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>

やり直し D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder 解説 ゲームが終了する直前に文字列がどうなっているか考えると良い。(頭いいな〜) 両端が同じ時 abab...a ->直前は奇数個 よって与えられた文字列が奇数の時はSecondの勝ち（firstと…

DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 - AtCoder ABCの3完、Dは方針はあってたっぽいけど実装が詰められなくて死亡。234位。19年卒じゃない枠で100位以内は本戦だけどきついな〜。 A - DDCC型文字列 やるだけ。 int main() { …

やり直し B: 難易度 - AtCoder Regular Contest 043 | AtCoder 問題概要 難易度Diの問題がN個ある 以下の条件を満たす4問を選ぶ選び方は何通りか 2 問目の難易度は 1 問目の難易度の 2 倍以上である 3 問目の難易度は 2 問目の難易度の 2 倍以上である 4 問…

やり直し C - 高橋君、24歳 問題概要 N人に手紙をそれぞれの人の宛名で出そうとしたが、K人は自分の宛名ではない手紙がきてしまった。手紙の渡し方は何通りあるか。1,777,777,777で割った余りを求めよ。 2≦N≦777,777,777,777,777,777 2≦K≦777,777 解法 Nがめ…

やり直し D - 食塩水 解説 平均を最大化する問題->二分探索 wiグラムの濃度pi%の食塩水をk個混ぜた時の濃度は、 これがp以上となる時は を満たす。 変形すると、 濃度がp以上の食塩水を作れるかどうかは、 の値が大きい容器からK個選んで0以上となっていれば…

やり直し C - 掛け算 解法 Bが109乗なので愚直にシミュレーションするとTLEになってしまう。aを昇順に並び替えつつ、何回かシミュレーションをすると a[0] * A >= a[N-1] となる時が来る。こうなったらN周期で同じ列が現れる状態になる。周期的になるまでは…

B - マス目と駒 やり直し 解法 メモ化再帰 trueが返ってきたら負けとして再帰で解く コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include </stdio.h></stdlib.h></vector></string></stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>

問題読み間違えて詰んでた 問題概要 ・幅Xi高さYiの長方形がN個ある ・面積がlimit以上となるように長方形を重ねる(はみ出して良い、はみ出したらいけないと思っていた) ・90度回転して良い ・最大で何枚重ねられるか 方針 まず幅>高さとなるようにし、幅で…

問題概要 ・i番目のキャンディーのタイプはa_i ・タイプが1,2,3...,Kまで1つずつになるようにキャンディーを選ぶ選び方は何通りか 方針 ・K = 1の時 1の個数 ・K = 2の時 1の個数×2の個数 ・K = xの時 1の個数×2の個数×...×xの個数 となるのでこれらを全て足…

今日からSRMdiv2med埋め開始(atcoderレート1469) TopCoder Statistics - Match Overview 例えばgoal = 00101110の時、goalのbitが0となっている桁が1になっている数字は取り除く必要はない。 10001111は取り除く必要なし。00101000は取り除く可能性がある。 …

ABCしかなかったのでABC070に参加しました。 100-200-300-400なので全完できた。 A - Palindromic Number やるだけ。 int main() { string s; cin >> s; if(s[0] == s[2]) { puts("Yes"); } else { puts("No"); } return 0; } B - Two Switches 場合分けしま…

yukicoder 171に参加しました。 5/6完で45位でした。 星3のDPが解けなかった。 No.552 十分簡単な星1の問題 long long でもオーバーフローするのでstringで受け取って+“0"する。 ただし、0が入力される場合はそのまま出力することに注意。 #define FOR(I,A,B…

雑なので時間があったらまとめていこう... 全探索(工夫して全探索も) http://arc020.contest.atcoder.jp/tasks/arc020_2 https://www.hackerrank.com/challenges/two-characters http://poj.org/problem?id=3279 http://abc002.contest.atcoder.jp/tasks/abc…

AtCoderの問題 C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方*** ・実装** ・面白さ*** 問題概要 ・N個の数からなる数列が与えられる. ・が単調増加、すな…

AtCoderの問題 C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方** ・実装*** ・面白さ** 問題概要 ・柱が1列にN本並んでいる. ・それぞれの柱の高さはであ…

AtCoderの問題 C: こだわり者いろはちゃん / Iroha's Obsession - AtCoder Beginner Contest 042 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方* ・実装** ・面白さ* 問題概要 ・が与えられる. ・0~9ま…

AtCoderの問題 Dashboard - Round 1C 2009 - Google Code Jam 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方***** ・実装*** ・面白さ**** 問題概要 ・P人の囚人が一列の牢屋にいる(独房) ・あなたはQ人を解放し…

AtCoderの問題 B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方** ・実装* ・面白さ*** 問題概要 ・大きさが同じn枚の正方形の紙がある ・何枚かを使って長方形…

AtCoderの問題 C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 現在AtCoderの過去問AB(たまにC)解いてます. 難しさ（初心者目線） ・考え方*** ・実装** ・面白さ**…

AtCoderで開催された日本橋ハーフマラソンの予選のA問題です. A問題に時間をかけすぎてBが悲惨なことになりました. ちなみに予選115位でした… A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選 | AtCoder 参考書 プログラミングコンテストチャ…

AtCoderの問題 B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方*** ・実装** ・面白さ*** 問題概要 ・N匹の生き物がいる ・それぞれ大きさがAiで色が…

AtCoderの問題 A: Airport Bus - AtCoder Grand Contest 011 | AtCoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方** ・実装** ・面白さ** 問題概要 ・N人の人がバス停にTi時に来る ・それぞれの人はK以下の時…

yukicoderさんの問題 No.179 塗り分け - yukicoder 参考書 プログラミングコンテストチャレンジブック [第2版] 難しさ（初心者目線） ・考え方*** ・実装*** ・面白さ*** 問題概要 ・白と黒で塗られたマスがある ・黒いマスを赤か青に塗り替えたい ・この時…

POJの問題 3723 -- Conscription 参考書 プログラミングコンテストチャレンジブック [第2版] 今回の解法はこの本から得ています. 難しさ（初心者目線） ・考え方**** ・実装**** ・面白さ***** 問題概要 ・女N人、男M人を雇いたい ・1人10000ドルで雇える ・…