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

水面下の夢

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

ARC048に参加しました

AtCoderARC C++ Python 競技プログラミング

時間内2問完133位。

B問題、TLE解から改善するのに時間食い過ぎました。やっぱり慣れてない言語(C++)はアルゴリズムがわかっていても、プログラムとして書き下すのが(言語依存の動きや文法のために)難しいですね。




ARC 048 A

A: 階段の下 - AtCoder Regular Contest 048 | AtCoder

階段を何回上がるかということですが、予備知識としてどこかの数学パズルか何かを読んだ時に「0階」が存在しないことを知っていたので、らくらくAC。クロス集計表を使うとこうなる。

地上 地下
地上 abs(x-y) abs(x-y) - 1
地下 abs(x-y) - 1 abs(x-y)

これをプログラムに反映して終わり。以下はPython3での解答例。

Submission #652377 - AtCoder Regular Contest 048 | AtCoder

s, t = map(int, input().split())
if (s > 0 and t > 0) or (s < 0 and t < 0):
    print(abs(s-t))
else:
    print(abs(s-t)-1)

ARC 048 B

B: AtCoderでじゃんけんを - AtCoder Regular Contest 048 | AtCoder

じゃんけんのシュミレーション。ただし、レーティングの大小でまず勝敗が決まり、そのあと正規のじゃんけんの結果が反映されるという条件付き。

方針としては、まず着目しているレーティングより、レーティングが低いものを全て勝ちとして集計、高いものをすべて負けとして集計したうえで、同じレーティングのものに対してじゃんけんシュミレーションする、という流れでできそうです。

実装としては、mapを使い、レーティングから参加者IDとジャンケンの手のPairを引き出せるようにしたうえで、昇順ソート。これにより、レーティングの上下について考えやすくなります。そして、レーティングが等しいものについては愚直にシュミレーションして計算しました。

この問題のポイントは全部シュミレーションせず、まずレーティングで大雑把に勝敗を決めてしまうことでしょうねー…

なお本番では、Pairを使わず参加者IDもvectorの配列に突っ込むということをしていたので、奇妙なコードになっていました。(map<int, vector< pair<int, int> > > で良い)

以下のコードはC++で、コンテスト後Pairを使って実装した例です。(こっちのほうが見やすい)ちょっとコード量が長くなってしまっているので、もう少し上手く書きたいですね^^;

Submission #655078 - AtCoder Regular Contest 048 | AtCoder

int data[100000][2];
map<int, vector< pair<int, int> > > rate;
int result[100000][3];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.precision(16);

	int n;
	cin >> n;

	REP(i, n) {
		int r, h;
		cin >> r >> h;
		data[i][0] = r;
		data[i][1] = h;

		rate[r].pb(mp(i, h));
	}

	int accu = 0;
	for(auto elem : rate) {
		int size = elem.second.size();

		if(size == 1) {
			int f = elem.second[0].first;
			result[f][0] = accu;
			result[f][1] = n - accu - 1;
		} else {
			for(int i = 1; i < 4; i++) {
				int tres[3] = {accu, (n - accu - size), -1};
				REP(j, size) tres[abs((i - elem.second[j].second + 3) % 3 - 2)]++;

				REP(j, size) {
					int f = elem.second[j].first;
					int s = elem.second[j].second;
					if(s == i) {
						result[f][0] = tres[0];
						result[f][1] = tres[1];
						result[f][2] = tres[2];
					}
				}
			}
		}
		accu += size;
	}

	// cout << "**RESULT**" << endl;
	REP(i, n) cout << result[i][0] << " " << result[i][1] << " " << result[i][2] << endl;
}

ARC 048 C

C: 足の多い高橋君 - AtCoder Regular Contest 048 | AtCoder

コンテスト終了後に解説スライドを読んで、ある程度納得したうえでときました。gcdに帰着するなんて思いもよりませんでした。最小となる値を求めて、各要素ごとに最小値を引いたリストを作り、そのgcdを求めて、2のべき乗を求めて、MODを取る… みたいな感じですね。


解説スライドへのリンクはこちらから。
http://www.slideshare.net/chokudai/arc048


なぜこの計算で合うのかは、私の説明よりも解説スライドを参照してみてください…。解説スライド通りに実装しているだけなので、特に語ることはないです…。(本番は長い方ばかり考えていて、短い方に目を向けることが出来なかった)


ただ、リストの要素の対してgcdを取ったら、なんかTLEするので、改良しまくって、結局分割統治する(マージソートをイメージして><)ようなコードが出来上がりました。実はリストの要素に対してgcdをとるプログラムは事前にライブラリとして書いていたのですが、これまでのものは線形的に前からやっているので、計算回数が若干無駄になっているという問題がありました。そこでそのコードを改良したらAC… ってこれ自分のライブラリもどきが悪いですね^^;


というわけで、ライブラリもどきも改善されて(?)問題もACされてホクホクでした。


以下はPython3のコードです。

Submission #654769 - AtCoder Regular Contest 048 | AtCoder

MOD = 10 ** 9 + 7
 
def gcd(a, b):
    if a < b:
        a,b = b,a
    while b > 0:
        r = a % b
        a,b = b,r
    return a
 
def arrgcd(a):
    alen = len(a)
    if alen == 3:
        return gcd(a[0], gcd(a[1], a[2]))
    elif alen == 2:
        return gcd(a[0], a[1])
    elif alen == 1:
        return a[0] # 最初から1つ
    elif alen == 0:
        return 0
    else:
        return gcd(arrgcd(a[:alen//2]), arrgcd(a[alen//2:]))
 
def solve():
    legnum = int(input())
    legs = [int(input()) for _ in range(legnum)]
    minleg = min(legs)
    gcdval = arrgcd([x - minleg for x in legs if x - minleg > 0])
    print(pow(2, minleg + (gcdval + 1) // 2, MOD))
 
if __name__=="__main__":
    solve()


それと、Pythonのライブラリとして提供されているgcdとreduceを組み合わせる解法もあるようです。というのをほかの人のコードを読んで気がついたので、書いてみました。

Submission #654775 - AtCoder Regular Contest 048 | AtCoder

from fractions import gcd
from functools import reduce
 
MOD = 10 ** 9 + 7
 
def solve():
    legnum = int(input())
    legs = [int(input()) for _ in range(legnum)]
    minleg = min(legs)
    gcdval = reduce(gcd, [x - minleg for x in legs])
    print(pow(2, minleg + (gcdval + 1) // 2, MOD))
 
if __name__=="__main__":
    solve()

C問題は実装自体は結構単純なところに落とせるので、考察がいかに大切なのかを教えられる問題でした…。(考察力がない)


以上でARC048の記事終わり…。

まだ集計上では、今年入って29 / 300らしい。。。ペースをあげたい。