Atcoder Regular Contest 80

参加しました。 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なら達成できる…

AtCoder Regular Contest 079

参加しました。 C問題 Cat Snake and a Voyage N個の島にM種類の定期船があって1とNをつなぐ定期船がないとき、2種類の定期船を使って1からNへ行けるか判定する問題。 1と直接つながっているかとNと直接つながっているかを調べて、どっちともつながっていた…

Atcoder Grand Contest 18

参加しました。 A問題 Getting difference 箱にN個のボールがあって各ボールにはA_iという数字が書いてある。以下の操作を行って数字Kが書いてあるようなボールを箱に入れることができるか? ・箱から二つボールを取り出して、その差の絶対値を書いたボール…

2017 ICPC国内予選

参加しました。 チーム名はIQ94(由来は1994年生まれだから) チームメンバー hyksm ホハム(mtsd) polyomino でした。 始まる前のチームとしての作戦は以下の通り。 hyksm : (重そうな)実装担当 polyomino : 考察+実装 mtsd : 考察 要するに(私は使い物になら…

AtCoder Grand Contest 017

参加しました。 A問題 Biscuits ビスケットが入った袋がn個。i番目の中にはA_i個ビスケットが入っていて偶数個か奇数個食べたいときの袋の選び方はいくつかという問題。 偶数個入ってる袋と奇数個入ってる袋の個数をともに数えて、組み合わせを愚直に計算し…

2017年度ICPC模擬国内予選

そういえば、学科民3人で参加してました。 良いチーム名が思い浮かばず、1994年生まれという共通点から IQ94(1994)というチーム名に。 分担は以下のような感じになりました。 ---解いた問題--- A問題 polyomino B問題 hyksm C問題 ほとんどhyksm (一応考察 +…

AtCoder Regular Contest 077

参加しました。 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..…

AtCoder Regular Contest 076

参加しました C問題 Reconciled? 区別可能なN匹の犬とM匹の猿がいるので犬と猿が隣り合わないように直線に並べる方法は何通り(%1000000007)あるかという問題。 NとMの差の絶対値が2以上のときは不可能。 NとMの差の絶対値が1のときは多い方から交互に並べる…

AtCoder Grand Contest 016

参加しました A問題 Shrinking 長さNの文字列tを長さN-1の文字列t'に変える操作を考える。 t'[i]はt[i]かt[i+1]を選ぶ。 このとき、全部が同じ文字に成るようにする最低回数を求めよ。 最初の文字列のi番目の文字のみになるような時の最低回数は貪欲的にでき…

AtCoder Regular Contest 075

参加しました C問題 Bugged N問の点数がs_iで定められているとき、10の倍数でないような最大の点数を求めよ。 無駄にDPをして1ケースだけ落としました。 D問題 Widespread N体の魔物のHPがh_iとする。爆発魔法が使えて、1体にAのダメージ他の全員にBのダメー…

AtCoder Grand Contest 014

参加しました。 A問題 Cookie Exchanges 3人がクッキーをA,B,C枚持っている時、各々が半分ずつ他の二人に渡す操作は何回できるか(奇数になったら終わり)という問題。 A,B,C → (B+C)/2,(A+C)/2,(A+B)/2になるので、二人の個数の差は1回の操作で1/2になる。…

AtCoder Regular Contest 073

参加しました。 C問題 Sentou スイッチを押すとそこからT秒間シャワーが流れる。 N人がt_i秒にスイッチを押した時、お湯の出る時間の総和を求める問題。 最初から順番にシミュレートしました。おわり D問題を見て完全に思考が停止し、E問題でmax,minを見れば…

AtCoder Grand Contest 013

参加しました。 問題A Sorted Arrays 長さNの配列Aを何箇所かで区切って、すべての部分列を単調非減少or単調非増加列にするには最低何箇所必要かという問題。 前から見ていって貪欲で取っていく。単調非増加か単調非減少かを判定し、そうでなくなるところで…

Google Code Jam 2017 Qualification Round

参加しました。英語はつらい。 Problem A. Oversized Pancake Flipper +-+---+-+みたいな列に対して連続するK個の±を反転させる操作で全てを+にするには最低何回必要かという問題。但し操作する箇所ははみ出してはいけない。 左端から-があったらひっくり返…

TCO2017 Round 1B

参加してました。 Easy. H2OとO2の量と1日当たりのコストが与えられるから何日生きられるか求める問題。H2OからO2を作ることが可能。 H2Oのみ、O2のみについて計算した後、O2が切れた時点でH2Oがまだ残ってたらOの量をH2Oコスト+2*O2コストで割ったら終わり…

AtCoder Regular Contest 071

参加しました。 C問題 怪文書 / Dubious Document n個の文字列が与えられるので、各々の文字列に対していくつか文字を取り出して別の文字列を作った時にどの文字列からでも作れる文字列のうち最長のものを求める問題。 出てくる文字をカウントしていって、各…

Atcoder Grand Contest 12

今回も数分遅刻。学ばない男。 A問題 AtCoder Group Contest 各人に強さA_iのついている3n人に対し3人組をn個作って、各グループの強さの中央値の総和を最大化する問題。 ソートしてi,3n-2*i-2,3n-2*i-1番目の人でグループを作っていくと最適。 B問題 Splatt…

Atcoder Grand Contest 11

参加しました。完全に忘れていて数分遅刻しました。 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円ず…

AtCoder Regular Contest 068

参加しました。 C問題 X: Yet Another Die Game サイコロゴロゴロして上の面の和がS以上になる最小回数を求める問題。 XI[sai]を思い出しました。小人くんが6の目と5の目をカタカタ回すのを想像。 6と5の面をひたすらゴロゴロすれば最大。あとは回数を計算。…

Atcoder Grand Contest 08

参加した。 A問題 Simple Calculator xに対して+1or符号反転を最小で何回やればyになるかという問題。 とりあえず愚直に場合分けすりゃ余裕っしょ!→x,yの符号と大小がややこしくてどっか間違えてWA。 人間にとってわかりやすい解き方を考える。 y-x,y+x+1,-…

第3回ドワンゴからの挑戦状予選

頑張って帰宅して参加。 以下感想。 A問題 動画検索 max(0,a+b-n) 終わり。 B問題 ニコニコレベル なんかバグらせる自信があったので後回しにしてしまったが、結局アレだった。 奇数番目からスタートするのと偶数番目からスタートするので場合分けすれば変な…

AtCoder Regular Contest 065

お酒を飲んだあとに参加したけど、あんまり影響はなかった。 以下感想。 C問題 白昼夢 4種類の文字列を追加していくことで文字列Sを作ることはできますかという問題。 dreamとdreamer、eraseとeraserは先頭の方の文字が一致しているので先頭から見ていくと泥…

AtCoder Regular Contest 064

AtCoder Regular Contest 064やりました。以下感想。 C問題 Boxes and Candles n個の箱に端の箱から順にキャンディーがa_i個入っている時、隣り合う箱に入っている個数がすべてx以下になるようにするには何個のキャンディーを取ればいいかという問題。 ぱっ…

CODE FESTIVAL 2016 参加

タイトルの通り、CODE FESTIVAL 2016参加してきました。 まずは予選の話から。の前にCODE FESTIVALに参加するまでのあらましを。 ・CODE FESTIVALに参加するまで 7月くらいに何か新しいこと始めようと思って、競技プログラミングを始める。 C言語を学科に入…

競プロ用ブログ始めました

code festival 2016本選参加記念に、はてブ開設しました。 競プロについて書いていく予定です。 これから成長していく方向性で。