現在12月31日午前4時50分 日記11日分溜まっています、今 これ書く意味ある？笑 2020/12/21 Codeforces Round #692 (Div. 1) B遅かったけど早々にDP方針を捨てられて良かった Cみたいな上から貪欲、何回も見てるので失敗はこれで最後に…(そもそも前提でヘマし…

日記、飽きてきたな まあ12月中は続けると思います 僕の書く文章読みにくくて見続けると嫌になってくる(？) 2020/12/14 起きて2限に出席 放置してる必修の英語のタスクを少し終わらせた ARのレポート一個も提出してないな どうしようもないね CF#689(Div. 2)…

2020/12/07 upsolveなど CGR12 C2. Errich-Tac-Toe (Hard Version) 証明各マスについてこの構築をしたときに変更する必要があるのが6回中2回なので6通り全てに対する変更回数の合計はちょうど2kしたがって6通りのどれかはk/3以下— てんぷら (@tempura_cpp) 2…

今年も日記付けます。12月ポエム投稿をしたくなるのは何故？ 2020/12/01 日付変わるタイミングでECR99があった。結果は微妙でBで焦って1ペナ出した分Cで慎重になってしまって踏んだり蹴ったりという感じ。E問題で TLE/WA のhackが多発してた、本番中詰めてた…

問題のリンク 問題概要 頂点辺からなる単純グラフが与えられる。次の条件のいずれかを満たすような部分グラフを1つ求めよ。存在しない場合は-1を出力。 部分グラフ内の全ての頂点が少なくとも個以上の隣接する頂点を持つ サイズのクリークである 制約 解法 …

問題のリンク 問題概要 のグリッドが与えられ、このグリッドを上下左右方向に傾けてタイルを動かす操作を行う。操作列は、(操作)*数字のように圧縮された状態で与えられる。最終的なタイルの状態を求めよ。 制約 解法 タイルに書かれた文字を無視すると、一…

チームgive us sociabilityで出場し、3完52位でした。 目標としていた4完&アジア大会進出が叶わず、同大学内でもライバルチーム2つに負けてしまい、良い結果とは言えない内容でした…。 模擬国内参加記 kkt89.hatenablog.com 模擬国内〜本番 チームでAOJ-ICPC…

ICPCチーム 去年と引き続き同学年のHyado君と組んで、今年2月に同じく同学年のhotman先生に加入して貰ってチーム結成しました。 チーム名は"""Give_us_sociability""" コンテスト前 前日にさっさとリハーサルを済ませておいてね、と伝えたが一人は当日朝4時…

昨日CodeChefの問題に出てきて分からなかったんですが、有名問題ぽい見た目をしているのにどう検索していいかよく分からなかった。 問題 自然数からなる長さの等しい数列 , であって、次の条件： を満たす時、 の最小値を求めよ(数列長は自由に取って良いも…

追記：これ分かりにくいので他ブログ見た方がいいです。僕も使いにくくて困ってるのでまた整備しようと思います。 区間をsetでやる奴苦手意識あるのでメモを残せるように書いた。 現状大したことは書いていないです。 やりたいこと 互いに重なりうる半開区間…

Day0 帰ります pic.twitter.com/aeHU6fRgdW— かっつ (@_KKT89) 2020年9月17日 次は郡山 会津合宿の前入りです！(素振り)— かっつ (@_KKT89) 2020年9月17日 会津に、行きたかった 人生— かっつ (@_KKT89) 2020年9月19日 社会情勢、許せねえよ……(政治的発言) D…

Day1 HUPC 2020 day1 のコンテストページが公開されました！https://t.co/DTWXxJAtZL北海道大学セットコンテスト時間： 2020-9-14（月）13:00 ~ 16:00（3 時間）参加登録よろしくお願いします！#hupc2020— HCPC 北海道大学競技プログラミングサークル (@hcpc…

純粋培養な僕がWUPC4th開催にあたって、色々パソコンカタカタ分からん！ってなった所のメモを残しておきます。 当方gitを触るのも初経験でございました…(この機会に触れられてかなり良かった、周りの環境が競プロerだと気兼ねなく質問しやすい(当社比)) rime…

Round1はA1とBを解いて通過でした. リンク https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A1 問題概要 2次元平面上に左下の点が, 右上の点がの長方形が個与えられる. 1からNの各について, を次のように定める. この時, を…

問題のリンク 問題概要 クエリ毎にN個の区間が与えられる。次の条件を満たす区間の部分集合のサイズの最大値を求めよ。 部分集合内の任意の区間のペアについて、どちらかが片方を完全に包含している。または共有点を持たないかのいずれかが成立する。 制約 …

問題概要 始め頂点(0,0)にいる。1回の操作で隣接する格子点を1つ選んで移動することができる。ただし、 かつ を満たす範囲には障害物があり移動することが出来ない。 回以内の操作で到達可能な格子点の総数を求めよ。 制約 解法 まず障害物が無い時を考える…

Solved By KKT89TopCoder: 19CodeForces: 949AtCoder: 1567AOJ: 361yukicoder: 211Sum: 3107 https://t.co/7ZgirqY9aKか— かっつ (@_KKT89) 2020年5月8日 3100問ぐらい解きました

一応分かった気がするのでメモ 議論間違ってたらすいません… リンク https://codeforces.com/contest/1349/problem/D 問題概要 N体のスライムがいてそれぞれ枚ずつビスケットを所持している。毎ターン毎に次の操作を繰り返す。 枚から一つ等確率でビスケット…

(2021/02/22:追記) アクセス分析見るとこの記事が割と閲覧されていて震えている…内容が不十分なところがあると思うので時間あれば手直ししたいと思ってます。 経緯 Topcoderとは コンテストの説明 Web Arenaでコンテストに出る 実際に問題を解く Java applet…

問題のリンク 問題概要 内接円の半径がRとなるような、辺の長さが全て整数の三角形を全て求めよ。 制約 考察 内接円の半径と三角形の3辺の長さの関係を知りたい→面積についての等式を立てる 三角形の3辺の長さをとします。この時ヘロンの公式を用いると、 と…

問題のリンク 問題概要 N個の景品から成るコンプガチャがあり当選確率はいずれも同様に確からしい。全ての景品をM個以上手に入れるまでの操作回数の期待値を求めよ。 制約 解法 が小さいのでのDPが間に合う。 を1個揃ってるのが 種類、2個揃ってるのが 種類…

リンク www.acmicpc.net 問題概要 要素数Nの数列Aが与えられる。区間内の(最大値)-(最小値)を満たすような数列Aの連続する区間で最長の長さを求めよ。 制約 考察 区間の最大値、最小値を見ていく問題ではスライド最小値(最大値)の考え方で解けるものが多く、…

問題のリンク 問題概要 N×Mのグリッドが与えられ、その内幾つかのマスに数字の書かれたタイルが置かれている。このグリッドに対して左詰め右詰め上詰め下詰めの操作を好きな順番で好きな回数行える。初期盤面は左下詰めで与えられる。左下詰めの盤面の状態で…

人と違う解法(?)だったのでメモ書き リンク codeforces.com 問題概要 長さNの数列が与えられ、次の操作を何回でも行うことができる。 隣接する値が同じ項を選んで、取り除く。そしてそこに元の値+1の要素を挿入する この時達成可能な数列の長さの最小値を求…

完全に忘れていたので復習 リンク atcoder.jp 問題概要 長さNの数列A,Bが与えられる。それぞれの数列から要素を取り出してくる方法は通り存在するが、その通りの要素同士の和について全てXORを取った値を求めよ 制約 考察 当然愚直は間に合わないので桁毎に…

リンク atcoder.jp 問題概要 N個のマスがあり最初はどのマスにも積み木は乗っていない。N個のマスのうち積み木が最小のマスを一つを選んで、現在の積み木の高さのMAX~MAX+Dの高さの好きな高さまで積み木を載せる操作を行う。N個のマスの積み木の高さが全てH…

勉強したことのメモ書きを残しておきます catupperさんのこの資料を読んで勉強しました。 辺彩色 from Ken Ogura www.slideshare.net 二部グラフの辺彩色については具体的に12ページから述べられています。 Konigの定理 任意の二部グラフの辺彩色数は二部グ…

これのK問題を解いたので、解法のメモを残します。 問題概要 2*Nのグリッドが与えられ、好きな点を一つ選びそこから縦横斜めに隣接する一つのマスを選んで移動する、ただし同じ頂点は二度通ることができない。この時全てのマスを丁度一回通るような移動の総…

自分が参加した(解いた)コンテストの備忘録です 一杯あった方が楽しい(？)ので抜け漏れているコンテスト募集してます 普通のコンテスト JOI2018 予選模試 2019の予選模試について調べていたら見つけた NPCA Programming Contest 2019 解説のリンク: NPCAcon2…

リンク https://codeforces.com/contest/808/problem/E 問題概要 ナップサック問題 ただ制約が特殊 解法 い つ も の dp[i]:iの重さを持つ時の価値の最大値,というDPは計算量がO(NM)になってしまい間に合わない。 明らかに怪しい制約があるのでそれを生かす…