クレジットカードを持っていなかったので課金できず(?)、バーチャル参加をしました。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上で問題が見れるようになって嬉しい。ありがとうございます。 考察・解法 こういうの…

皆さんこんにちは、おきもちです。2019年7月12日(金)に行われたICPC2019国内予選の参加記です。やや長いです。 結果 チームokimochiは全体4位で、無事アジア地区予選横浜大会に出場できることになった。やったね！5完内1位でした、全体的に早かった メンバー…

オイラーツアーとかはともかく、この解法が思いつけないのは悔しい...。 問題 F - Colorful Tree 解法 まず、色の変更のことは忘れて、「木上の点間の距離を求めよ。」というクエリに効率的に答えることについて確認する。このクエリに答えるには、の最小共…

クラスカル法あたりの考え方をちゃんとわかっているかを問われている気がしてよかった。 問題 G - MSTX 考察・解法 最小全域木だしクラスカル法っぽく考えたい。まずのとき、つまりの辺から優先的に使うことを考えてみる。このとき、もしの辺を使うことがあ…

やっぱりAGCの問題は綺麗で良いなあ...。 問題 D - Rotation Sort 解法 Rotation操作はややこしいので、言い換えを考える。よく眺めると、右シフトは「好きな数を今の位置より右側の好きな位置に移す」と言い換えられる。左シフトも同様なので、結局 「コス…

参加資格ありのチーム内で5位！チームとしての上限に近いパフォーマンスだったと思う。 Aをまず通す。その間にBは01bfsやるだけですと言われたので受け取り、難なく通す。少しバグらせたのでここまで15分くらいかかってしまったが、そこそこ早かったようだ。…

3時間2セット。 RUPC2017Day3 こるとんがAを通す。僕がBをやろうとするがうーんとなり、DがいつものDijkstraらしいのでBをこるとんに渡してDを受け取る。risujirohがCを通したあとDを僕が書く。問題を誤読していて(え…)焦るがまあ通る。その後Eが遅延セグ木…

こういう問題を解いていると競プロ楽しいなと思う(やはりパズルが好きなのでは？)。 問題 D - Go Home 解法 すべてのマンションが地点から見て同じ方向にあるときは自明なので、そうでない場合を考える。 初期状態から考えるとつらい気持ちになるので、終了…

方針立ってから時間かけ過ぎた...。 問題 D - Squirrel Merchant 解法 まず1つの金属について考える。例えばなら、Aでどんぐりを金にして、Bで金をどんぐりにするという行為以外ありえない。このように不等号の向きを見れば、ある程度取るべき行動が確定する…

う 問題 G - Chicks and Cages 解法 dpっぽい雰囲気はあるが、何の整理もなしにはうまくいかない。まず、ある鳥かごに振り分けられたひよこの集合をとする。この鳥かごで発生するストレスの値はである。つまりストレスの値の総和は、ひよこの大きさに、その…

コンテスト中に解き切りたかったけど、細かいところも少し要求されるので厳しかったかな...。 問題 F - Frog Jump 解法 蓮以外の点に行かないようにしないといけないので、まずという条件が得られる。この下で、を決めたときの動きを観察すると、以下のよう…

これが解けて紫になった。 問題 Problem - E - Codeforces 解法 をsortした列を考える。この列を眺めていると、区間を消去できることの必要条件は 上で述べた列について、の値が未満のところまでは昇順である」かつ「がより大きいところからは昇順である」 …