2020-01-01から1年間の記事一覧
メモ。 Problem - D - Codeforces 問題概要 単調非減少な数列Aが与えられる。この数列に対して、次の操作を繰り返し行い、単調非減少ではない状態にしたい。 ・ 隣接する二つの要素を取り除き、そこに二つの要素の排他的論理和を挿入する。 必要な操作回数は…
サクッと解けた。この回はずいぶん簡単だったと思う(KickStartって結構難しい問題あるんだけど...) codingcompetitions.withgoogle.com 解法 簡単にいうと、人 i が文字xを経由して人 j に到達する、というルートを、文字xについて26通り試すと、最短ルー…
これもやさし目なABC-Fって感じ でも面白かった codingcompetitions.withgoogle.com 問題概要 二次元グリッド上にN人の人がいる。N人をある格子点からX軸に平行に一列に並べたい。人が格子点から格子点に移動するためにかかるコストは2点のマンハッタン距離…
ABC-Eぐらいでありそう 問題リンク: codingcompetitions.withgoogle.com 問題概要 ある正整数Xが"boring"である、とは次のように定義される:「Xを文字列として見た時、左から数えてi(1-index)桁目の偶奇がiの偶奇と一致する」。L以上R以下の"boring"な数は…
B - First Second Trie木を使った実装を説明します。 実装については algo-logic.info を参考にしています。Trie木全体の実装などはこちらを読むと良いと思います。ここでは、この問題を解くために必要な部分だけを記述します。 問題概要 文字列がN個与えら…
昔のARCもちゃんと埋めていこうと思います。 問題概要 無向グラフが与えられる。人i(1 <= i <= N)は始点Sから出発して、自分より小さい番号の頂点を通らずに頂点iまで到達できるだろうか?到達できる番号を全て列挙せよ。 頂点数、辺数共に2e5以下。 解法 解…
ググり力、灯台下暗しと言ったところでした。 レートは冷えたけど、学びもありました。Eまでは悪くないペースだったと思うけど... A問題 こう言う問題で秒単位で時間を削るなら3項目演算子使うべきなんだろうけど素直にif文を書いてしまった。いや別にいいん…
2020/7/25 M-SOLUTIONSプロコンオープン2020で、AtCoder青色レートになりました! 実に一年近くを過ごした水色レートを卒業できてとても嬉しいです。 実は青色レートが現実的な視野に入ってきたのはごく最近です。6月の後半ぐらいで、1800〜2100程度のパフォ…
解説ACしたメモです。 問題ページ:https://codeforces.com/contest/1370/problem/D 問題概要 長さNの数列Aが与えられる。長さKの部分列に対して、部分列の"cost"を次のように定義する。 ・cost := 部分列の奇数番目の要素全体の最大値と、偶数番目の要素全…
実質1行のDPなんですが、コンテスト後のTLを観たら結構いろんな解き方がされていて、割と自分の実装は短く済んでいる方だということがわかったので結論だけ簡単に示しておこうと思います。 問題ページ:https://atcoder.jp/contests/agc046/tasks/agc046_b …
今更ですが、GCJ R1Bが4/20 午前1:00(!)にあったので出場しました。流石に時間が遅いので出るか迷いましたが、別にレートがつくわけではないので(ABCもレートがつきませんでしたね)、爆死しても損はないと言うことでダメもとで出場しました。 結果 845…
こんにちは。今回はGCJ2020 Round1Aに参加した記録を残そうと思います。 私、lynmisakuraは、現在AtCoder水色、codeforces青色です。もちろんWorld Finalsに本気で出られるなどとは思っていませんし、Tシャツだって現実的には厳しいと思いますが、せめてR1突…
昼から酒を飲むなどしたあとコーヒーを決めてなんとかこどふぉに出た。案外頭は回ったが(9時スタートはAtCoderと同じなのでそれに体が慣れてるとは思う)紫は遠いと思った 今日の精進 codeforces 精進はしていないのでHello 2020で解いた問題だけ https://c…
今日の精進 最近全然こどふぉを埋められていない... AtCoder atcoder.jp 400点なのにちょっと捻ったDPは全然書けない。最初1次元のDPで、1個前とK個前とを参照すればいいと思ってた atcoder.jp 学生最強コン予選F。数列に対する数学の典型必須要素が詰まって…
昨日ブログ書いたのが日付変わったあとだったのでこう言う題名になってしまった。書いてる途中で日付が変わってしまった 今日の精進 AtCoder ・冬休み中に数列の扱いについて「典型」を明文化できるように(ある程度)したいのでScoresの点数でソートして全…
あけましておめでとうございます。もう1月2日になってしまいましたが、みなさん今年もよろしくお願いします。 感想1 歳を感じる。明らかに新年を作業的に迎えるようになってしまった。 感想2 新年早々飲酒をしましたが、生ゴミみたいな後味のビールを飲むと…