この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 - Adventarの20日目の記事です． 問題概要 各要素が $1$ 以上 $L$ 以下の整数列 $A = (a_1,\dots,a_N),B = (b_1,\dots,b_M)$ が与えられる． 整数に対して定義される全単射の写像 $f : [1,L] \rightarro…
AtCoder にレートがつき始めた AGC001 で初めてコンテストに参加して、苦節6年半、ようやくレッドコーダーになれました pic.twitter.com/oidsYpuzr7 — ホハム (@soiya_ksk) December 4, 2022 タイトルの通り、AtCoder でレッドコーダーになりました。折角な…
概要 ICPC2022模擬国内予選 (2022/Practice/模擬国内予選/案内 - ICPC OB/OG の会) に参加しました。 結果は ABCDEFG の7完で2位でした。 模擬国内2位！ﾍﾍｯ pic.twitter.com/ZwGQ2JWzuj — ホハム (@soiya_ksk) 2022年6月25日 チーム名は Bue World でチーム…
AtCoder Heuristic Contest 011 に参加しました。結果は 6 位でした。 解法を大雑把に言うと、「盤面と操作列を同時にビームサーチで探索する」です。 せっかくなので、時系列順にやったことをまとめてみます（問題概要は省略します）。 第一実装：最終盤面…
atcoder.jp 想定解とは異なる解法で解いたのでメモを残しておきます。（恐らく、対応する日本語記事はないと思ったため） 問題概要 N+M 個のマルバツ問題があり、そのうち N 個の問題の答えはマル、M 個の問題の答えはバツということを知っています。問題が…
ACM-ICPC 2018 国内予選に参加しました。 ・チーム決め 昨年度はIQ94としてhyksm, mtsd, polyominoで参加しましたが、エースhyksmが参加資格を失ってしまったので、新たなメンバーを探すところからスタート。 同期で競プロをやっていたのはkopricky, mtsd, p…
まとめます。 1/13 第4回ドワンゴからの挑戦状 58位 歩きながらEを考えてたら解けちゃったので急いで机に向かってコーディングしました。実装下手過ぎて泣きました。最後CじゃなくてD解きに行けばよかったかもなぁ・・・ 1/14 Atcoder Grand Contest 020 344…
参加しました。（久しぶりの更新） その前に今年のコドフェス振り返り。 予選A これはJAG夏合宿2日目夜に出ました。隣には住建という状況。 C誤読して大幅に書き直すはめになった記憶。Dは頭がバグって完全に停止しました。 住建はずっとデバッグで苦しんで…
3日間泊まりで参加しました。 ～遡ること一か月前～ 院試の発表まだだけど家で落ち着いている気分じゃないし大阪旅行に行こう！ ということで、急遽ICPCチームメンバーのpolyominoと大阪旅行に行くことに。 大阪旅行2日目。 実家に帰っていたパチコ様(pachic…
参加しました。 C問題 sugar water 100aか100bの水を入れる、もしくはcかdの砂糖を入れるを繰り返してf以下の重さの最も濃い砂糖水を作れ（ただし、100に対してeしか砂糖は溶けず溶け残りがあってはいけない)という問題。 不等式をきちんと立ててa,bのありう…
参加しました。 C問題 4-adjacent 長さNの a=(a_1,a_2,...,a_N) の数列を並び替えて隣り合う数の積が4の倍数になるようにできるかを判定せよという問題。 4の倍数がp個、4の倍数でないが2の倍数であるものがq個とすると、 2*p+1>=Nかq+2*p>=Nなら達成できる…
参加しました。 C問題 Cat Snake and a Voyage N個の島にM種類の定期船があって1とNをつなぐ定期船がないとき、2種類の定期船を使って1からNへ行けるか判定する問題。 1と直接つながっているかとNと直接つながっているかを調べて、どっちともつながっていた…
参加しました。 A問題 Getting difference 箱にN個のボールがあって各ボールにはA_iという数字が書いてある。以下の操作を行って数字Kが書いてあるようなボールを箱に入れることができるか？ ・箱から二つボールを取り出して、その差の絶対値を書いたボール…
参加しました。 チーム名はIQ94(由来は1994年生まれだから) チームメンバー hyksm ホハム(mtsd) polyomino でした。 始まる前のチームとしての作戦は以下の通り。 hyksm : (重そうな)実装担当 polyomino : 考察+実装 mtsd : 考察 要するに(私は使い物になら…
参加しました。 A問題 Biscuits ビスケットが入った袋がn個。i番目の中にはA_i個ビスケットが入っていて偶数個か奇数個食べたいときの袋の選び方はいくつかという問題。 偶数個入ってる袋と奇数個入ってる袋の個数をともに数えて、組み合わせを愚直に計算し…
そういえば、学科民3人で参加してました。 良いチーム名が思い浮かばず、1994年生まれという共通点から IQ94(1994)というチーム名に。 分担は以下のような感じになりました。 ---解いた問題--- A問題 polyomino B問題 hyksm C問題 ほとんどhyksm (一応考察 +…
参加しました。 C問題 pushpush 長さnの数列{a_i}から、空の列bに対して以下の操作をn回行う。 1. a_i をbの末尾に追加 2. bを反転 bを出力しなさいという問題。 bを作ってみて対応するaのindexを書いてみると、 n,n-2,n-4...,0,1,3,5...,n-1 or n,n-2,n-4..…
参加しました C問題 Reconciled? 区別可能なN匹の犬とM匹の猿がいるので犬と猿が隣り合わないように直線に並べる方法は何通り(%1000000007)あるかという問題。 NとMの差の絶対値が2以上のときは不可能。 NとMの差の絶対値が1のときは多い方から交互に並べる…
参加しました A問題 Shrinking 長さNの文字列tを長さN-1の文字列t'に変える操作を考える。 t'[i]はt[i]かt[i+1]を選ぶ。 このとき、全部が同じ文字に成るようにする最低回数を求めよ。 最初の文字列のi番目の文字のみになるような時の最低回数は貪欲的にでき…
参加しました C問題 Bugged N問の点数がs_iで定められているとき、10の倍数でないような最大の点数を求めよ。 無駄にDPをして1ケースだけ落としました。 D問題 Widespread N体の魔物のHPがh_iとする。爆発魔法が使えて、1体にAのダメージ他の全員にBのダメー…
参加しました。 A問題 Cookie Exchanges 3人がクッキーをA,B,C枚持っている時、各々が半分ずつ他の二人に渡す操作は何回できるか（奇数になったら終わり）という問題。 A,B,C → (B+C)/2,(A+C)/2,(A+B)/2になるので、二人の個数の差は1回の操作で1/2になる。…
参加しました。 C問題 Sentou スイッチを押すとそこからT秒間シャワーが流れる。 N人がt_i秒にスイッチを押した時、お湯の出る時間の総和を求める問題。 最初から順番にシミュレートしました。おわり D問題を見て完全に思考が停止し、E問題でmax,minを見れば…
参加しました。 問題A Sorted Arrays 長さNの配列Aを何箇所かで区切って、すべての部分列を単調非減少or単調非増加列にするには最低何箇所必要かという問題。 前から見ていって貪欲で取っていく。単調非増加か単調非減少かを判定し、そうでなくなるところで…
参加しました。英語はつらい。 Problem A. Oversized Pancake Flipper +-+---+-+みたいな列に対して連続するK個の±を反転させる操作で全てを+にするには最低何回必要かという問題。但し操作する箇所ははみ出してはいけない。 左端から-があったらひっくり返…
参加してました。 Easy. H2OとO2の量と1日当たりのコストが与えられるから何日生きられるか求める問題。H2OからO2を作ることが可能。 H2Oのみ、O2のみについて計算した後、O2が切れた時点でH2Oがまだ残ってたらOの量をH2Oコスト+2*O2コストで割ったら終わり…
参加しました。 C問題 怪文書 / Dubious Document n個の文字列が与えられるので、各々の文字列に対していくつか文字を取り出して別の文字列を作った時にどの文字列からでも作れる文字列のうち最長のものを求める問題。 出てくる文字をカウントしていって、各…
今回も数分遅刻。学ばない男。 A問題 AtCoder Group Contest 各人に強さA_iのついている3n人に対し3人組をn個作って、各グループの強さの中央値の総和を最大化する問題。 ソートしてi,3n-2*i-2,3n-2*i-1番目の人でグループを作っていくと最適。 B問題 Splatt…
参加しました。完全に忘れていて数分遅刻しました。 A問題 Airport Bus sortして前から貪欲した。終わり。 B問題 Colorful Creatures sortして前から足していってA[i-1]までの和S[i-1]の2倍がA[i]より大きければスルー。もしS[i-1]*2
参加しました。 A問題 Yahoo yahooを並び替えてできる文字列ならYES、そうでないならNOを出力させる問題。 y,a,h,oの出現回数を調べて終わり。 B問題 オークション N個出品されていてそれぞれ最初の値段がA_iで1日1品しか買えない。1日経つごとにすべて1円ず…
参加しました。 C問題 X: Yet Another Die Game サイコロゴロゴロして上の面の和がS以上になる最小回数を求める問題。 XI[sai]を思い出しました。小人くんが6の目と5の目をカタカタ回すのを想像。 6と5の面をひたすらゴロゴロすれば最大。あとは回数を計算。…
