Codeforces

まずは条件を整理する。 インデックス があって（ ） 、 から までで条件が「2」のとき、長さ1に 両方を含むことはできないので明らかに0通り。 から までの条件が「1」で までの条件が「2」のとき までに2種類を含むので0通り。 以上から答えが「0」のときは予め出力して処理を打ち切っておく。 上の条件を含まない時、 から の条件が「2」のときかつ の条件が「2」のとき、 の条件は「0」と同一視してよい（ から ですでに二種類ふくむ）。 から の条件が「1」のとき、すべての の条件は「1」と同一視してよい。 よって が始点になる条件は、「 最後の条件1のインデックス」と「最初の条件2のインデッ…

先日開催されたCodeforces Round #839 (Div. 3)のD問題を解説します。 本番中に通せなかったのと、あまりみたことのないタイプの問題だったので記憶に残すためにも書きます。 問題概要 問題文 正の数からなるある数列Aが与えられる。あるxを選び、と置換した時にAがソートされた状態になるようなxを1つ探す。 制約 解説 まずは小さいケースから考えます。 ] この場合は、すでにソートされていますが、どんなxを選ぶことができるでしょうか？ の時条件を満たし、になると条件を満たしません。 ] この場合はどうでしょうか？ になると条件を満たします。 この2ケースを比較すると、連続する…

。をの素因数の集合とする。 が答え。 とは互いに素なので両方が、の素因数の倍数であることはない。 またがの倍数なのでがの倍数の場合、もの倍数。 よってとは共にの倍数ではない。 以上からとにある数を足すことで両方をの倍数にできる。 のすべての素因数にたいしてこの足す数の最小値が答え。 注意点1。 のとき出力する答えは。「差が1の2数は互いに素 gcd(x,y)=1」は有名事実。いくつ足してもとの差は1のままなので、永遠に互いに素。 注意点2。 上の考察を素直に実装するとTLEになる。素朴に高速化するとMLEになった。いい感じに実装する必要がある。 イメージ図

こんにちは、shu8Creamです。 先日行われた、LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）にて1754パフォーマンスを出して、水色になることができました！ 現在のレートは1247で、レートが一気に+73されたので大成功回でした。 初めて緑になったのが、2021/4/18らしいので2022/8/6で水色になるまで、1年4ヶ月ほどかかりました。 ちなみにCodeforcesは少し前に青色になりました。 ちなみにちなみに最近AtCoder Heuristic Ratingでも水色になりました。 精進記録 学んだアルゴリズム 実際に使…

Codeforces Round #713 (Div. 3)(2022/5/12) A: Spy Detected! 初項と末項が等しければその間に, 異なればそのどちらかが異なる数であるので場合分けをすればよい. 場合分けをすると, 多数側の数を確定できるのでそれを比較に用いればよい. https://codeforces.com/contest/1512/submission/156893367 B: Almost Rectangle 2点が異なる行, 列にある時はその2点が対角線になるようにすればよく, そうでないときはその2点が長方形の1辺となるので, 残りの辺をその辺と平行になるよう…

Codeforces Round #693 (Div. 3)(2022/5/10) A: Cards for Friends が2で割り切れる回数を , が2で割り切れる回数を とすると, カードは最大で, 個に分割できる. これと の大小関係を見ればよい. https://codeforces.com/contest/1472/submission/156418203 B: Fair Division 2をできるだけ均等に分けた後, 1で調整をすればよい. https://codeforces.com/contest/1472/submission/156418372 C: Long Jum…

Codeforces Round #674 (Div. 3)(2022/5/3) A: Floor Number の時だけ場合分けをして残りは割り算によって求まる. https://codeforces.com/contest/1426/submission/155732980 B: Symmetric Matrix まず が奇数の時は明らかに敷き詰められない. が偶数の時は, 対角成分を敷き詰めるために, 1,0成分と0,1成分が等しい行列が存在する必要がある. 逆に, 全ての要素をこの行列で敷き詰めたものは対角行列になる. https://codeforces.com/contest/14…

割とすんなり解けた。 https://codeforces.com/contest/1733/problem/E

09/11(月) 午後4時過ぎ起床。半からインターン先定例会に参加した。今週の進捗も昨日寝る前に稼働した分だけである。 勉強会は現場で使われているシェルスクリプトを読むというものだった。2年ほど前に自分が行った勉強会で少しシェルスクリプトの文法に触れたが、その資料の特にリダイレクト回りが役に立ったらしく嬉しい。フィールドの抜き出しにAWKが効いていたり、sedのsコマンドの区切り文字を/から変更したりと、思ったよりいろいろなものが使われていてワクワクした。 勉強会1115.pdf - Google ドライブ 普段より早く終わったので学食に行って夕食。帰宅してからはずっと週記を書いていた。先週の…

たまにCFって妙に実行時間の長い問題が出るな。 https://codeforces.com/contest/1728/problem/G

本番中のAC数が妙に少ない。 https://codeforces.com/contest/1728/problem/F

7問回なのに5問目から難易度高め。 https://codeforces.com/contest/1728/problem/E

本番中に解き切れず。 https://codeforces.com/contest/1717/problem/F

以前ライブラリ化しておいて良かったかな。 https://codeforces.com/contest/1721/problem/F

09/04(月) 午後4時半前に起床。インターン先定例会に参加した。進捗報告はあまり時間がなかったので「少しだけ進んでいます」と何の具体性もないことを言った。この少しというのは昨日寝る前に稼働した分である。 チラッとTLを見たら言語アップデートがされたとのツイートが目に入った。過去の問題を開いてみると確かに最新の言語が使えるようになっている。一昔前なら即座に何もかも忘れてコードゴルフに没頭していただろうが、今はちょっと……時間もモチベもない。特に何もせず会議に戻った。 勉強会は声について、特に機材と喋り方の話だった。オーディオインターフェイスや専用マイクに少しお金をかけるのはありかもしれない。…

Div2回ボス問がinteractiveになると、割と厄介な印象。 https://codeforces.com/contest/1715/problem/F

08/28(月) 午後4時半起床。インターン先の定例会に参加した。 先週は1on1で一瞬作業したきり一切稼働していない。最近進みがないと正直に報告したところ原因を聞かれたので、学業を理由に挙げた。しかし修論ヤバいですよと指導教員の先生に言われ続けているのがストレスになっていることは確かだが、かといって学業に邁進しているわけでもないのが現状のため、罪悪感を感じてしまう。 勉強会は会社の決算書の読み方だった。損益計算書とか貸借対照表とか、経営ラノベで名前だけ聞いたことがあったものの実例を見て興奮。ただし金額の正負だったり分類の慣例がややこしくて内容はあんまり理解できなかった。お金が入ってきているの…

なんか今回どれも問題文が読みにくい…。 https://codeforces.com/contest/1718/problem/D

問題文がなんか読みにくいな。 https://codeforces.com/contest/1718/problem/C