時間内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
以下のコードは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らしい。。。ペースをあげたい。
