Codeforces Round #450 (Div. 2) D問題
和がNで数列の全要素のGCDが1となる数列の数を求めたい。
a(n) = sum_{d|n} mu(n/d)*2^(d-1)
この式で表せるらしいが全然意味が分からなかったのでメモしておく。
d | n……dはnの約数という意味。
sum_{ }……{ }内のすべての要素について何か処理をする。
mu()……メビウス関数。
つまり、nの約数であるすべてのdについて、mu(n/d)*2^(d-1)の総和を求めたいらしい。
また、包徐原理を使うことで、2^(n-1)からd>1となるa(d)を引いても求められるらしい。
和がn/dだったときに(a,b,c)だったのがd倍すると(ad,bd,cd)となるからかなあ。
北大＆日立MMその1
1日目
King's Graphはどうでもいいので、2S*2S四方のフィールドに元のグラフの頂点を乗せていくことにする。
(King's Graphへの変換後に辺が伸びているかはチェビシェフ距離が1か否かで判定できる)
とりあえず愚直貪欲を書いてみようと思って、頂点0をフィールドの中央に置いた後、一番スコアの伸びるものを貪欲に配置していくことにした。
ここまでで153329点
時間の許す限り開始点を変えつつ、より重い辺がたくさん伸びている頂点から回すと155626点
ランダム2点swapを実装し、156150点
2点swapを全探索に変更しつつ高速化をして156658点
軽いケースで初期解の探索に時間をかけるようにすると156716点
この時点では3位狙えるんじゃね！？みたいに思っていた。
二日目
全探索3点swapをバグらせつつも書ききり157037点
全探索4点swapを実装すると同時に、2点swap～4点swapを関数化、ここで3,4点swapをバグらせる。が、スコア更新し157048点
全探索5点swapも実装したが効果がなさそうなので没に
三日目
方針が降ってこなくてお掃除をしていた。
1点moveを実装していないことに気づき1点ムーブを実装し157334点
moveとかswapの順番をいろいろいじってたら157483点
四日目
前日に引き続きいじっていたら157553点
そろそろ頭打ちだなあと思い始めたので、初期解の改善に取り組む。
配置していくにあたって共通の隣接ノードを持つ頂点同士を隣り合わせるように変更を加えると157599点
ずっとこれをいじる。
五日目
前日に引き続きいじっていたが芳しくない結果だったのでやる気を失いかける。
こどげに逃げようかな～とか考えていると、今の方針が特に意味のないものであることをゆる～く説明できるようになったので今の方針を捨てることを決意。
コードをグッと睨むと定数倍重くするだけ(約20倍)で初期解の探索時に深さ2の全探索を行えることに気づく。
六日目
ようやく深さ2の全探索の実装を終え、158413点。
すると4点swapがお役御免になったので4点swapに別れを告げる。
3点swapまでは最悪ケースでも約3000msで行えるので初期解の探索にもう少し時間をかけるようにすると158562点。
ケースハック(？)を試み始める(ア)
七日目
ひたすらケースのNの特定作業を行う。
あと、一番最初に配置するノードはどれがいいのか調べると、やはりより重い辺がたくさん伸びてる辺を最初に置くのがいい可能性が高いことが判明する。
N=3とN=7で全探索しようかな～とか考えていたけどすでに最適解が出ていた。
八日目
全ケースのNを特定するもシステスらしくて悲しいね
長さ3の全探索を実装しようとしていたけど場合分けが半端なくてあきらめた。
九日目
初日に捨てたビームサーチが案外うまくいくのでは！？みたいに思ったので実装を始める。
全然ダメだったので方針を捨てる。と同時に案が尽きたので終了
十日目
なんやかんやでMM復活
長さ3全探索の実装を再開。
十一日目
前日の続き
十二日目
前日の続き
方針を変えないまま実装の方針を変えることにする。
十三日目
実装成功するも何故かスコア落ちる。
さらに実装方針を変更する。
REが出て80位まで落ちた…悲しい…
よく考えたら焼き鈍しの問題なのに方針捨てたのはまずかったので次回以降気を付けような👊
DDCC2017参加記
前泊ダメだよとのことだったので朝5時ぐらいにお家を出て新幹線で東京に向かうことに。ほぼ始発だったのでめちゃくちゃ混んでて怖いね。
品川でりかちゃんとうしさんと合流して大森海岸へ、
4号車マンやが
— olphe (@_olphe) 2017年11月2日
僕も4号車です
— TAB@DDCC (@_____TAB_____) 2017年11月2日
途中偶然TABさんと遭遇したりしていた。
どうでもいいんですが、たぶさんとたぷさんって似てるね。
朝食後会場に向かい、Tシャツが強制着用だったので着替えたら結構寒かった。
しばらく時間があったのでサイン帖を埋めていた。みんなありがとう。
コンテストはAB解いた時点で7位ぐらいで、Cが800なんで50には入ったかな～と思いつつCの考察へ、なんか何も見えなかったのでMMの気持ちになったら終了2分前に解けたので喜んでいた。結果は30位でした。(3位の人も同じく1600点だったのでもうちょっと頑張っていれば…とか思ったり)
非常に集中していたのか終了直後に軽めの脳貧血を起こしてア。
昼食はTIkeさんとらてあさんと食べながらうろついていたら大所帯になっていて全員は把握できていないんですが、eiyaさんとかAzさんとかつたじろうさんとかりかちゃんとかyazatenさんとかがいた気がする。
その後いろんな人とCの解法についてしゃべってたけど何もわからなかった。復習しましょう。
対談は面白いな～と思いながら聞いていました。
僕が学生の間にtouristを負かすAIとか出てくると思うんだけどどうなんだろう。
まあアルゴリズムとかきれいだな～みたいな感じなので続けるんだろうなあとぼんやりと思っていたりもした。
そういえば社内ツアーで案内係(？)の人が水があって見辛いみたいなことを言ったときに何人かで笑いだしたの面白かった#DDCC2017
— olphe (@_olphe) 2017年11月3日
社内見学のハイライトです。
日本企業に対する偏見が強かったので正直あまり真剣に見るつもりはなかったのですが、福利厚生がしっかりしているなあと思ってちょっと安心した。ほかの企業も充実してるといいな。
夕食時は主にアルゴンさんとみなみさんとICPC頑張りたいなあみたいな話をしていた。ICPC頑張りたいなあ。
終了後ボーリングしてたんですが、あれ難しすぎませんか。
らてあさんと一緒に京都まで帰ってきてDDCCは終了でした。
すごく楽しかったのでオンサイトたくさん出たいね。次はRUPCに出られたらいいなあ。
Marathon Match 95
画像が与えられるので、指定された数の半透明な円を描いていって元の画像に近づけようという問題。
作成途中の画像の状態だけが重要で配置の順番はどうでもいいと思ったのでビームサーチ案を捨て、貪欲に円を配置していくことを考えた。
貪欲パートは、ランダムな位置にランダムな大きさ(大きさは進度に依存する)の円を描くことを考えたときに、変更前、後の各RGB成分の平均を取り、そこから求めた色を塗ることとした。
外側重視とか画像の隣接するマスの近似度とかを使おうと思っていろいろやっていたけどそちらはうまくいかなかった。(最終的に円は小さいので外側重視に意味があまりない？)(思いついたのが最終日の2時ごろなので時間がなかった)
0)1.2455719E7
1)1.6093684E7
2)2.5773614E7
3)1.1478683E7
4)7802575.0
5)1.1083905E7
6)4.0074287E7
7)2.4999824E7
8)1.981949E7
9)3.5520464E7
Codeforces Round #435 (Div. 2)
ABDの3完で239位
A問題
数字の数と作りたいMEX,N個の数が与えられる。数字を出現させたり消したりしてMEXを指定の数にしたい。
配列を用意して舐めてあげればよいです。
http://codeforces.com/contest/862/submission/30502250
B問題
木が与えられる。二部グラフのまま辺を追加したいとき、何本足せるかな？
距離を求めて各頂点がどっちの領域にあるか求めてから引き算すればよい。
http://codeforces.com/contest/862/submission/30514174
D問題
0と1からなる文字列が与えられる。文字列を出力するとハミング距離が分かるので、0の場所と1の場所を一個でいいのであてよう。
まず000..と1000..を出力し、先頭の文字を確定させる。その後、もう一個の文字を探してにぶたんする。
Codeforces Round #434 (Div. 1, based on Technocup 2018 Elimination Round 1)
3完99位
Unratedめ…
A問題
文字列が与えられる。その中に2種類以上の子音が3個並んでいたら切る問題。
切る回数を最小にしたい。
前から貪欲に調べていって条件を満たし次第切ればよい。
貪欲なのでO(N)
http://codeforces.com/contest/860/submission/30422539
B問題
電話番号がたくさん与えられる。それらを連続部分列で識別する場合、各電話番号について一位に定まり且つ最も短い連続部分列を求める問題。
まず全ての連続部分列を求めておく。その後各電話番号について連続部分列を求め、あらかじめ求めたものと見比べればよい。mapで殴る。
O(N(logN)^2)だと思うけど定数倍がでかい。
http://codeforces.com/contest/860/submission/30428030
C問題
たくさんの文字列とその文字列が全体の中で前に来るか後に来るかの情報が与えられる。最終的に文字列を1~Nまでの数字に置き換えつつ並び順も正しくしたい。
まず、数字としては正しいが位置が間違っているものを探し出し、それらを優先的に移動させる。その後、関係のないものを移動させる。
ただし、移動させられない場合は間違った場所にあるものを一度変な名前に変えてやるとよい。セグ木で殴る。O(NlogN)
Ratedだったら+81だったらしいのでつらい…
Codeforces(MemSQL Start[c]UP 3.0 - Round 1)
5完122位でした！すごい！Round2も頑張るぞ！
A問題
本選に25人参加できるコンテストがあり、それらの参加者のうち何人かの予選での順位が与えられる。本選参加を辞退した人は最小で何人かな？
http://codeforces.com/contest/859/submission/30389464
B問題
ブロックがN個与えられるので、それらを並べてできる多角形の周の長さを短くしたい！
基本的には正方形を目指して並べる。欠けていても周の長さは変わらないが、一辺が1短い長方形を作れる場合があることに注意
http://codeforces.com/contest/859/submission/30389970
C問題
パイを順番に配っていく。お互いが最善を尽くしたときに得られるパイの大きさの総計を求める。まず先攻が配る権利を持っている。パイを自分に配ったとき、相手に配る権利が移る。
DP[次に何枚目のパイを配るか][また、配る権利を持っているのはどちらか]
でメモ化再帰を行った。
http://codeforces.com/contest/859/submission/30394617
D問題
トーナメントを行う。各参加者同士では勝率が定められている。i回戦で相手に勝った時、その勝利が発生する確率*2^(i-1)の点を得られる。また、相手が貯めこんでいる点も得られる。どのように進行したら優勝者の持つ点が最大になるかな？
まず各参加者についてi回勝ち残る確率を計算しておき、
DP[i回目に][jが勝ったときの]得点の最大値
を回す。
http://codeforces.com/contest/859/submission/30397238
E問題
席替えをする。各人について今の席と希望する席が与えられる。また、各人は席替え中に席を移動しない、若しくは希望した席に移動する。の二種類しか行動をとりえない。
まず、今の席から希望する席に向かって辺を伸ばし、有向グラフだと考える。
各連結成分についてループが存在しない場合、移動の仕方は連結成分の頂点数通り存在する。ループがある連結成分については、2通り存在する。
それらを掛け合わせてやればよい。
http://codeforces.com/contest/859/problem/E
レート変動は1910->2038でhighestを更新した。やったぜ。
