競技プログラミング

SRM 645 Div1 Easy JanuszTheBusinessman

TopCoder Statistics - Problem Statement [問題] 365日の中に、重なるかもしれないN個の区間がある。いくつかの区間を選び、すべての区間が選択した区間と重なるようにしたい。最小でいくつの区間を選べばよいか? 2≤N≤50 [解答](後で) 区間を終了日順でソ…

SRM642 Div1 Medium TaroCutting

TopCoder Statistics - Problem Statement [問題] N本の木とD本のカッターがある。木は最初height[i]で1日にadd[i]のびていく。カッターは木の高さをdevice[i]丁度にすることができる。 各カッターは、1日に一回だけ使うことができる。 time日後、最小の木の…

SRM642 Div1 Easy WaitingForBus

TopCoder Statistics - Problem Statement [問題] バス発着所にN台のバスがある。それぞれのバスは出発するとtime[i]後にバス発着所に帰ってくる。時刻0にいずれかのバスが確率prob[i]で出発し、戻ってくるといずれかの次のバスが同じく確率prob[i]で出発し…

AtCoder Beginner Contest(ABC) #016 D - 一刀両断

かD: 一刀両断 - AtCoder Beginner Contest #016 | AtCoder [問題] 多角形(凹凸)と線分1本が与えられる。線分により、多角形は何個に分割されるか? [解答] 多角形の各辺について、線分との交差判定を行う。交差判定はベクトルの外積の符号判定を用いて行う(…

AtCoder Beginner Contest(ABC) #016 C - 友達の友達

- AtCoder Beginner Contest #016 | AtCoder [問題] N人について、友達関係M個が与えられる。 それぞれの人について、「友達の友達」の人数を返す。 [解答] 友達の友達から、友達と自分を引く。 [コード](Ruby) https://paiza.io/projects/KIPFdk49anacJxZTY…

AtCoder Beginner Contest(ABC) #016 B - A±B Problem

- AtCoder Beginner Contest #016 | AtCoder [問題] A,B,Cが与えられる。A+B=C、C-B=Dを満たすかどうかで、?(両方満たす), +(+のみ満たす), -(-のみ満たす), !(両方満たさない) のいづれかを返す。 [解答] 4通りチェックする。 [コード](Ruby) https://paiz…

AtCoder Beginner Contest(ABC) #016 A - 12月6日

- AtCoder Beginner Contest #016 | AtCoder [問題] 月が日で割り切れれば"YES",それ以外は"NO"を表示する。 [解答] 月%日==0で判定 [コード](Ruby) https://paiza.io/projects/BXfPvIAk9Mn-a-amw05H_g [感想] 頑張れば50バイトぐらいになるかなぁ?

yukicoder No.86 TVザッピング(2)

No.86 TVザッピング(2) - yukicoder [問題] N x Mのマス目がある。あるボタンから開始して、通れるマス目を1回づつ巡って最初のマスに戻る。ただし、ボタンを巡る際、進行方向はまっすぐか左にのみいける。 [解答] 最初のボタンの前後では実質的に右み回るこ…

yukicoder No.85 TVザッピング(1)

No.85 TVザッピング(1) - yukicoder [問題] X * Yのマス目にボタンがある。いずれかのボタンからスタートして、上下左右のいずれかのボタンに動いて最初のボタンに戻る。各ボタンは一度だけ辿ることができる。このように巡回することはできるか?ことはでき…

TopCoder SRM 639 Div1 Medium Board Folding

http://community.topcoder.com/stat?c=problem_statement&pm=13457 [問題] N x Mのマス目がある折り紙が机に置いてある。それぞれのマスは白(1)又は黒(0)色になっている。 折り紙は机から持ち上げずに、縦又は横に折り目を付け、左、右、上、下から半分を持…

yukicoder No.84 悪の算盤

No.84 悪の算盤 - yukicoder [問題] R行C列のマス目から1個だけ選んで"*"を書く。 作れるパターンに0から順番に番号を付けると何番まで書けるか。 1<=R,C<=10^9 [回答] 基本的にパターン数はR*C。 縦横の長さが同じ場合、90度で回転させるので4で割る。違う…

yukicoder No.83 最大マッチング

No.83 最大マッチング - yukicoder [問題] 0..9のデジタル数字をマッチで書く。マッチN本で数字を書く時、最大で書ける数字(複数桁)は何か? 2<=N<=10^5 [回答] 1本で書ける数字はない、2本で1が書ける、3本dで7が書ける。 桁数が多い方がいいので、1を使え…

yukicoder No.82 市松模様

No.82 市松模様 - yukicoder [問題] 幅W、高さH、左上C("B" or "W")で、"B"と"W"の市松模様を書く。 [回答] (w + h)%2==0 or 1で"B"又は"W"を出力。 Cが"B"か"W"で出力を反転。 [コード](Ruby) https://paiza.io/projects/8cO8BE7P9BK9mOHEVVh5pA [感想] 左…

ARC(AtCoder Regular Contest) 030 C - 有向グラフ

C: 有向グラフ - AtCoder Regular Contest 030 | AtCoder [問題] n個の頂点とm本の辺の有向グラフがある。各頂点には'a'-'z'のアルファベットが1個ある。任意の頂点から開始してグラフをたどり、アルファベットを合計k個順番に取る。各頂点では取っても取ら…

ARC(AtCoder Regular Contest) 030 B - ツリーグラフ

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder [問題] n頂点のツリーグラフがある。いくつかの頂点に宝石がある。頂点xから開始して、全部の宝石を取ってxに戻るには、最短で何個の辺を通ればいいか。 [回答] 頂点xから出発してDFS(深さ優先探索…

ARC(AtCoder Regular Contest) 030 A - 閉路グラフ

A: 閉路グラフ - AtCoder Regular Contest 030 | AtCoder [問題] N個の頂点が円のように線で結ばれて並んでいる。 ここからいつくかの頂点を取り除いて、K個の線分に分割することはできるか?できれば"YES",できなければ"NO"を返す 3<= n <= 10^5 1<= k <= 1…

TopCoder SRM 639 Div1 Easy AliceGame

問題: 何回かAliceとKirtoでゲームをする、それぞれの回ではAliceのKirtoの勝った方が1,3,5,7,... 2i-1点となる。負けた方は0点。 最終的にAliceはx点、Kirtoはy点になる。 Aliceの勝利回数は最小で何回か。存在しなければ-1を返す 0<= x,y <= 1,000,000,000…

yukicoder No.78 クジ付きアイスバー

No.78 クジ付きアイスバー - yukicoder 問題 はずれ、あたり1個、あたり2個のいずれかのアイスバーが箱にN個順番に入っている。 K本のアイスバーを食べるには、何個買う必要があるか? 1<=N<=50, 1<=K<=2*10^9 解答 後で。 1個目の箱と最後の箱は一個ずつ…

yukicoder No.77 レンガのピラミッド

No.77 レンガのピラミッド - yukicoder 問題: N列分のレンガ(Ai)が並んでいる。 1列目からピラミッド型([1,2,3....L-1,L,L-1,....1])に並べるには レンガを何回移動させるか捨てればいいか? 1<=N,Ai<=100 回答: L段のピラミッドの個数は 1 + 3 + 5 + ... = …