2017年度ICPC模擬国内予選
そういえば、学科民3人で参加してました。
良いチーム名が思い浮かばず、1994年生まれという共通点から IQ94(1994)というチーム名に。
分担は以下のような感じになりました。
---解いた問題---
A問題 polyomino
B問題 hyksm
C問題 ほとんどhyksm (一応考察 +mtsd)
D問題 mtsd(書いてバグらせる人) polyomino(それを怒る人)
E問題 hyksm 幾何ライブラリ (polyominoも一緒に考えてたはず)
---手を付けようとした問題---
G問題 mtsd polyomino (考察まで)
H問題 hyksm
まあこんな感じでした。具体的にどんな感じでやったかは以下のような感じ。
13時半くらいに学科控室に集まる。polyominoと昼ごはんを買いにファミマへ。
控室に戻ったらhyksmも到着。昼ご飯を食べながら駄弁る。
13時50分くらいに慌てて環境を整えだす。
全員普段のエディタがバラバラ。いつもはsublime text使ってるけどまあpolyominoに合わせる。hyksmはvimを準備。
一応キーボードを持ってきていたのでちゃんと動くかチェック。macだったので若干変。まあ仕方なしといった感じ。
14時にページを更新するも問題が出ない。違うページ見てるか?と焦る。コンテスト延期の情報をTwitterで確認。
結局3時までだったのでダラダラ駄弁る。
結局開始までに特に作戦を決めず。最初に座ってたpolyominoにAを任せる。まあ通す。
その間にBとCをhyksmと読む。Bはとりあえず前から見ていけばいいねという感じ。Cは獲得しうる点数のmaxとminさえ見ておけばいいね、被ったらもう一方も見ようねという感じ。
結局二つとも実装をhyksmに投げて、その間にD問題を考える。
問題文の解釈に手こずる・・・ まあ2分探索だろうな~ これレベルの上げ方貪欲でいいの?という話に。
その間にhyksmが2問とも通す。流石、頼りになる男。
貪欲でいいことにようやく気付き、すかさず書いてやるぜ~とPCの前に。
普通に書くのに手こずる。安定の実装力。後ろでE問題はやるだけだとかHも解けるぞとか言われていて普通に焦る。
Dを一応書ききってテストケース実行。なんかおかしい、つらい。デバッグタイムへ。
polyominoと一緒にどこがおかしいのかを調べ始める。なんかいろいろヤバそうという話に。
その間にhyksmがH解けたというのでHを書いてもらう。
結局、2分探索のスタート範囲とかboolの条件がおかしいということが分かる。(頭がこんがらがっていてもうダメ)
H書き終わってテストケースも通ったとのことで提出。WA。よく聞いてみると勘違いしていた模様。悲しいね。
まあ気を取り直してD問題修正へ。上手く行ってそう。提出しよう!
提出用ケースを見るとanswerが-1ばかり。不安になって問題データを確認。回数制限がでかすぎるの多くない?ということで一応投げるかと提出。通りました(*^▽^*)
ここらへんで確か2時間くらい経過?
hyksmの持ってきた幾何ライブラリをフル活用でE問題を解きに行く。その間にF,Gを考える。
Fはグラフ関係のなにかだけどグラフはよく知らないしパス。Gは算数力が試されそうだしGやるぞ!という感じでGの考察へ。
まず許される状態を考えて、二人だけで閉じた関係の時だけ変なことが起きるんだなということが分かる。後は白丸、黒丸、仕切りの並び替え問題に帰着だ!という感じに。
まあE通した段階でもう間に合わなそうだなって感じになって終了。
順位を見てみると7位!E通したチームが少なかったのが影響したかという感じ。まぁF通したチームは多かったけど・・・
まあ本番は同じ大学のチームがまあ強い。はい。って感じになるんでしょうが。5問解けたらうれしいなって感じの目標で。
初の参加となりますが、チームワークが問われていて役割分担とか面白いですね。
僕は当日は実装することはやめて、頑張って実装を応援しようという感じになりましたとさ。(これで考察もボロボロだとただの置物になってしまう恐怖)
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...,1,0,2,4...,n-1
となるのでそれをもとにやりました。
D問題 11
1~nが少なくとも1つ含まれるn+1個の要素のある数列aに対して,
要素kの部分列(連続しなくてよい)は何種類ありますか?という問題。
1つだけかぶっているということは明らか。かぶっているのをpとする。
(aコ) p (bコ) p (cコ)
という感じの列のとき,普通に全パターンを取ってくると
(aコの中のいくつかから選ぶ) p (cコの中のいくつかから選ぶ)
というようなやつだけ2回ずつ数えているので,それだけ減算しました。
(コンビネーション書くのに時間をかけまくるという体たらくっぷり)
E問題はなんかimosやればいいんだろうなというところまではなんとなくわかったけど、上手くできずに終了。
順位 307位 パフォーマンス 1831 新レート 1977(-16)
算数ゲー来ないかなぁ()
AtCoder Regular Contest 076
参加しました
C問題 Reconciled?
区別可能なN匹の犬とM匹の猿がいるので犬と猿が隣り合わないように直線に並べる方法は何通り(%1000000007)あるかという問題。
NとMの差の絶対値が2以上のときは不可能。
NとMの差の絶対値が1のときは多い方から交互に並べる場合のみ。
N=Mのときは、犬から始めても猿から始めても良い。
あとはN!とM!を求めましょう。おわり。
D問題 Built?
N個の街があって、街の座標(a,b)と(c,d)の間に道を作るには、
min(|a-c|,|b-d|)円がかかります。街同士を繋げて全ての街を行き来できるようにするには最低何円必要かという問題。
x座標とy座標でソートしたものを各々作り、隣り合う点同士に枝を貼って最小全域木を求めればよいです。
実装下手くそすぎて泣きかけた。
E問題 Connected?
長方形の内部(境界含む)に数字が1~Nが2つずつ含まれているとき、長方形の外部に出ずかつ曲線が交わらないように同じ数字を結ぶことができるかという問題。
数字つなぎとかそんな感じのパズルに近いが、適当に曲線を書いていいので本質的にはかなり違いそう。
境界上になければ、空間を歪める感じで、同じ数字を重ねあわせることができるので、数字がともに境界上にあるときだけを考えれば良い。
辺に沿うように、座標軸をとって、辺上で現れる順番に数字の列を作りました。
後は交わらないようになっているかを考えれば良い。
盲目的に再帰をやったけど、stackを使えばいいというのはそれはそうなので非常に悲しい。
終了1分半前にギリギリ通して一安心。
順位 159位 パフォーマンス 2138 レート1993(+18)
地道に黄色に戻していこう!(溶ける時は一瞬)
AtCoder Grand Contest 016
参加しました
A問題 Shrinking
長さNの文字列tを長さN-1の文字列t'に変える操作を考える。
t'[i]はt[i]かt[i+1]を選ぶ。
このとき、全部が同じ文字に成るようにする最低回数を求めよ。
最初の文字列のi番目の文字のみになるような時の最低回数は貪欲的にできるので、全部の文字についてやりました。
B問題 Colorful Hats
1~N匹の猫が色のついた帽子をかぶっている。
i匹目の猫から見ると他のN-1匹はa_i種類の色の帽子をかぶっているとする。
{a_i}が与えられた時そういうパターンは存在するかという問題。
とりあえず考察。
(1) a_iで出てきていい数字は2種類まで(3種類以上あると無理)
(2) 2匹が同じ帽子をかぶっていると必ずその色はすべての猫から見える
(3)a_iで出てくる数字がk,k+1のときkの方の猫は全て別の色の帽子をかぶっている
以上で無理な場合を弾いていけば解けました。
C問題 +/- Recrangle
H*Wの行列が以下を満たすようなものを構成しろ(無理ならNo)
・行列の全要素の和は正
・h*wの部分長方形を取り出しても要素の総和は負
貪欲にh行w列ごとに-hwを配置していけばいいんじゃね?というノリでやったら無事死にました。
H=1,W=3,h=1,w=2で落ちるようです。( 2, -3 ,2 とすれば良い)
全然気づかなかったのでもうダメ。
D問題 XOR Replace
問題文は結構面倒なので省略。
a1,a2,....,x の値のセットは常に一定なので、末尾とのスワップのみでb1,b2....bnを作ることを考えました。
多分方針はあってるような気がするけど、時間も足りず終了(後半が本質らしいのでやっぱ無理)。
順位 275位 パフォーマンス 1996 レート1975(+2)
精進あるのみ。
AtCoder Regular Contest 075
参加しました
C問題 Bugged
N問の点数がs_iで定められているとき、10の倍数でないような最大の点数を求めよ。
無駄にDPをして1ケースだけ落としました。
D問題 Widespread
N体の魔物のHPがh_iとする。爆発魔法が使えて、1体にAのダメージ他の全員にBのダメージを与えられるとき、何回使えば全員倒せますかという問題。
回数について2分探索してしまえばよい。
とりあえず全員にBのダメージを与えて、後何回A-Bダメージを個別に与えるかを計算しました。
F問題 Mirrored
正の整数nに対して左右に反転させて得られる整数をrev(n)としたとき、
rev(N) = N+DとなるようなNはいくつ存在するかを求める問題。
rev(N)-N= (10^m-1)x_1+(10^(m-1)-10)x_2...
的なことを考えて上から順番に決めていく方針をとりました。
サンプルが通ったので投げたら半分くらいWA。どこがバグってるのか分からず。
C,D書くの遅かったけどF問題解けたっぽいし投げるか!というクソプレイングをした結果、爆死しましたとさ。良い子のみんなは真似しちゃだめだぞ!
427位 パフォーマンス 1452 新レート 1973(-48)
青くなりました チャンチャン。
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になる。よってシュミレーションすればlog(A,B,C)でいけるという感じ。(3人とも同じ枚数なら無限に続く)
B問題 Unplanned Queries
N点の木に対してまず各辺に0をふった後、M個のクエリをやる。
「a_i,b_iの2頂点間のパスに現れる辺にふってある数字を+1する」
全部の辺にふってある数字が偶数になるような木は存在するかという問題。
なんとなくa_i,b_iに現れる数字の回数の偶奇がそのまま関係してそうだったので、全部偶数回か調べたら通りました()。
C問題 Closed Rooms
H行W列の部屋があり、移動は接する部屋のみ。閉じている部屋と開いている部屋が最初存在していて、1,H行目、1,W列目についたらゴール。
K部屋以下分移動し、K個以下の部屋を開けるという魔法を何回使えばゴールできますかという問題。
K個部屋開けてK部屋進むという一連の操作で直進し続けられるので、初期状態でK部屋以下分移動した時に、どこまでゴールに近づけるかさえわかれば良い。
queueを使って行ける部屋を管理してみました。
バグらせて時間を結構使ったけど通ったのでよし。
D問題は端から貪欲に取っていけばいいということはわかりましたがバグらせました。(終わった後普通に通ったので、ダメ)
208位 パフォーマンス2118 レート2021(+12)
いつ黄色から落ちるかのチキンレース
AtCoder Regular Contest 073
参加しました。
C問題 Sentou
スイッチを押すとそこからT秒間シャワーが流れる。
N人がt_i秒にスイッチを押した時、お湯の出る時間の総和を求める問題。
最初から順番にシミュレートしました。おわり
D問題を見て完全に思考が停止し、E問題でmax,minを見ればいいんだろという投げやりな感じでトライしたところ、ドハマりして無事終了。ダメすぎる。
393位 レート更新はまだだけど、黄色から落ちそう。そりゃそうだ。