TeXでAPA形式を使う

しばらく．
最近全くSRMに参加できていないのですが，そういやこのブログはSRMのためだけに作ったわけではないのでした．

SRMに参加できない理由の一つである課題で（勝手に）TeXに手をつけているのですが，APA形式で文献を記載しなさいと言われてだいぶ困ってしまったので，忘れないように書いておくことにします．

だいぶ調べまわった結果，

\usepackage{apacite}

を最初の方に書いて，

\bibliographystyle{apacite}
\bibliography{（.bibの場所）}

を最後の方に書けばいいだけでした．だいぶ時間を無駄にした．つらい．

SRM699Div1感想

久しぶりにSRMに参加できました．今回はDiv1ということで辛いだろうな，と思っていましたが案の定まっっったく解けませんでした！

Easyだけ見ましたが，僕にとっては全然easyじゃない．しばらくはDiv2で修行を積んだ方がいいと思います．

さてそのeasy問題ですが，ざっくり解釈したところはこんな感じでした．

未知の数列 \{ w_n\}_{n=0, 1, \cdots, N-1}があり，数列 \{x_n\}_{n=0,1, \cdots, N - 1}が与えられる． x_n=-1でないとき， x_nの値は数列 \{w_n\}の第 n項以外の排他的論理和を表す．このとき， \sum_{n = 0}^{N} w_n の考えうる最小値を求めよ．

思いついたことといえば x_0 = w_1 \oplus w_2 \oplus \cdots \oplus w_{N-1} \\ x_1 = w_0 \oplus w_2 \oplus \cdots \oplus w_{N-1}を辺々足したら
x_0 \oplus x_1 = w_0 \oplus w_1だから，順々に使っていけばとりあえず全探索はできるな，ということくらいでした．時間がなくて実装は間に合いませんでしたし，これでは計算量が多すぎないかとも思います．さらにこの漸化式チックなもので作った \{w_n\}が本当に \{x_n\}と矛盾しないかの確認も必要になるってことにも終了直前で気づきました．つらい．

今回はエディトリアルがすぐに公開されたので，明日みようと思います（今日はもう寝ます）．

SRM691Div2反省

反省や解法のメモを書いていきます．


300:

0~9の数字の書いてあるカードと+の書いてあるカードがそれぞれ何枚かと1個のカウンターがある．ある順番でこのカードを取っていき，以下の操作を行う．

    

  • 数字のカードなら，その数字とカウンターの数字の差の絶対値の分だけペナルティを加算する
    • 

  • +のカードなら，カウンターの数字を1進める
    • 

カードの構成が与えられたときペナルティを最小にするための順番を返せ．

直感的に解ける問題でした．他の人のコードをちらっと見た限りでも，みんなだいたい同じ解き方で，

数字のカードを小さい順に並べ，+の数を増やしながら，+が足りなくなるまでペナルティが0になるように数字を配置していく

という感じのものでした．僕の解法も同じでしたが，charとintの変換に苦労するなど初心者感満載な時間のかけ方をしてしまいました……

500:

0~n-1のn個の頂点とi,a[i]間の辺をもつグラフが与えられる．新たに頂点nを追加し，頂点の部分集合Mに対して，Mに属するすべての頂点iについて，辺i,a[i]を削除して，辺i,nを追加する．この操作のあと，すべての頂点が繋がっているような部分集合Mの数を返せ．

僕は解法が思いつかず．Div1だと「0から1のパスが存在するようにする」問題だったようですが，Div2では「すべての頂点が繋がっている」ようにする問題でした．Div1のほうが簡単にみえる……僕に理解できた解答は，ループから一つ頂点を選んでも連結のままだが，ループ以外から頂点を選ぶとその頂点が切断されるということに着眼して，

    

  1. 各ループから少なくとも一つずつ頂点を選ぶ
    2. 

  2. ループに含まれない頂点は選んでも選ばなくても良い 
    3. 

という条件を満たすような選び方の総数を求める

というものでした．いやぁ難しい．精進します．

900:

整数 nを割り切らない正の整数のうち二番目に小さいものを S(n)とおくとき， \sum_{i=1}^{n}S(i)を返せ．

いたってシンプルな見た目の問題で，解を出すだけならどちゃくそ簡単ですが，nが1,000,000,000まで大きくとれるので，時間を短くする工夫が必要でした．他の人のコードを見ると，どうやら「n=1,000,000 * iの答えを配列でとっておき，n=1,000,000 * i + rのときはrの分だけ計算する」ことで計算量をO(r)くらいに減らした解答が多かったです．なるほどローカルなら時間制限なしで走らせられるのでそういう解き方もできるんですね．勉強になります．真似しようとは思いませんが．うまいと思ったのは，それぞれのnに対してS(n)を計算するのではなく，逆に

 S(n)に対してS(n)=kとなるようなnの個数N(k)を求め，k \cdot N(k)の総和を求める

というものでした．いわゆる逆転の発想，大事ですね．

結局まともに解けたのは1問だけでしたが，Div1に配属されました．かなり厳しいと自覚はありますが頑張ろうと思います．

SRM691Div2感想

初めてSRMに参加しました．出来は良くはないですが，同じルームの中ではちょうど半分くらいの位置でした．1問しか解けていないのにDiv1スタートとは先の道が厳しいなぁ．

 

SRM691Div2は300-500-900の問題構成でした．
300と900は提出し，900は撃墜されました（知ってた）．
300は簡単でしたね．+と0~9の数字を並べる問題でしたが，直感的な方法でもシステムテストに通りました．
500, 900は（個人的には）難しかった……
500は全探索だとO(2^n)で完全にタイムオーバーだし，900も制限がn<=1,000,000,000とかいうバカでかい数なので工夫が必要でした．なにも思いつかなかったし時間もなかったので素直に実装しました（撃墜されたけど）．
他の人のコード見て勉強します．わかったらまた書きます．

同じルームに一人初参加で1200点くらい取ってる人がいました．すごいね．全問システムテスト通して僕の900撃墜してるからね．

精進します．