競技プログラミング
ICPC 2024 Asia Yokohama RegionalにICPC OB/OGの会（JAG）スタッフとして参加しました。 -N日目 ご飯を食べながらOB/OGの会の勧誘ができるようにサンドイッチマンになろうと思い立つ。構想としては、勧誘用のスライドを印刷したものをクリアファイルに挟み…
問題はAtCoderを参照。コードはGithubにあります。 ChatGPT(無料)とGithub Copilotを使っています。 準備 日課の散歩をして、昼寝をしてから万全の状態で挑むつもりだったが、テレビでデルタ・フォースという面白い映画がやっていた。それを見ていたら30分前…
はじめに 数学セミナーの2023年7月号に、数学オリンピックの特集があった。その特集の中には、過去の参加者の方々が数学オリンピックの思い出についての記事と、「わたしの1問」という思い出の問題についての記事があった。後者は難しそうなので読まなかった…
今年もICPCアジア地区予選のお手伝いをして来ました。今年で3回目です。 私が手伝った日は11/16,17の二日間です。 前日夜 去年、必要になった張り紙を手書きで済ませたので、今年はちゃんと印刷できるようにパワポで張り紙を作り始めます。作り終わったあと…
注意 これはあくまで非公式の文章です。公式のルールやアナウンス、指示と矛盾する場合は、必ずそちらの方に従ってください。 また、この文章は日本で行われるアジア地区予選についてなので、他の国で行われる大会には通用しないと思われます。 これは何？ …
今年もOBOG会スタッフとして参加してました。 -X日目 ISUCONに参加登録してから、今年のISUCONとICPCが被っていることに気がつく。申し込んだのが自分な上、チームで参加登録したので、自分が参加しないわけにはいかないだろうということで、ICPC一日目は受…
もし、あなたが 今後もこの大会が続いていってほしいと思っていて、かつ、 ICPCへの参加資格がなくなっている のならば、ぜひICPC OB/OGの会（ICPC Japanese Alumni Group、通称JAG）に入会してください。日本で行われるICPCアジア地区予選は、JAGスタッフに…
atcoder.jp 方針 解説にも書いてあるが、集合の大きさが等しいのはサイズが等しいときのみ。各接頭辞に対する要素の集合は前から順番にSetに突っ込んでいけば簡単に求められる。 集合が等しくなる瞬間のサイズは、次のようにして求められる。（尺取的な気持…
これは、2019年12月22日に行われた飲酒プロコン（忘年会0次会）の参加記です。 開催されるまで 11月終盤ごろに、amylaseさんが「今年中に飲酒プロコンをやりたい」と言っていたので、「やってください！」とお願いしておきます。12月の初めに「今年中はさす…
この記事はCompetitive Programming (2) Advent Calendar 2019の21日目の記事です。 飲酒は20歳になってからです。未成年の人は20歳になってから読みに来てください。 僕がRatedコンテストにお酒を飲みながら参加している理由と、（自分の中での）レギュレー…
この記事はCompetitive Programming (2) Advent Calendar 2018 - Adventarの15日目の記事として書かれました。 この記事で言いたいこと： ACM-ICPC OBOGの会では、競技プログラミングが大好きで、ICPCを引退した人達を常時募集しています！ FrontPage - ACM-…
（注）この記事は、僕が個人の意思で公開するものであり、IOI2018事務局さんは内容に一切かかわっていません。 IOI2018の競プロ経験者向けボランティアに参加するために、僕が送ったメールを（個人情報を隠して）公開します。参加したいけど、メールに何を書…
同僚に「最近ARCのC,Dを毎日2問ずつぐらい解くようにしてるんだよね」という話をしたら，「何か難しい問題あった？」と聞かれた．（お前ら僕よりよっぽどレーティング高いやろ！） しばらく考えて解法が思い浮かばなかったこの問題を教えた．ちなみに，問題…
ICPCのアジア地区予選のお手伝いをしてきました。ICPCに行くのは2年ぶり、JAGスタッフとしては初めての参加でした。 0日目（12月15日） この日は通常通り会社に行って働いていた。つくばは行ったことがあったし、東京からはそんなに遠くないので、出発時刻を…
この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの記事として書きました． この記事に，技術的に有用なことはありません． 「証明を書こう！」という話です． 何か月か前に，とある方から次のような質問をされました． 競技プ…
チーム名はyotei_awanaiです． チームメイトのハンドルを知らないので，N君とK君とします． 結果 どう考えても5完セットでした．6完ワンチャンだったと思います．でも3完74位です． 引退 & JAG入会待ったなし． 結論 コミュニケーション大事 練習大事 平常心…
ケアレスミスでEasyを落としました．（何やってんだか．） 解いた問題 Easyのみ.120点ぐらいでの提出だった． 問題概要 整数 とが与えられる．（） 1 ~ 100 までの整数のうち，個の数 を選び，どのように を選んでも，がにならないようにする． 解法 等差数…
ぼくはAもんだいをとおしました．ぼくがAをとおしたあとは，くりんぺっとさんがB,Cをとおして， しゅんかんてきにいちいになりました．そのあと，EやFをおもにかんがえましたが，ほうしんがまとまらず， すわっているだけになりました．きょすくんが「Hがや…
オリセンで開かれたICPCアジア地区予選に参加してきました．アジア地区予選に出場するのは個人でも学校でも初の経験でした． 結果は4完29位(大学別24位)でした．29位だったのでリクルートさんからNiku Awardをいただきましたありがとうございます． チーム編…
解説では，Suffix Array + Range Minimum Queryでの解法が紹介されていましたが，僕はクエリ先読み + Aho-Corasick法で通しました．というか，Suffix Arrayよくわかってない．ある人には，「クエリ先読みするなよ」と言われました． 概要 文字列SとQ個のクエ…
概要 牡牛がN頭いて，M個のコートに1頭ずつ割り当てたい． 牡牛はそれぞれ好むコートが決まっている． 割り当て方は何通りあるか． 解法 bitDPやるだけ． ただし，愚直に実装するとMLEを起こすはずなので，配列の再利用をする． int N, M; int P[30]; int B[…
POJ100問AC記念． 概要 N人の子供が一枚ずつカードを持っていて，輪になって並んでいる． K番目の子供からスタートする．まず，現在選んでいる子供を輪から除外する．除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ．これを繰り返す…
概要 N次正方行列があり，初期状態ではすべての成分が0である． T個のクエリが来て，内容は (x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う． (x1,y1)の成分を答える である． 解法 2次元のBITを用意する．これは，(1,1),(x,y)によって定まる矩形領域の値…
概要 2次元格子上においてある黒い石の情報が与えられる． ある格子点において，x方向，y方向共に黒い石に挟まれているならそこにも黒い石を置く． 最終的に格子上においてある黒い石の個数はいくつか？ 解法 扱いやすいように座標圧縮をしておく． 各x座標…
概要 一次元座標x[i]と，値v[i]が与えられる．iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である．コストの総和を求めよ 解法 座標でソートしておく． 各iについて，BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計…
思いがけないところではまったのでメモ． 概要 線分の上を物体がある方向に向かって動く．2つの物体が衝突すると反対に動く． 一番最後に落ちる物体の名前とその時間を求める． 解法 蟻本の蟻と似た考え方．最後に落ちるものを特定するには，左側にどれだけ…
概要 20個のボウルが一列に並んでいて，あるボウルを選ぶとそのボウルと両側のボウルが一緒にひっくり返る．（端っこのボウルを選ぶと2個だけひっくり返る） 全てのボウルを正しい向きにするには，何回の選択が必要になるか？ 解法 端っこから地道にシミュレ…
ほろ酔いコーディング 概要 5行6列のライトのついたボタンがあって，ボタンを押したらそのボタンと4近傍のボタンが反転する． 与えられた状態からライトを全部消す押し方を求める． 解法 蟻本まんま．幅と高さをいじればそのまま通用する．．．と思う． 僕は…
POJ 2566は，そのままだとしゃくとりできないが，累積和にしてソートするとしゃくとりできるようになる．なぜならば，問題が知りたいのは合計の絶対値であるから，累積和の差だけを考えればよいため．カンニング先→POJ-2566 : Bound Found - komiyamの日記 P…
概要 N個の提灯が下がった糸を垂らす．片方の端点はAとし，他方をBとする． このとき，糸は重力にしたがって垂れ下がる． i番目の提灯の高さをH_iとすると， H_1 = A, H_N = B, H_i = (H_(i-1) + H_(i+1)) - 1 が成り立つ． あるAが与えられたとき，全ての提…
