いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

Educational Codeforces Round 25(ECR25)

出ました
Educational Codeforces Round 25 - Codeforces

こどふぉは前から出てみたいと思っていたので適当にググって参加方法を参照して登録して参加した
以前SRMにも出たので同じ感じで(結果がしょっぱかったので参加記書くか迷って書かなかった)

A.Binary Protocol
1の個数がその桁の数字を表すので数えて出力したらAC
問題文の理解ができなくて最初普通に二進数を十進数に直すコードを書いてそりゃ合うわけないわなって言ってた
なんでだ

B.Five-In-a-Row
5目ならべ、次の1手で勝てるかどうかを判定する
とても愚直に全探索を実装した
これに時間がかかったしバグ生えたしまだまだだなと思い知らされた
実装力が足りなさすぎる

C.Multi-judge Solving
通せませんでした
問題を誤読しているのかもしれない

nは問題数
kはすでに解いた問題の最高難易度
以降aはそれぞれ問題の難易度
で、解ける問題はそれまでに解いた問題の最高難易度*2以下の問題
解けない問題はいくつありますか?

だと思ってたらテストケース6が通らず
で、解けない問題をカウントして解いたことにして進めたらテストケース7が通らず

#include "bits/stdc++.h"
using namespace std;

int main(){
	long long int n,k;
	cin>>n>>k;
	
	long long int cans=k;
	vector<long long int> a(n);
	int ans=0;
	
	for(long long int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	
	for(long long int i=0;i<n;i++){
		if(cans*2<a[i]){
			ans++;
		}
		cans=max(cans,a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

そんなところでタイムアップだった
次回以降も出ていきたいし英語問題にも慣れていこうと思う
明日はTwitterでいいねしていただいた数だけAOJ自明埋めていきます

ぜひいいねして私を追い込んでください

ACM-ICPC 2017 国内予選 参加記

Yurahuna氏、Yazaten氏と共に参加しました「sparsely_populated_regions」というチーム名で参加しました
飲んできたので覚えてないとかを言い訳に雑に書きます

会場に集まったら各チーム準備をしていた
開始したらまず画面にB,C問題を表示して下の方でテンプレを写す部分を担当する予定だったが、開始直前でプリンターの動作が怪しいとかでA,Bを表示してYazaten氏がテンプレを担当に、私はAを読むことに変更した
時間がない中でうまく回ったのですごいと思った

A問題は読んだら二分探索をしそうだと思ってしまったが、メンバーに説明する段階でそれはないと言われ、説明中に全探索で行けることも気づいたので後は実装するだけだった
二人はもう少しで何とかなりそうって感じだったので実装をした
コードはささっと書けたがcinを忘れるとかやらかしてサンプルをバグらせていた、緊張し過ぎである、開始前には反復横跳び等をしていた人物もいた

軽くYazaten氏がフォローしてくれてAC
どうすればいいか二人を見てみるとYurahuna氏がBを書ける、Yazaten氏がC解けそうだったのでDを印刷して読むことに

D問題は読んだ感じ自分では無理だと思った、無理だと分かった事を褒めよう(?)
誤読をしないように丁寧に読み直してサンプルをすべて図示した
そこで多分bitDP(書けない)を使うんじゃないかと思ったがこれを伝えて固定観念を与えてしまって違った時が痛すぎると思ってノートに書いた文字を消した
制約が妙だったのでしっかりメモしておいた
f:id:ratetion:20170714231559j:plain
そこら辺でYurahuna氏がBをAC、Dを聞きに来てくれた
丁寧に読んでいたので説明がスムーズに出来たようでよかった
再確認とかをしていたらYazaten氏がCをAC、Dを聞きに来てくれたので二人にDを任せてE,Fを読みに行った

Eは構文解析で、論理回路っぽい問題だった
論理回路をしっかり理解してなかったのでやばいと思ったが、説明自体はそれほどでもないので軽く読む程度にしておいた

Fはなんだかひたすら考察をしそうだと思ったので、サンプルを図示した上で、紙を実際に折って確かめ、全分岐を3回分まで図示した
なにか法則っぽいものが見えたが難しい
f:id:ratetion:20170714231618j:plain

二人がDを通してくれた、この時点で100分経過程度だったと思う
割とDを通してるチームが多く、もう1問無いと危険かもしれないという空気が流れていた
Yazaten氏にEを説明、Fの方が解けそうにも見えたので聞いてくれないかと言ったがEが解けそうらしいので信じることにした
二人が分担して実装と考察をしていたのでそれのフォローに入った
こんな方針でやろうと思ってるけど違和感あるかとYurahuna氏が問うてくれたのでそれに関しては平気っぽそうだと思った
テストケースを書いたり確認したりひたすらしていたら、Yazaten氏が実装をかなり進めていてよさそうな雰囲気だったがタイムアップになった

4完じゃ怪しいと思っていたので微妙に悔しいような感覚だった
結果は4完の35位でした
最初の3問を素早く通せたのがよかったっぽい
しかし自分はAでくだらないミスをしてしまったし、WAを吐いていればかなり順位が落ちていたっぽいので反省しかない

それでは2次会へ行ってきます
今日はお疲れさまでした

ICPC模擬国内予選2017参加記

2017/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group

本番に出るチームで参加しました
結果は4完でした
チーム名はsparsely_populated_regions(限界集落)(575)
チームメンバーの開始直前のツイートです



時系列で書いた方が面白いかもしれないのでそのように
内容は忘備録程度なのでいつも通り雑に書きます

二人がライブラリを印刷していたが、自分はまだ全域木とかしか無いしそのような実装は時間がかかりすぎて任せるしかないので、基本的だけど書き方に自信がない物だけ用意しようと思った
印刷場所が遠いので手書きにした


事前に私がA,ゆらふな氏がB,やざてん氏がCと決めていたのでまずA問題を読んだ
みんな読み終わった段階で私だけ理解できてなかったのでもう一回読んだらすぐ解法が浮かんだ

A:問題がn個与えられる、それぞれの難易度が1~mで与えられる
各難易度から1問ずつ出題し、合計でm問出題する
しかし各問題には推薦度が決められておりそれが最大になるようにする
配列でmaxを持っておしまい
だったけど添え字をミスったのでサンプルが通らなかった
二人が声をかけてくれてゆらふな氏が指摘してくれてAC

ゆらふな氏が読んでたBのヘルプに入る
問題文の解釈がややこしくて二人で相談しているうちにやざてん氏がCを通してくれていた
後で問題の概要を聞いたけどどうも混乱しそうだった

やざてん氏の手が空いたのでゆらふな氏にDを頼んでBをやざてん氏に読んでもらった
先に問題の概要を説明しようとしたが、問題を理解してないのに説明しても意味がないと後で思ったしその時本人が止めてくれた
この隙にBのサンプルを図示しようとした
読んでもらったらすぐ実装できそうとのことで実装を頼んで、図示が終わり次第Dを読み始めた

Dもまた問題文がややこしいけどなんとなくわかったなぁと思っていたらゆらふな氏がサンプルの動作を実際に説明してくれたのでわかりやすかった
なんとなく二分探索しそうだなぁと思ってたらゆらふな氏が同じことを言っていた
クリアできないケースについては整理でき説明できたのでよかった
しかし本当に二分探索でいいと言い切れず、二人がDPを使ってはどうかと言い始めたあたりで話について行くのがやっとだったので離れて別の問題を読むことにした

Eを開いたら数学っぽくて今まで解いたことのないジャンルだと感じたので読まずに飛ばした

Fはマトリョーシカ風に立方体を入れ子にしてなるべく一番外の立方体の体積の合計を小さくする問題だった
条件は直感的でわかりやすいし伝えやすい、後は何か具体的なアルゴリズムを知っていれば解ける系なんじゃないかと感じたのでやざてん氏に相談したら解けそうとの事で考察を任せ、サンプルを図示し始めた
二人とも多分Dから離れゆらふな氏はEの考察をしていたと思う
この図示が難しくて妙に時間がかかったがミスするよりはいいと思った

図示の合間にやざてん氏がFで使うらしいライブラリの写経を少し手伝った
キーボードがHHKBかmacbookのJISを用意していたがHHKBの十字キーがわからずmacbookを使って書いていた
緊張してミスタイプが多かったので確認してすごく遅い写経になってしまった

やざてん氏の考察が終わったので写経を代わってもらって終わり次第実装に入ってもらった
私は図示の続きと確認をして納得がいったので後半の問題で優しそうなのがないか探していた
f:id:ratetion:20170702232910j:plain

やざてん氏がバグを吐いていたのでヘルプに入った
バグが起こってそうな部分を雰囲気だけで伝えてみたが、どんな実装なのかあんまりわからなかったので下手なことをいうより考えてもらった方がいいと思ったので端的に伝えて答え合わせとかの準備をしていた
答え合わせが多少スムーズになったので悪くはなかったと思った
時間かけてバグを取ってAC、ここで4完、残り30分弱だったと思う

ゆらふな氏がEが解けるとの事で使うライブラリの写経を投げてきたのでどこを写すか整理してやざてん氏に投げていた
写経速くてやべえと思った、やべえ
写経が終わったらゆらふな氏が実装に入ってくれたので写経部分のミスをひたすら探すお仕事をした
2個ほど見つけられたのでまあやることがあってよかったなぁと思った
実装間に合わずタイムアップ
ABCFの4完でした

自分はほとんどキーボードに触れず考察と図示サポートをしていたので、問題や解法をうまく伝える能力がもっと必要だなと感じた
また添え字ミスとか露骨なミスを減らさないといけないなぁと思った

3日連続でSRM,ARC,模擬国内と出たので充実した3日間だった
おわり

AtCoder Regular Contest 077(ARC077)

AtCoder Regular Contest 077 - AtCoder Regular Contest 077 | AtCoder
出ました、出ました
自宅で4人でオンサイトごっこしながら出ました
結果は1完の終了後にDも通しました

C.pushpush
数字がn個与えられる、これを

1,数字を後ろにくっつける
2,逆向きに並び替える

という操作を繰り返していく
最初は文字列にして処理してやろうかと思ったけど、よく考えたら
1,2,3,4,5,6と与えられた場合
6,4,2,1,3,5
という風になる
出力順を見れば後ろから1個飛ばしで出力したのち前から1個飛ばしで出力している
これをループさせてAC
終わった後で友達がTLEを吐いていたので聞いてみると先頭に追加していたが、その部分ですべての要素を1ずつずらす処理が入るためだった
dequeueを思い出したので勧めたらACしていたのでよかった
思考放棄かとも思うが速いので

D.11
n+1の数列が与えられる、その要素はn以下の数をすべて使っているので1つだけ2回登場する数がある
これらの部分列の個数を1~n+1までそれぞれ求めて出力
しばらく考察をした
同じ数を見つけてそれの左にある数字の個数と右にある数字の個数をそれぞれ数えて組み合わせを全体から引けばいいと思った
組み合わせだと思ったのでとりあえずABCの問題を探した
C: 経路 - AtCoder Beginner Contest 034 | AtCoder
フェルマーの小定理を使わないと1e9+7で割ったあまりをうまく求められないことを覚えていたので(今後当たり前になるらしいのでテンプレ化予定で)
なんとなく理解しそれとなく実装しておいた

で、実装するとかなり惜しい答えが出たが合わない
あちこち見直し頭を抱えてたらタイムアップ
終わったらY氏が華麗に解説してくれた

例えば
1234567489を考える
4が同じ数なので左の4の左に数字が3つ、間が開いて右の4の右に数字が2つ
2数からなる部分列でダブるのは14,24,34,48,49となる
この場合は私の実装でもうまくいく
しかし3数以上を考えるときダブるのは124,134,234,489まではいいが、4の外を両方使ったを使った148,149,248,249,348,349が数えられてない
なので正しくは左から選ぶ通り、右から選ぶ通りではなく、左右の合計から選ぶ通りを引けばよかった

実装したら通らなかったのでTwitterに投げたら、c++では負の値の余りを計算すると正にはならないらしく、負のまま出力されていたらしい
1e9+7を足したうえで余りをとるように変更したらAC
ありがとうございました

学ぶことが多くていい回だったなぁと思いました

AtCoder Regular Contest 076(ARC076)

AtCoder Regular Contest 076 - AtCoder Regular Contest 076 | AtCoder
出てました
そっちかよって感じですが今日のも後で書きます

C.Reconciled?
犬と猿の数が与えられるから、交互に並べる通りを数えてください
犬猿は区別します
犬と猿の数の差が2以上だと並べられない(犬か猿が隣り合ってしまう)のでそれを場合分けで跳ねて、さらに差が0か1かで場合分けをした
それぞれ計算して終わり

D.Built?
これにとても苦戦して5時間かかりました、最近のARCは長いなあ(?)
街の座標がx,yで与えられる、これらの街に道をひいてすべての街を行き来できるようにしたい
この時道のコストがa,bとc,dの街の間でmin(|a−c|,|b−d|) 円かかる
最低で何円必要か

最初に問題を見て最小全域木だと思った
最近Y氏が教えてくれた奴だ、やったぜ
しかし制約を見て無理だと分かった
しかし色々考えた結果最小全域木が蟻本に載ってるってことはそれ以上のアルゴリズムはないってことだ(?????)
まあほかにいい方法が思いつかなかったので図をいっぱい書いて考察を練ってた
x,yそれぞれソートしてみたら引くべき道が絞れてきて、(n-1)*2本でいいことが分かった
これに対して最小全域木を作れば行けると確信し始めて実装を書き始めたらタイムアップになった
TLを眺めてるとどうも正解っぽくて悔しいやらうれしいやら

という事で実装していたら5時間かかってしまった
Submission #1379815 - AtCoder Regular Contest 076 | AtCoder
忘備録だから書いたつもりだけどうまく書けないし多分忘れることもない問題になってしまった

ABC056 C.Go Home

C: Go Home - AtCoder Beginner Contest 056 | AtCoder
解きました
一回諦めて時間空いてたシリーズ
カンガルーがi時間経過時にiの距離ぴったりジャンプできる
入力された値の位置に行けるまでにかかる時間の最小を求める
最初見た時どうしていいかわからなかった
最近考え直していて気付いたのだが、1-nまでの数字を選んで足し合わせると、総和までのすべての数が作れる
で、当然1から足していってnを超えたらnまでの数は全て作成可能である
計算量は10^9で10^5ループ程度だったので普通にAC
細かいことを言えば10^9は44721ループだったのだが何か求め方とかあるんですかねぇ
Submission #1333576 - AtCoder Beginner Contest 056 | AtCoder

AtCoder Regular Contest075(ARC075)

AtCoder Regular Contest 075 - AtCoder Regular Contest 075 | AtCoder
出ました、毎回悔しかったですとか言うてる気がするけど悔しかったです

C.Bugged
n個の整数が入力されるので合計点を求めたいんだけど、合計が10の倍数だと0になっちゃうからうまく選んで最大値を求めてねって感じ
ちょっと迷ったけど冷静に考えたらすぐわかった
合計を求めて合計が10の倍数でなければそのまま出力して終わり
合計が10の倍数の場合はソートをして、小さい物から10の倍数かどうか見ていく
10の倍数でなければ合計からそれを引いたものを出力して終わり
やや遅くなったが何とかAC

D.Widespread
魔物がn体いてそれぞれHPがある
魔法が使える
1体選んでAダメージ、ほかのすべてにBダメージ与える
全部倒すまでの魔法の最小使用回数を答える
愚直にソートして一番大きいものにAダメージを繰り返しシミュレーションしようとした
毎回ソートするのがかなりあほらしいなあと思う
工夫しようと思って全体から引くよりBダメージを毎回保持して最大HPから保持した値を引けば抜けるか決めれるようにした
案の定テストケースが終わる気配がなかった

次にpriority_queueを使えば自動でソートしてくれるじゃんって思って実装した
ここで制約を読み直してどうあがいてもシミュレーションやってると10^9ループが逃れられないのでダメだと気付いた
むろん実装後の話

一旦E問題を覗きに行くことにした
しばらく部屋を闊歩したのち二分探索じゃないかと思ってしばらく考え込んだ後実装を始めた
実装できたと思ったがあちこちでWAが出る
細かいところでミスしてるんだろうなぁと思いつつ、気になったところを修正して試していたらタイムアップ

その後10分もしないうちに大なりイコールに変更、少数を考慮していない部分を修正、long long intに変更してACしてしまった
時間あれば解けたなぁと思うけど、以前の私なら解けなかったので成長はしてると実感できた
Submission #1328812 - AtCoder Regular Contest 075 | AtCoder


E.Meaningful Mean
途中でチラ見して制約がやばそうで逃げた
具体的には整数がn個与えられるのでそれらの組み合わせの平均がk以上となるものがいくつあるか調べる
メモ化再帰とか使ってDFSでも書けばいいやと思ってたけどそんなまさかこの制約で出来るわけがねえって思って逃げた
いい判断だった
解説も聞いてないのでまたリベンジしたい


レート
f:id:ratetion:20170603235634p:plain