自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型90問

競プロ典型90問:022 - Cubic Cake(★2)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_v 挑戦結果 挑戦日:2021/10/06 結果:解けた 時間:30分ぐらい 考えたこと 一番小さい辺の長さで直方体を作る これが間違っていて、WAを出した 3辺の最小公倍数にカットすればよさそう 公式解…

競プロ典型90問:018 - Statue of Chokudai(★3)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_r 挑戦結果 結果:解けた 時間:40分ぐらい 考えたこと 俯角とはなにかを調べた 数式一発な問題と思った E869120 君の座標(x,y,z)の計算式を求めた 高橋直大像との俯角に必要な三角形を求めた …

競プロ典型90問:016 - Minimum Coins(★3)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_p 挑戦結果 結果:できた 時間:5分ぐらい 考えたこと 三重ループで全列挙。ループのネスト条件をだんだん狭くするやつ。 サンプル問題が帰ってこなかった。 最後は計算すればループが不要にな…

競プロ典型90問:014 - We Used to Sing a Song Together(★3)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_n 挑戦結果 結果:できた 時間:3分 考えたこと 小学生も学校も、左から順番にペアを組むのが最短になりそうと思った 公式解説 https://twitter.com/e869120/status/1382478816627478530/photo/…

競プロ典型90問:012 - Red Painting(★4)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_l 挑戦結果 結果:できなかった 時間:30分ぐらい 考えたこと 囲碁っぽくやること。TLEした・・・。 公式解説 UnionFindを思い出したし、以前にライブラリ化もしていた。 解説を読んだふりかえ…

競プロ典型90問:010 - Score Sum Queries(★2)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_j?lang=ja 挑戦結果 結果:解けた 時間:20分ぐらい 考えたこと 愚直は計算量がNGなんだろうと思った。累積和なことは思いついた。 クラスがあるからどう扱えばいいかと思ったけど、それぞれ累…

競プロ典型90問:008 - AtCounter(★4)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_h 挑戦結果 結果:解けた 時間:30分ぐらい 考えたこと DPっぽいことは最初から感じた 遷移の条件に苦労した 公式解説 https://twitter.com/e869120/status/1379927227739987972?s=20 解説を読…

競プロ典型90問:007 - CP Classes(★3)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_g 挑戦結果 結果:解けた 時間:10分ぐらい 考えたこと 愚直はTLEする $A$はソートすれば二分探索で近いクラスを見つけられる。見つけたら前後のどちらか($A_i$と$A_{i+1}$)が最も近いクラスな…

競プロ典型90問:006 - Smallest Subsequence(★5)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_f 挑戦結果 結果:できなかった 時間:30分ぐらい 考えたこと 全列挙を再帰的に作ることはできると思ったけど、計算量的にどう考えても無理だった。 貪欲に求める方法も考えたけど、思いつかな…

競プロ典型90問:004 - Cross Sum(★2)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_d 挑戦結果 結果:解けた 時間:15分ぐらい 考えたこと 愚直に計算するとTLEなんだろうと思った 事前に縦と横で集計しておくと、$縦合計+横合計-A[i][j]$ で$B[i][j]$が求まると気がついた 解説…

競プロ典型90問:003 - Longest Circular Road(★4)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_c 挑戦結果 解けなかった 考えたこと ワーシャルフロイドで全ノード間の距離を求めて、その最長の距離に+1すれば良いと思った。 コード書いたけどTLEした。$N3$では無理だった。 グラフの直径を…

競プロ典型90問:002 - Encyclopedia of Parentheses(★3)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_b 挑戦結果 解けた 時間:20分ぐらい 考えたこと すべて列挙なのでループして求める N文字なら、開カッコがN/2個、閉カッコがN/2個 閉じカッコが先行する場合がNG (と)の全順番を$2N$パターン作…

競プロ典型90問:001 - Yokan Party(★4)

問題 https://atcoder.jp/contests/typical90/tasks/typical90_a 挑戦結果 解けなかった 時間:30分ぐらい 考えたこと 苦手なDPと思ってずっと考えていたけど、あきらめた。 解説を見たら「答えで二分探索」の問題だった 解説を読んだあとのふりかえり 長さM…