Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

competitive programming

AtCoder Beginner Contest 169

4完3WA。落ち着け。 各問題 A - Multiplication 1 掛け算を、します。 B - Multiplication 2 まず、0が一つでもあるときは絶対0なので0を出力します。サンプルにもあるで大丈夫でしょう。(優しい・・・) で、順次掛けていくわけですが、10^18を超えてはい…

NOMURA プログラミングコンテスト 2020

2完。6:01。 いや、そんなに失敗してないと思うけど、パフォ渋い・・・。 各問題 A - Study Scheduling 起床時間と就寝時間を分に換算し、それらの差からKを引けばよいです。 ただし、マイナスになったら0を出すことを忘れないように。 (2020-05-30 23:38 追…

C. Similar Pairs (Codeforces Round #644 Div. 3)

問題 https://codeforces.com/contest/1360/problem/C 問題概要 項数が偶数の整数列が与えられる。この列の項で偶数と偶数、奇数と奇数、または差が1の項どうしでペアを作る時、あまりなしですべての項をペアにすることが可能か答えよ。 考察 まず列の中の偶…

B. Honest Coach (Codeforces Round #644 Div. 3)

問題 https://codeforces.com/contest/1360/problem/B 問題概要 整数列が与えられる。これを数列AとBに過不足なく分けたとき、Aの最大値とBの最小値の差の絶対値が最小になるようにしたい。 実現可能な差の絶対値の最小値を答えよ。 考察 例えば数列[4, 1, 9…

A. Minimal Square (Codeforces Round #644 Div. 3)

問題 https://codeforces.com/contest/1360/problem/A 問題概要 2つの辺がaとbの長方形2つを、はみ出さずに敷き詰めることができる正方形の面積を求めよ。 考察 わざわざはみ出させても得をしませんから、2つの長方形は同じ長さの辺が揃うように並べて2倍の…

B. Two Arrays And Swaps (Codeforces Round #642 Div. 3)

問題 https://codeforces.com/contest/1353/problem/B 問題概要 長さnの正の整数で構成された配列aとbが与えられる。また、正の整数kも与えられる。(ただしk<=n) aとbの項目をk回以下入れ替えて作れる配列aのうち、各項の合計が最大になるときの最大値を答…

A. Most Unstable Array (Codeforces Round #62 Div. 3)

問題 https://codeforces.com/contest/1353/problem/A 問題概要 2つの整数n, mが与えられる。 負でない整数から構成された長さn、かつ隣接する各項の差の絶対値の合計が最大になるように配列aを作成した場合の、隣接する各項の差の絶対値の合計を答えよ。 コ…

AtCoder Grand Contest 044

初の、NoSub。戦術的なやつではなく、手元でサンプルを通すことも叶わずでした。 各問題 A - Pay to Win 最初、2倍3倍5倍の全探索(過不足を最後に調整)かと思ったんですけど、これだと途中で+1が挟まるパターンに対応できず。 次にメモ化再帰とBFSを考えま…

G. Special Permutation (Codeforces Round #640 Div. 4)

問題 https://codeforces.com/contest/1352/problem/G 問題概要 整数nが与えられる。隣り合う項の差の絶対値が2以上4以下となるような、長さnの順列を作れ。無理な場合は-1を出力せよ。 考察 これは気づいてしまえばおしまいという問題で、以下の手順ででき…

F. Binary String Reconstruction (Codeforces Round #640 Div. 4)

問題 https://codeforces.com/contest/1352/problem/F 問題概要 '0'と'1'で構成された文字列を考える。その文字列の隣接した2文字を数値として足して和が0, 1, 2になる区間の合計数がそれぞれ与えられる。 例えば文字列1110011110の場合、11, 11, 10, 00, 01…

AtCoder Beginner Contest 168

まさかの1日2回幾何www(えでゅふぉとABC) しかもsin, cos, tan全部出てきました。 各問題 A - ∴ (Therefore) 10で剰余を取って、後はif文で頑張りましょう。"hon"の時をelseにするのが一番効率がいいということにあとで気づきましたが、まあ誤差の範囲…

E. Special Elements (Codeforces Round #640 Div. 4)

制約について考えさせられる問題でした。 問題 https://codeforces.com/contest/1352/problem/E 問題概要 長さnの数列が与えられる。各項は1以上n以下の整数である。 各項の値について、その数列の連続する2つ以上の項の和で表すことができる場合、その項は…

D. Alice, Bob and Candies (Codeforces Round #640 Div. 4)

問題 https://codeforces.com/contest/1352/problem/D 問題概要 非負整数で構成された長さnの数列が与えられる。アリスは右からボブは左から以下の規則のとおりに数列の数字を取っていく。 最初にアリスが一番左の数字をひとつだけ取る 次にボブが右から取る…

AtCoder Beginner Contest 167

4完1WA1RE。 こどふぉDiv. 2のAとか、ABCのBに強烈な苦手意識があるのをなんとかしたい今日この頃。 各問題 A - Registration SとTの|S|文字までを比較して、すべて一致すればYes、しなければNoです。 B - Easy Linear Programming A >= Kなら1をK枚引けるの…

B. Same Parity Summands (Codeforces Round #640 Div. 4)

問題 https://codeforces.com/contest/1352/problem/B 問題概要 整数nとkが与えられる。nをk個の非負整数の和として表した時、k個すべてを奇数またはk個すべてを偶数とする方法はあるか答えよ。ある場合は一例を示せ。 考察 まず、nよりkのほうが大きいとき…

A. Sum of Round Numbers (Codeforces Round #640 Div. 4)

記念すべきこどふぉDiv. 4の一問目! 問題 https://codeforces.com/contest/1352/problem/A 問題概要 整数nが与えられるので、それを丸めた数の和として表現せよ。その際、項の数は最小になるようにせよ。 考察 例えば1234なら1000と200と30と4に分けろとい…

AtCoder Beginner Contest 166

5完2WA。 久々の5完なのに緑パフォとか、世間の風は冷たい・・・。 各問題 A - A?C 入力がABCならARCを、ARCならABCを出力です。 B - Trick or Treat N人のすぬけ君のためにintの配列を用意して、お菓子毎に持っているすぬけ君のカウントを上げていけば、最…

AtCoder Beginner Contest 165

4完1WA。 C、いい問題だったなー#AtCoder— Toy (@mdstoy) 2020年5月2日 いやほんまにw 各問題 A - We Love Golf O(1)の解法でもいいんですが、つまらないミスをしてもいやだし、何も考えず全探索書くほうが速いし(コンテストだから)、というわけで、Aから…

AtCoder Beginner Contest 164

3完1WA。 各問題 A - Sheep and Wolves S <= Wが成り立つならunsafe、そうでないならsafeです。 B - Battle シミュレーションすればよいです。先に体力が0になった方の負けです。 私はa <= 0とすべきところをa == 0としてしまい1WAを出した上に、それに10分…

Re: D. Nastya and Scoreboard (Codeforces Round #637 Div. 2)

mdstoy.hatenablog.com この記事の続きです。ちゃんと想定解のDPで解き直したので、それの解説というか、おぼえがきです。 問題 https://codeforces.com/contest/1341/problem/D 問題概要 7セグがn個並んでいて、点灯状況が与えられる。しかし、k個のセグメ…

D. Nastya and Scoreboard (Codeforces Round #637 Div. 2)

注意:以下の解説は想定解ではありません。しかも、コンテストではシステムテストを通ったのに、今投げるとTLEで落ちます。(えー 想定解はDPですのでDPで解きましょう。 この記事は自分のための備忘録として残しておくものです。 (2020-04-26追記)DPで解き…

C. Nastya and Strange Generator (Codeforces Round #637 Div. 2)

問題 https://codeforces.com/contest/1341/problem/C 問題概要 幅nの区画が横一列に並んでいて、左から順に1, 2, 3, ..., nである。 各区画に改めて別の番号を1から順に振っていく。その番号を振る際のルールは以下の通り。 各区画について、自分を含めて自…

B. Nastya and Door (Codeforces Round #637 Div. 2)

Nastya was very confused じゃあないんだよ。困惑してるのはこっちだよ。 問題 https://codeforces.com/contest/1341/problem/B 問題概要 峠を境に地区が分かれている地域がある。 その地域の幅nの区間ごとの標高と、幅kが与えられるので、幅kの中に含むこ…

A. Nastya and Rice (Codeforces Round #637 Div. 2)

問題 https://codeforces.com/contest/1341/problem/A 問題概要 n個の袋があり、袋一つの重さはa-bからa+bの間であり袋n個全体の重さはc-dからc+dの間であるという。 n, a, b, c ,dが与えられるので、上記の条件を満たしているかどうかを答えよ。 考察 (a-b)…

B. Balanced Array (Codeforces Round #636 Div. 3)

問題 https://codeforces.com/contest/1343/problem/B 問題概要 偶数nが与えられる。以下の条件を満たす長さnの数列を一つ構築せよ。なお、構築可能であるかどうかは保証されない。 前半のn/2個の要素は偶数である 後半のn/2個の要素は奇数である すべての要…

A. Candies (Codeforces Round #636 Div. 3)

問題 https://codeforces.com/contest/1343/problem/A 問題概要 のときを満たすようなxを一つ求めよ。 考察 与えられた式を変形するととなります。よってがnの約数となるようなkを見つけてきてをすればよいです。 kは2から順に一つずつ見ていけばよいです。…

B. Yet Another Meme Problem (Educational Codeforces Round #80)

問題 https://codeforces.com/contest/1288/problem/B 問題概要 conc(a, b)を、aとbを連結したものを返す関数として定義する。例えばconc(12,23) = 1223であり、conc(100,11) = 10011である。 2つの正の整数A, Bが与えられるので、1 <= a <= A, 1 <= b <= B…

AtCoder Beginner Contest 163

うーん、Unratedですか・・・。まあ仕方なし。 各問題 A - Circle Pond 円の周長は直径×πで、与えられるのは半径Rなので、答えはR * 2 * πです。πは言語で提供されている定数があるならそれを使いましょう。定数がなければ、この問題は「絶対誤差または相対…

B. Sorted Adjacent Differences (Codeforces Round #633 Div. 2)

問題 https://codeforces.com/contest/1339/problem/B 問題概要 n個の整数からなる数列が与えられる。 この数列をとなるように並び替えよ。 考察 絶対値の差が広がるように並び替えろということです。これは元の数列をソートして、真ん中から左右に一つずつ…

A. Filling Diamonds (Codeforces Round #633 Div. 2)

ギャグ of the year 2020 有力候補 問題 https://codeforces.com/contest/1339/problem/A 問題概要 整数nがある。4n - 2個の正三角形を使って幅nの図形を作る。(図形の形は上記リンク参照) 幅1のときと同じ形のひし形を、幅nの図形に敷き詰める時、何通り…