キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)
61:52 ABCDE5完 1ペナ
perf. : 2137
rating : 1921 -> 1944 (+23)
A - Discount (1:29)
(A-B)/A、printfでちょっと手間取る()
B - Play Snuke (4:04)
問題文が全然頭に入ってこなくて焦る。ゲーム機が1 台10 億円で売られており、毎分1 台ずつ売れる世界。
C - Unexpressed (14:42)
x = ab となる x を全探索すると時間が足りないので a,b を全探索。普通にやると被りが出てくるので、既に数えたものは連想配列でメモ。包徐っぽくやろうとして無駄に時間を使ってしまった......
D - Poker (28:39)
# が何になるかを全探索でいいよね？いいよね？最近D が難しかったので疑ってしまった。# を決めると確率とそれぞれの点数が計算できる。のであとはやるだけ。
E - Oversleeping (61:52 1WA)
何かの部分問題で出てきて解けなかったやつだ、無理じゃんと思っていると、Y、Qが小さいことに気づく。1周期内における、起きている時間とBにいる時間をそれぞれ1つに決めて立式してみると拡張ユークリッドの互除法が使いたい見た目になる。拡張ユークリッドの互除法を使うと負の値が出てきてよくわかんないが、それっぽく処理。サンプルは合ったので投げる！WA！はい。そうだよね。互除法の結果から一般解を導く方法とかを調べてみるも、頭が壊れそうになる。一旦冷静になって、中国剰余定理を使う方法を考えてみるとすぐできて無事AC。ありがとう中国の人。
F - Zebraness
マスの色を状態に持って、上と右のマスだけをみるDPを書いてみる。サンプルが合わずに冷静になってみると、嘘に気づく。一旦落ち着いて、ここまで怖くて見れなかった順位表を見てみると意外と耐えてることに気づき、途端に集中が切れてしまった。おわり。コンテスト後のタイムラインで燃やす埋める問題だと知る。診断人さんのスライドをいつか勉強しようと思ってブックマークしておいたんだけどね、やらないよね。明日やります。
まとめ
途中まで本当にダメだと思って怖くて順位表見れなかった。意外と耐えてて良かった。中国剰余定理とは仲良くなれた気がする。燃やす埋めるとは明日から仲良くなれるといいな。明日はもっといい日になるよ。ね、ハム太郎！！
Codeforces Round #699 (Div. 2) virtual
https://codeforces.com/contest/1481
ABCの3完、むーん
A. Space Navigation
どれだけ消してもいいので最短距離で進むのが良い。px が正(負)なら、R(L)が|px|個以上あればいい。pyも同様にやる。
B. New Colony
nもhも小さいので愚直シミュレーションで通る。
C. Fence Painting
m回目のペイントでbに無い色を塗ってしまう場合はNO、以降ある場合を考える。各目的の色ごとに塗り変えなければいけない (ai != biのもの) plankの番号をメモしておく。前から見ていき、塗り変えなければいけないものから順番に貪欲に塗っていけばおっけー。bに存在しない (最終的に存在しない) 色が現れたらm回目のペイントで塗るplankを塗っておけばおっけー。最終的にちゃんと塗り変わっていればYES。塗り変わっている判定でミスって1WA。
D. AB Graph
構築。構築の典型として、単純な操作で構築できないかを考える、というのがある (？)。全ての文字が同じ文字列は回文であることに気づくと、ある頂点対を結ぶ2つの有向辺のラベルが等しいとき、その2つの頂点をひたすら往復すると、全ての文字が同じ文字列ができる。このような頂点対が一つでもあればYES。以降は無い場合、つまり全ての頂点対を結ぶ2つの有向辺のラベルが異なる場合を考える。まず、mが奇数のとき、2つの頂点をひたすら往復するだけで回文ができることがわかる。あとはmが偶数の場合についてのみ考える。ある3つの頂点を取り出してみると、同じラベルの有向辺でサイクルができているパターンとそれ以外に分けられる。サイクルがあるパターンはサイクルをたどり続ければいける。それ以外のパターンは非常に説明しづらいが、回文の真ん中の2文字だけ同じ文字になるように構築できる。サンプルをみると、m=2のときはNOなのがわかる。これで良いと思ったが最後までWAが取れず。終了後に何が間違っていたかを見てみると、YESの出力し忘れだった......
E. Sorting Books
時間外で解いた。「ABC-006D トランプ挿入ソート」を思い出す。トランプ挿入ソートのように、動かさなくても良い要素の数の最大化を目指してみる。ある値の要素を動かさないことにした場合、それらの間に挟まれている値が異なる要素は全て動かさなければならない。一番左にある値 x の要素の位置 lx と一番右にある値 x の要素の位置 rx と値 x の要素の個数を記録しておけば、Flog DP (蛍光灯DP?) のように index を状態に持つ一次元のDPでいける。サンプル2のように最初から後ろにある要素を動かさないという選択もできるのでうまいこと対処する。
まとめ
時間外だけど、Eが解けたのは良かった。デバッグ環境を整えたいなあと常々思っている。
AtCoder Regular Contest 113
51:50 ABCD 4完 ノーペナ (えらい！！！)
レート : 1883 → 1921 (+38)
perf. : 2214
A - A * B * C (3:09)
ABがKを超えない範囲で全探索するとお馴染み調和級数のやつになるのでO(KlogK)でいけちゃう。
B - A ^ B ^ C (15:08)
1の位の値は1の位同士の演算によって決まる。1の位の値は10種類しかないので10以下の周期で遷移することがわかる。愚直に掛け算して遷移の仕方と周期を求める。あとは肩のBC (mod 周期) が求まればおっけー。これは繰り返し二乗法で間に合う。任意modのmodint構造体を前に作っておいたので貼るだけ！
C - String Invasion (31:07)
後ろから貪欲に変換していくのが良さそう、あえて変換しないことが最適になることは無い、はず。あえて変換しないことで別の変換時に変換できる文字の数を増やすことはできるが、合計は変わらないことがわかったのでよし。s[i] = s[i+1] のとき、i+2 以降に存在するs[i]の数 (= cnt[i+2]) がわかっていれば、変換できる文字数が求められる。cnt[] は後ろから見れば作れるが、変換を行った後で分布が変わってしまい、毎回更新していたら間に合わないので、変換した場所以降は別処理することにする。具体的には変換した場所と文字の種類を保持しておき、cntに関しては変換した場所より前で見れば良い。これはセグ木を使うと楽、思考停止でセグ木を26本生やしておっけー。サンプルが合ったので提出！する前に、手元でaaaとかを入力してみたら-1とか返しおる。明らかにミスっている。ミスを見つけて直して提出！AC！ファインプレーだった。
D - Sky Reflector (51:50)
マスに値を書き込んでいって列対を確認するのはちょっと不可能そう。作成できる列対の必要十分条件を考えるのが筋が良さそう。Aを適当に決めてみる、このとき最大値をmaxAとすると、Bの各値はmaxA以上である必要があることがわかる。逆にmaxA以上であれば十分であることもわかる。maxAを固定すると、通り数が計算できて (Aの最大値がmaxAであるようなAの選び方) * (Bの値が全てmaxA以上であるようなBの選び方) になる、Aの方は(maxA)N - (maxA-1)N で求められる。これは典型。N,M のどちらかが1である場合には注意が必要でちゃんと提出前に気づけた。ファインプレーその2。
E, F
嘘貪欲すら投げられず、ひたすらに椅子を暖め続けた。
まとめ
今のベストに近い立ち回りができた気がする。が、結局高難度 (暖色diff.) には歯が立たないのでまだまだ。
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)
88:38 全完、9ペナ (？？？？) で レートは1881 → 1883 (+2) perf. 1901
A - Star
100 - X%100
B - uNrEaDaBlE sTrInG
大文字小文字判定ができますか？
C - Kaprekar Number
ギョッとしたけどやるだけ、直前に自作したstoi関数が火を吹いたぜ！
D - Base n
まず、適当な嘘 (最上位がMを超えないような最大のBをにぶたんで見つけてその周辺を探索する) を投げてWA、落ち着いてEにいった。
E - Train
あえて遅く到着するのが最適であることはあり得ないので、ダイクストラをちょびっと改造すればいけそう、順位表からも簡単なことが判明していたので素直にやって投げる。
D - Base n (再)
最上位だけじゃなくて全部見れば良くない？になる。ちゃっちゃと書き直して投げるとWA(2) 。明らかなバグを直し、にぶたんの範囲を変更して投げるとWA(3)。REが出たので、ああ、0徐算かとなってにぶたんの範囲を戻して投げるとWA(4)。ふと手元で|X|=1のケースを試してみると明らかにバグってるのを見つける。|X|=1のとき、無限じゃない？となって混乱。|X|=1のときは0を返すようにして提出 (なんで？？？？) 当然WA (5)。問題文を良く読んでみるとnの種類数ではなくn進数で見たときのXの値の種類数であることがわかる。つまり|X|=1のときは1ね！として投げるとWA(6)。原因が分からずに苦し紛れににぶたんの範囲だけ変更して投げる、WA(7)。|X|=1のとき、0になる可能性に気づく、X > M のときは0として投げる、ようやくAC！！！落ち着いて振り返ってみるとひどいね
F - Potion
kを固定して考えてみると、素材をk種類選ぶ選び方で、(魔力の総和) = X (mod k) となるもののうち、魔力の総和が最大になるものを選べばいいことがわかる。これは素材をいくつとったかと、総和 (mod k) を状態に持つDPでいける。全てのkについてDPを行うとO(N4)だが、軽いのでいけそう。総和がXを超えちゃう場合はどうしようかと思ったが、制約でそのパターンはあり得ないことになっているので問題なし。ぱぱっと書いて投げるとWA(8)。DPテーブルの初期値を全て0にしてしまっていた (素材をk種類選ぶという状態が無意味になる) ので直して投げるとWA(9)。-INFから遷移させてるのが怪しいことに気づいて投げ直してAC。ふう......
まとめ
毎度のことだけど焦りすぎ。青上位 perf. で暖まらなくなって今青上位にいるんだなあと実感した。
2020/02/06
Solved By kkktym
Topcoder: 0
Codeforces: 267
AtCoder: 1529
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1868
ABC191
ABCEの4完 93:10 1ペナ 破滅！
レートは 1913->1881 (-32) でした......
A - Vanishing Pitch
マッハ3の魔球を投げる高橋君、消えなければそれを打ち返すことができる青木君
B - Remove It
Aより簡単
C - Digital Graffiti
論争を巻き起こした問題その1。特に疑問に思わずに(たまたま)正しく題意を汲み取れたのですぐ通せた。マスの境界を舐めていき連結成分の個数を数える方法でやった。
D - Circle Lattice Points
その2。とりあえず104倍、とりあえずするには重い......あとは、x軸と平行でyが整数である直線と円の交点を求めてその内側にある格子点の数を数えるだけ！交点を求める際に生じる平方根をうまく(誤差なく)処理することができずに死亡。75分くらいまで考えてたけど流石にやばいと思って諦めてEにいった。
翌日、5時間くらい格闘した末にようやくAC。しんどかった......平方根は二分探索を使って整数値に丸め、104で割って格子点の数を数える際にもどっち方向に丸めるかで頭が壊れた。丁寧丁寧丁寧に考えてようやくAC。これを通せた人はすごいです。うーん、平方根を二分探索で処理するのを思いつかなかったのが一番の敗因、それぐらい思いつきたかったね......
E - Come Back Quickly
実家の安心感を感じた。各頂点から1回で辿れる頂点から元の頂点までの最短距離を計算しておけば答えが計算できるね。最短距離は......うん！制約も小さいしワーシャルフロイドで！(なんで？) 。TLE。焦りすぎた。落ち着いてダイクストラに書き直してAC。とっととDを諦めていれば......と思ったが、Dが解けなかったことを反省すべきではある。
F - GCD or MIN
コンテスト中には問題文を見ることすらできなかったよ。翌日、頭に入れておきながらジムでランニングしていたら解けた。帰って実装したらAC。ちょっと自尊心を取り戻した。コンテスト中に通せることと、コンテスト外に自力で通せることには大きな壁があるなあ......
まとめ
非常に悔しかったです。悔しくて、死にそう
2020/02/05
もつ鍋が世界で一番おいしい
Solved By kkktym
Topcoder: 0
Codeforces: 267
AtCoder: 1522
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1861
黄diff埋め
6/168 → 13/168 (+7)
ARC010 C - 積み上げパズル
DP[i][j][k][l] := i個目まで見て、これまで使った色の集合がjで、最後に使った色がkで、現在同じ色がl回続いているときの最大スコア。でやると当然間に合わない。遷移を考えると何回連続しているかは別にいらないことに気づく。これで間に合う。
日立コン2020 C - ThREE
これはコンテスト中に解けた数少ない(2つ)黄diffのうちの一つなので当然覚えている。かなり好きな問題、解けたので。
ARC032 C - 仕事計画
区間スケジューリングだけど、復元パートがある。辞書順最小なので前から貪欲に決めていきたいけど、なんでもかんでも選んでいいわけではない。区間スケジューリングしたのち、選んで良い仕事の条件(開始時間と終了時間)を求める。あとは前から貪欲に。こうしたら良さそうっていうのはすぐ浮かんだけど形にするのに時間がかかった。
ABC056 D - No Need
Ai が必要である条件は、Ai 以外の要素を自由に選んで和をK-Ai ~ K-1 にできることである。一要素を除いた部分和問題を求める問題は見たことある (All-you-can-eat?) これは両側から部分和DPをすればおっけー。見通しが悪くて両側から部分和DPをした後、作ることができる要素をピックアップした配列を作って、にぶたんして....とかやってたらMLEした。MLEを出すのは人生で二回目だぜ。とりあえず、部分和DPから配列を作った後はDPテーブルはいらないのでclearしてshrink_to_fitした。数は減ったけど一個だけMLEした。配列を作るのとshrink_to_fitを並行してやったらなんとかAC。
ARC009 C - 高橋君、24歳
とりあえずNからK個選ぶ、これは二項係数。NがめちゃでかいけどKがちっちゃいのでO(K)で求められるやつでやる。K個選んだあとは、要素数Kの順列で元の順列と同じ位置にある要素が無いようなものの数を求めれば良い。多分よくあるような問題な気がするので、「順列 元の位置に無い」とかで検索すると撹乱順列というものがヒットする。あとはこれをやる。サンプルが全然合わなくて焦ったけど、modが1777777777なのに気づいてAC。なにこれ。多分今出たら水diffくらいなのかもしれないと思った。
AGC016 C - +/- Rectangle
これはわりかし最近やった気がする。そのときは僕が考えうる最強の構築を作ってなんかACしてしまったけど、解説が綺麗に解いてて反省したのを覚えていたので、今回は綺麗に解いた。結構好き。
ARC045 C - エックスオア多橋君
これもかなり記憶に残ってたので瞬殺。これもすき。
まとめ
雑炊を人数分頼むとかなり多い
2020/02/04
自由という不自由
Solved By kkktym
Topcoder: 0
Codeforces: 267
AtCoder: 1520
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1859
Educational Codeforces Round 96 (Rated for Div. 2) ばちゃ
なんか先週テキトーにバチャして ( ABCのウォーミングアップに途中まで解いてやめたり ) たら、Codeforces Anytime のレートが急降下してた。
D
できるだけ連なっているところからとるのが良い。前の方から操作2で消されてしまうので、前の方からとるのが良い。
E
反転した文字列を前から合わせていく。indexがずれるのを管理する必要があるが、ずれ方が区間で一気にずれる感じなので区間加算セグ木でいける。どこかでやった気がするな。
黄diff埋め
黄diffをdiff順に解いていくことにした。解き直しもいっぱいあるけど...
ARC099 D - Snuke Numbers
式にして考える。n/S(n) <= n+1/S(n+1) とか、n/S(n) <= n+10/S(n+10) とか考えると、下の何桁かぶんは9じゃないとダメなことがわかる。候補が絞れたので全探索。かなり雑にやって通ってしまった。要復習？きっとしない
ABC127 F - Absolute Minima
数列A1...Anに対してg(x) = Σ|Ai - x| の最小値を与えるxは数列Aの中央値である。これはもはや典型(ABC102Cとか？)。aの値をmultisetで管理、中央値、中央値より小さい要素の総和、大きい要素の総和を管理していけば解ける。初めmultisetじゃなくてsetでやってて時間をロスした。
ARC039 C - 幼稚園児高橋君
マスの上下左右のマスを更新しながら進めば良さそう。今いるマスの上下左右に1方向について更新すれば良いので十分間に合いそう。マス全部を配列でもってしまうと死ぬので連想配列とかで管理する。構造体をmapのkeyに入れるときは比較関数を定義しないといけないんですね、それはそう。ちょっとめんどくさかったけどAC。
M-SOLUTIONS プロコンオープン 2020 F - Air Safety
実装が大変。考察はさくさく進んだ。コンテスト中に通せる気がしないぜ。
ABC181 F - Silver Woods
この問題はよく覚えていたので瞬殺。
ARC104 C - Fair Elevator
この問題もよく覚えていたけど実装にてこずった上に3WA出しちゃった。やっぱ難しいね、でもすき。
まとめ
昨日よりは修論が終わって解放された感じがあった。じわじわ実感していくものなのかもね...
