UTPC2020運営のidsigmaです。今回は問題に直接かかわることは少なかったですが、一応仕切り役をやっていました。適当に感想を書きます。 経緯 なんかのいみがやりたいと言い出す 乗り気になってメンバーを集める 今は亡きUtCoderでコンテストをやろうとして…

はじめに 本記事は、競プロアドベントカレンダー2020 の12/15分の記事です。ネタに困っていたんですが、Twitter上でクエリ平方分割に関する記事がほとんどないという声を見て、殴り書きではありますが本記事を作成することにしました。易しい問題を例にクエ…

公式解説とは異なる、経路数を考えることによる導出を紹介する。 考察 とりあえず、各を固定して考えよう。というのは、縦がマス、横がマスのグリッドにおいて、左下から右上に右移動と上移動だけで向かうときの経路の数に等しい。この値を掛け算するので、…

idsigmaです。HUPC2020 Day3の運営側の感想を書いていきます。 ちなみに解説リンクは以下になります。 https://drive.google.com/drive/folders/1zkt1cO4580zyypgXHAyxdIxiBBRM7TbZ?usp=sharing A この位置に何置くか難しいよね 大学合宿をテーマにしてみた …

公式解説とは異なる解法を紹介。典型的な考え方を知っていると頭をあまり使わずに済むかも。 問題 atcoder.jp 考察と解法 とりあえずを止めておく。区間]と重なる名産品の区間の数が答えなわけだが、異なるの値について同じ区間が重なると数えるのが面倒であ…

ある意味有名な(?)問題。解説と少し違ったので思うので書いてみる。 問題 atcoder.jp 考察 とりあえず、xorと和の関係を表す式であるところのを書いてみる。この式は、2つの自然数の足し算というのは、桁ごとの和(xor)と繰上がりに分解できるということを言…

解けたけど、コンテスト中のACは遠い...。 問題 codeforces.com 考察と解法 期待値の代わりに総和を考えることにする。スコアが和の形をしているので、2つの数の積が足される集合はいくつあるかを考えよう(0-indexedとする)。といってもこれは簡単である。あ…

こういうやつの定跡を知っているかが重要そう。 問題 onlinejudge.u-aizu.ac.jp 解法 木から頂点を取り除いていくので、森を扱うことになる。森の連結成分の数は、頂点の数から辺の数を引いたものである。これは期待値にしても変わらず(期待値の線形性)、を…

これが解けないのは悔しいんだけど、まあ難しいね...。 問題 codeforces.com 考察と解法 まず、どの3つのスイッチを取っても、その3つに関わるランプは存在しないという条件に注目する。これは、各ランプについて、押すと影響のあるスイッチは高々2つしかな…

こういう非自明な例が出てくると理解が進んで助かる。(間違ってたら教えてください) 問題 B - Hawker on Graph 解法 解説の議論を追っていくことにしよう。 単に足していくだけだったら... まず最初に、重みの辺を通るごとに所持金がだけ増え、負になること…

遅延セグ木で殴るのは、気持ちがいい。 問題 https://codeforces.com/contest/1285/problem/E 解法 座標について、その座標を覆う区間の数をとする。求めるものは、(考えるべき座標の両端のの値が0であることにすると)上でが連続している部分(つまり区間)の…

クレジットカードを持っていなかったので課金できず(?)、バーチャル参加をしました。179:50で全完、ひどいハマりかたをしたところはあったけどまあ自分の実力的にはこんなもんかなと思います。簡単に感想と解説を書いておきます。そのうち出る公式解説が丁寧…

本記事は、Competitive Programming (1) Advent Calendar 2019 - Adventarの12/11分として書かれたものです。 この記事について こんにちは、monoidsigma1です。皆さんはSegment Tree(通称セグ木)を知っていますか？セグ木というのは簡単に言うと、結合則 を…

A 曜日を格納した配列を作っておいて、入力と一致したら対応する値を出力すればよいです。 Submission #8612614 - AtCoder Beginner Contest 146 B 各文字ごとに丁寧にN回インクリメントすればよいです。 Submission #8612571 - AtCoder Beginner Contest 14…

2013 ICPC Aizu Regional をやった。 前日にやるセットだったのだろうか…。 Aを読む。やるだけなのでこるとんに投げる。Bを読む。やるだけなのでこるとんに投げる。(Bはともかく、Aくらい書いてもよかったかな…。) Aが通った後Cをrisujirohが無と言い書き始…

2019年11/09(土)に行われたICPC2019 Seoul Regional にkort0n,risujirohと参加してきました。日本からは唯一の参加チームとなりました。3泊4日の記録です。 出発まで 国内予選が終わった時点から、どこかには行きたいという話をしていたが、なんだかんだ皆忙…

2016 Bangkok Regional なぜか問題のダウンロードに時間がかかり焦る。前半をこるとん、中盤を僕、後半をrisujirohが読む。 読んだ感想は E:木クエリなのでrisujiroh F:文字列ゲーム、trie木っぽい G:数え上げ、これはrisujiroh H:なんやこれは、こるとん L…

毎日即位してくれ。 ICPC2017の筑波大会をやった。 Aをこるとんが読み通す。Bは僕が読んでいて、幾何だし全探索なので概要を伝えてrisujirohに投げる。その間に題意が掴めないと言われたCを読む。たしかに題意が掴めない(は？)。とりあえず放置して後ろを読…

注)本記事は読者として競プロerを想定しています。 AtCoder Jobsに何らかの求人を出しているFから始まる会社は3つありますが、そのうちの新宿のF社にインターンに行ってきました。せっかくなので簡単に記録を残しておきます。 採用まで 運ゲーです。 応募 Tw…

慣例に従って書くんですが、ちゃんと書くと面倒なのでめちゃくちゃ雑に書きます。 要約 2019/9/28(土)のABC142でAtCoder黄色になった。 ついに黄色くなりました！1950入ってから本当に長かった....idsigmaさんのAtCoder Beginner Contest 142での成績：87位…

idsigma(おきもち)です。ACPC2019に参加しました。福島に行くのはほとんど初めてで、こういう合宿系は(JAG夏合宿を除いて)初めてだったので、楽しみでした。 Day0 てんぷらさん、Tsutajさん、Tikeさん、こるとんとボドゲをした。モダンアートをやって微差で…

idsigma(おきもち)です。JAG夏合宿2019に参加しました。 Day1 コンテスト前 普通に集合30分前くらいに着いた。チームメイトの1人のrisujirohが20分遅刻した。この日は泊まらずに帰る予定だったので荷物が軽かった。 コンテスト だめでした。覚えてない。 本…

解説と考え方がちょっと違った。 問題 F - シャッフル / Shuffling 考察・解法 まず、操作列の左端が単調増加であることに注目してみる。となる部分があったときに、から文字目の並びは、回目以後の操作の影響を受けない。よって、この時点でこの区間の文字…

tourist コンテストでやった。他のチームと合同で、予定したチーム以外にも参加してもらえた。 https://not-522.appspot.com/contest/5665527433265152 台風の影響で全員揃う前に始まってしまった。 最初にBを僕が読んでいたら簡単枠だったので着いたらやり…

おきもち(idsigma)です。2019/8/31に行われたTTPC2019に参加しました。 昼食 わくさんとplatyplusさんとご飯に行くことに。何を食べようかなあと思っていたら... 大崎に非常に気になる店名のラーメン屋を見つけてしまった...らーめん食堂 あの小宮 https://t…

経験不足だった。 問題 F - Coincidence 解法 考察 をで割った余りがに等しいという条件が謎なので，もうすこしわかりやすい条件に言い換えることを目指そう。まず，がある自然数をで割った余りであるということから，が成り立つ。この不等式が成り立つため…

なんかだいたいこんな感じだけで通してしまったかも...。 問題 B - RGB Balls 考察と解法 最小化すべきものは，条件を満たすように人に区間を割り当てたときの長さの総和である。本問の場合，区間としては]という半開区間を考えるべきだろう。さて，整数があ…

はじめに ~この記事の経緯~ AtCoderで久々にBellman-Ford法を要求する問題が出題されました。Bellman-Ford法は蟻本でも紹介されている有名な単一始点最短経路アルゴリズムであり、負閉路の検出を行うこともできます。ところが今回扱う問題では、この負閉路検…

想定解は結構難しいと思ってしまった。 問題 Tally Counters | Aizu Online Judge 解法 「ある区間を選び、その区間の数字を同時に増やす」という操作が回であるとどういうことが起きるかを考えてみる。例えば、つのカウンタがあって、すべてが成り立ってい…

なんかAOJ-JOIの難易度6(AOJ/AtCoder-JOI)で難しいという声があり、実際苦戦したので記事にしてみた。 問題 A - オレンジの出荷 (Oranges) 有志の方の尽力によってAtCoder上で問題が見れるようになって嬉しい。ありがとうございます。 考察・解法 こういうの…