読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ABC024 に参加しました

最後はさっぱりでした.C問題まで完答.
145位でした.ちょっとC問題の実装に手間取りすぎましたかね…





ABC 024 A

問題

A: 動物園 - AtCoder Beginner Contest 024 | AtCoder


回答

Submission #412965 - AtCoder Beginner Contest 024 | AtCoder

基本的には子供料金と大人料金をそれぞれ求めて合計.
もし団体割引がきくならそこから引く.それだけですね.
解説スライドでも言われていますが,未満と以下に注意.(未満:<,以下:<=)

A, B, C, V = map(int, input().split())
S, T = map(int, input().split())
print(A * S + B * T - (0 if S + T < V else C * (S + T)))


それとpythonだと

(0 if S + T < V else C * (S + T)))

みたいな書き方が割りとできていい.発想しやすくて楽.他の言語でも出来るものはありそうだけど.

ABC 024 B

問題

B: 自動ドア - AtCoder Beginner Contest 024 | AtCoder


回答

Submission #413306 - AtCoder Beginner Contest 024 | AtCoder

ドアが開いている時間がかぶっていれば,差分を計算して後は積みあげていくだけ.
そこの計算が一番難しいところでしょうか….

N, T = map(int, input().split())
ali = [int(input()) for _ in range(N)]
res = T
before = ali[0]
for i in range(1, N):
    if before + T > ali[i]:
        res += (ali[i] - ali[i-1])
    else:
        res += T
    before = ali[i]
print(res)

部分点解法は長いリストを準備して,ドアが開いている時に1を足して,1以上になっているところを数え上げる形式じゃないですかね.
多分こう,じゃないかな….(と思ったら,TLE連発で通りませんでした.実装方針はこれでよいと思うのですが,Python以外の言語なら同じアルゴリズムで部分点取れると思う)

N, T = map(int, input().split())
ali = [int(input()) for _ in range(N)]
timetable = [0 for _ in range(ali[-1] + T)]
for a in ali:
	for i in range(T):
		timetable[a + i] += 1
print(sum(1 for i in timetable if i > 0))

追記

CでTLEするバージョン描いた.50点です.久々に書くと配列の初期化とかわからなくて辛い.

Submission #416794 - AtCoder Beginner Contest 024 | AtCoder

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
 
void solve(int n, int t) {
	int i, j, temp;
	int res = 0;
	
	bool timetable[2000000];
	memset(timetable, false, 2000000);
 
	for(i = 0; i < n; i++) {
		scanf("%d", &temp);
		for(j = 0; j < t; j++) {
			timetable[temp + j] = true;
		}
	}
	
	for(i = 0; i < 2000000; i++) {
		if(timetable[i]) res++;
	}
	
	printf("%d\n", res);
}
 
 
int main(void) {
	int N, T;
	scanf("%d%d", &N, &T);
 
	solve(N, T);
	return 0;
}
ABC 024 C

問題

C: 民族大移動 - AtCoder Beginner Contest 024 | AtCoder

回答

Submission #415453 - AtCoder Beginner Contest 024 | AtCoder

やや強引に解きました….
移動できるかぎり,貪欲に移動する.そして移動範囲の中にゴールがあれば,ゴールする.
それだけなんですが,うーん,自分のコード見ると無駄が多い気がしますね.

思ったけど,答えようのやつすべてリストに一度入れるんじゃなくて,今考えている民族だけ読み込んで逐次出力したほうがいい気がします.ダメだなこれ^^;

N, D, K = map(int, input().split())
movelist = [list(map(int, input().split())) for _ in range(D)]
goallist = [list(map(int, input().split())) for _ in range(K)]
goalday = [0 for _ in range(K)]
day = 0
for m in movelist:
    li = []
    for i in range(len(goallist)):
        if goallist[i][0] < goallist[i][1] and m[0] <= goallist[i][0] < m[1]:
            if goallist[i][1] <= m[1]:
                goallist[i][0] = goallist[i][1]
                li.append(i)
            else:
                goallist[i][0] = m[1]
        elif goallist[i][0] > goallist[i][1] and m[0] < goallist[i][0] <= m[1]:
            if m[0] <= goallist[i][1]:
                goallist[i][0] = goallist[i][1]
                li.append(i)
            else:
                goallist[i][0] = m[0]
    day += 1
    for i in li:
        goalday[i] = str(day)
    if 0 not in goalday:
        break
 
print("\n".join(goalday))

(そして提出コード,copyインポートしてるけど意味が無いぞ!)


D問題はさっぱりでした.式の計算をひたすらしていて,式を簡単にすれば良いことまでは思いついたのですが,そこから逆元を求める話とかさっぱり,

ちなみにて計算で式を簡単にしようとしていたら,ボロボロ計算ミスしてました.
久しく数学の問題とか解いてないから,こういうことになるんですね.
頭のトレーニングとしてちょっとやっておいたほうが良いかも…ww