jsc2019で久しぶりにキョウプロしました ABを早く解くことができて割と順位はよかったです。 でもC~は手も足も出ず精進不足を感じました。気が向いたときにやっていこうと思います。 今回はサボってた時期のコンテストを解きました。 A - Password やるだけ…

700点問題解説AC 典型っぽさはあったんですが、うまく考察を詰め切れませんでした。 問題：ｎ個のpairがそれぞれどちらかを青、他方を赤に塗る。青の範囲と赤の範囲の長さの積を最小化せよ 解説： まず、小さいほうを片方に寄せることを考える。 そうでない…

バチャ A. Maxim and Biology 読解しづらくて9分でした。渋み 連続する4つなので全探索すればよいです B. Dima and a Bad XOR 問題：行列の各行から1つ整数を選ぶ。XORを取って0にならないような選び方があるか調べよ 考察： 2種類の整数が含まれる行がある…

バチャした。紫なんですけど、Div2でしました。 A. Stock Arbitraging 問題：株を買ってから売って現金を最大化せよ 考察： もっとも安いときに買って、高いときに売ればよいです。 なぜか最適かわからんくなって5分 B. Tiling Challenge 問題：十字のブロッ…

予定あって出れなかったやつやりました。 結果は70分5完で500位くらいでした。嘘解法だったのもあってちょっとつらみ A - Tenki やるだけ。初心者的に文字列操作結構しんどいイメージあります。 B - Power Socket 問題文がわけわからんやつでした。 サンプル…

bqaya A. Neko Finds Grapes 問題：ｎ個の整数列Aとｍ個の整数列Bを１：１マッチングして、足して奇数になる組を最大化せよ 考察： それぞれで奇数偶数の数を数えます。 奇数と偶数のマッチングしかないので、それぞれの小さいほうを足せばよいです。 B. Nek…

codeforces.com ばたや A. Eating Soup 問題：ｎ人が円状にならんでいるとき、ｍ人を退席させる。非連続にわかれる最大の個数を求めよ 考察： n/2までは増えてそれからは減りそうです。 奇数のときでn/2付近が怪しいので実験して丁寧に解きましょう B1. Cat …

バチャ A. A pile of stones 問題：ある個数の石ｘから初めて与えられた操作をする。最小値が0以上のとき、最後に残る石の数を最小化するｘを求めよ 考察： Aにしてはちょっと厄介でした。 全体での最小値を0とすることが最適なので、x=0とか適当にして、最…

codeforces.com A XORinaccistandard a,b,a^bの順になります やるだけ B Uniqueness 問題：整数列Aから連続する部分列を削除して、残ったものがdistinctになるようにせよ 削除する部分列の長さを最小にせよ 考察： 左からと右からを考えます。 左からL個残し…

C - Sequence Growing Easy C - Sequence Growing Easy 問題：すべて0の数列XのX(i+1)=Xi+1にする操作を好きなだけできる。数列Aiを実現する最小操作回数を求めよ 考察： 逆順に見ます。 操作：Ai+1==A(i+1)のとき、A(i+1)を好きな要素に変える。 全て0にし…

atcoder.jp 参加しました～ A - Takahashi Calendar 全探索で十分間に合うのでそうします。 B - Kleene Inversion 問題：N個の整数列ＡをK個並べた整数列の転倒数を求めよ 転倒数：あるaiより左側にあり、aiよりstrictに小さい。これを満たす整数組の数 考察…

bあｙた A. Silent Classroom 問題：n個の文字列が与えられ、2つのグループにわける。下で定義される値を最小化せよ。 うるささ：同じグループ内で同じ頭文字を持つペアの順序なしの数 考察： まず全部を頭文字でわけます。 ある文字で始まる文字列がｋ個の…

バチャ ボロボロすぎた A. Circle Metro やるだけ。 特別気を付けることもないかなって印象です。 サンプルみて問題もよくわかりました B. Pairs 問題：pairがm個ある。ある整数2つを選び、すべてのpairのどちらかにどちらかが含まれるx、yはあるか。 考察：…

参加しました～ codeforces.com A. There Are Two Types Of Burgers やるだけです。 h,cの大小で場合分けしてもよいですし、全探索でも間に合います B. Square Filling 問題：n*mの０１行列がある。任意の2*2の範囲をすべて1にする操作を好きなだけして、与…

D. All Your Paths are Different Lengths 問題：頂点１からｎが有向グラフでトポロジカルに並んでいて、１からｎのパスがL個あり長さが０～L-1であるものを構築せよ。ただし頂点数２０以下辺の数６０以下とする。二重辺を許す。 L<=１０＾６ 考察： １０＾…

atcoder.jp 700点問題2問目も解説ACでした… 蟻本の由来になったとか？ 典型なんでしょうか。全くわからなかったです。 問題：周の長さLの円にN匹の蟻がいる。蟻は単位時間に１進み、時計回り化反時計回りか最初に決まっている。蟻同士が出会うと２匹とも反転…

codeforces.com ばｔｙ６あ A. From Hero to Zero 問題：1を引く、kで割るを何回すればnを0にできるか求めよ 考察： nが非常に大きいので、n%kを使い前者の操作を効率よくやります 3分でした。よい B. Catch Overflow! 問題：3つの命令が与えられる。初期値0…

バチャ。 ３０分３完で２２００位でした…低い… D通さないといけない回だったんですかね。リサブで減点されたことを加味しても悲しい順位でした。 codeforces.com A. Ehab Fails to Be Thanos 全ての要素が一致するときだけ-1で、他は構築可能です。 簡単な例…

700点埋めそうそう解説AC… 典型っぽいので慣れたい（むずくない？） 問題：Kの正の倍数の10進法の桁和で最小のものを求めよ 考察： 桁DPで150桁くらいまで雑にやったけどダメでした。 mod Kだろうなって感じはしたんですけど、うーーん 解説： グラフ問題に…

codeforces.com 初のdiv1が0完でしたが… A. Almost Equal 問題：2n個の整数の順列が環状に並んでいる。n個の連続する要素の和2n個の、任意の2つの要素の差が最大でも1になるような順列を求めよ 3個だと思ってました（なぜ） 解説： コンテスト終わった後に考…

https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_d 解説ACです。うーん難しい 問題：ｎ個の整数列Aに操作を好きなだけしてBと一致させたい。可能か。 操作：隣り合う2つの片方に、もう一方をXORする 解説： ある2要素を入れ…

新環境になってWordにためてた精進記録が取れなくなったのでブログで代用 これからは単発も上げるわ（虚空に向けて） https://atcoder.jp/contests/agc001/tasks/agc001_c 問題：n頂点の木が与えられる。頂点を削除して直径をk以下にせよ。最小頂点数を求め…

2日連続でACのコンテストじ A - Red or Not 3200未満がredで3200以上がsと出力する 逆じゃん！というネタですね。 redじゃなくてresとtypoして危うくペナ踏むところでした。あぶねえ B - Resistors in Parallel 問題：逆数を足したものの逆数をとる やるだけ…

出ました。ABはやめの2完で黄色パフォ。久し振りにレートが伸びました(うれしい) A - Dividing a String 問題：文字列ｓの分割で隣りあう２つが一致しないような最大の分割数を求めよ 考察： とりあえず貪欲にわければよいです 1つ前と一致する場合1文字追加…

あちゃ codeforces.com A. Nauuo and Votes やるだけです。丁寧に場合分けしましょう B. Nauuo and Chess 問題：n個のコマをm*mのマスに置く。任意の2つの駒のマンハッタン距離が番号の差より大きくならなければならない。最小のｍを求めよ 考察： かなり天…

ばちょ codeforces.com A. Filling Shapes 問題：L字のピースを3*nの枠に綺麗にはめる。何通りのハメ方があるか 誤読して何ピース使うかかと思いました。 そもそもピースに対する記述少なすぎてなんだかって感じでした。サンプルも雑だし B. Plus from Pictu…

atcoder.jp ゴリラジで触ったので自分用振り返り 問題：二次元平面上を(0,0)から移動する。ルールに従いk回の直進をする。直進の方向のみ与えられたとき、最後にどこにいるか。 ルール：1回も通ってない点に到達するまで直進する。 考察： もし進む先が既に…

we did a pretty good job so far^^ nanikore codeforces.com A. Chunga-Changa 問題：ｘ円とｙ円持っている人がいる。ｚ円のものを2人で協力してできるだけ多く買いたい。最大化したとき、一人がもう一人に譲渡しなければいけないお金を最小化せよ。 考察：…

参加しました。 codeforces.com A. Circle of Students 問題：長さｎの順列を環状に並べたとき、ソート済みになるかを調べよ 考察： これめっちゃ時間かかっちゃいました。 色々解法あると思うんですけど、なんにせよ場合分けある程度しなきゃいけなくてしん…

宴じゃ。2時間半長すぎ codeforces.com A. Ropewalkers やるだけです。ソートして、最小値と最大値を中央値から離せばよいです B. Email from Polycarp 問題：意味不明。2つの文字列が与えられるのでナニカを判定する。 考察： どうにか読解したあとサンプル…