[Excel VBA]Xmas Contest 2019のA-Signboard 1
クリスマスコンらしくプログラミングできなくても努力で何とかなる系の問題。
Private Sub Worksheet_Change(ByVal Target As Range) If Application.Intersect(Target, Range("A1:H8")) Is Nothing Then Exit Sub Else Dim c As Range For Each c In Target If c.Value < 1 Or c.Value > 64 Then MsgBox ("ダメ") Exit Sub End If Dim PicPath As String, Pic As Picture, ImageCell As Range PicPath = "D:\pg\AtCoder\signboard_t1\pieces\p_" & c.Value & ".png" Set ImageCell = c.Offset(0, 9) Set Pic = ActiveSheet.Pictures.Insert(PicPath) With Pic .ShapeRange.LockAspectRatio = msoFalse .Left = ImageCell.Left .Top = ImageCell.Top .Width = ImageCell.Width .Height = ImageCell.Height End With Next c Exit Sub End If End Sub
セルのRange(A1:H8)に[1,64]を入れるとRange(J1:Q8)のセルの位置に画像が追加される仕組み。
どう考えても絶対確実に今後使わないプログラムなので保存はしないけど、なんか勿体ないのでここで供養代わりに上げておく（そのためにこれを書いている。
エクスプローラで縮小画像見ながらパズルしたけど、パワポでやるべきだったなあと思う。
Excelおじさんになりつつある。
[Java]ABC134の[B,E]の反省
ABCがABCDEFになってからかなり易化したのに緑パフォ出しちゃったのでこれはマズい。
B - Golden Apple
想定解だと(N+2D)/(2D+1)を出力してO(1)。
自分は左から一人ひとり監視員を置いていくシミュレーションを行ったO(N)。
シミュレーションを行った理由は数式で提出するとコーナーケースが漏れそうな気がするからだけど、変に気合入った設問でN<=10^10とかだったとすると多分躓く。早急に改善したいところ。
C - Exception Handling
最大値AmaxとなるAが二つ以上あると、どのAを取り除いたとしても最大値はAmax。
最大値が一つの時その最大値を取り除いた時の最大値は数列A1,A2,...の中で二番目に大きい数。
よってAの中で一番目に大きいものとそのインデックス、二番目に大きいもの、の3つを一回の精査で見つけておけばいい。
自分がリアルタイムでやった時は2番目に大きいものを見つけるためにソートしてて無駄が多い。ここも精進ポイント。
D - Preparing Boxes
i番目の箱にボールの数をBiとして考える。
よく考えると箱の後半部分の(∀i>n/2)でAi=Biであることが分かる。
次に箱の前半部分を考えると、i<=n/2のAi=Sum(Bj,j=i,2i,3i...)(mod 2)=>Bj=Ai+Sum(Bj,j=2i,3i...)(mod 2)なので、Biを降順を降順に求めることで全部求めることができる。
コンテスト後にTwitter見てるとこの計算量で躊躇してる人が多かったっぽい。
N+N/2+N/3+...ってのは何か大学受験した時の数学思い出して懐かしかった。（小並感）
E - Sequence Decomposing
解けなかった。これ千人通すのくっそ怖い。
とりあえず対偶取ったとこまでは良かったと思う。
最初にぱっと思いついたのが転倒数。
次に考えたのがLISのDPを変形してAの数列を増加部分列にうまく分割する方法で、それをずっと考えてた。
対偶取ったとこから素直にAi>=Ajを考えてれば減少部分列を思いついたかもしれない。猛省だ。
[Java]Arrays.fillの罠
Arrays.fillの中身って
public static void fill(Object[] a,Object val){ for(int i=0,len=a.length;i<len;i++){ a[i]=val; } }
https://github.com/openjdk/panama/blob/master/src/java.base/share/classes/java/util/Arrays.javagithub.com
なんですね...
参照が渡されるから実際のオブジェクトは1個。
まあそらそうよな感じですけどいつかバグらせそう...というかバグらせたからここに覚書として書くわけだけど。
Supplier貰ってfillしてくれる関数も欲しい
M-SOLUTIONS(2019)-D
解法
そもそもこの問題でまず自分が詰まったのが「木構造のデータの持ち方（データ構造）」について。
リアタイではNodeやEdgeといったクラスを作ったりMapやSetを使ったりして試行錯誤しながら2時間椅子を温めてましたが、普通に隣接リストでいいんですね...(隣接行列は空間計算量の制約的にダメってぱっと思い浮かぶのにこっちは思い浮かばない)
他人のコード見てると
List<Integer>[] g=new List[n]; //Set<Integer>[] g=new Set[n];じゃない理由はあるんだろうか...
の形式が一番多いっぽい
次点で
int[][] g=method(n,from[],to[]);//とか(2番手) Map<Integer,Set<Integer>> tree;//とか Map<Integer,List<Integer>> tree;//とか List<List<Integer>> g;//とか
あと次数を
int[] deg;
で持っとくのもいいテクニックだなって思った（小学生並みの感想）（リアタイではNodeが隣接してるノードの番号を示すSetを持ってて.size()で次数を取ってて詰んだ）。
あとwhileなんかで配列やリストにアクセスするとき
int idx=0; while(hoge()){ ~~~c[idx++]~~~ }
と自然にやれると良いな。
本質的な解法は単純に木の葉っぱの方からスコアが小さい順に埋めていくだけ。
やり方は思いついてただけに悔しいかんじ。
敗因は上記の「木のデータ構造」とDequeの扱い。
追伸
今JavaGold取ろうとしててその勉強しているけど、言語の詳細を覚えるにつれて競プロっぽい書き方が抜けて行ってる気がする。
ライブラリとか覚えるとどうにかしてそれ使おうとしちゃうんだろうな。
Google Code Jam Qualification Round 2019のやつ
2019年4月6日8:00からのGoogle Code Jam Qualification Round に参加したのでそれの解法とか記録。
参加した人はお疲れ様です。
A Foregone Solution
問題
いくつかの桁に'4'が含まれる正の整数Nが与えられるので桁に'4'を含まない正の整数であるA,Bを使ってA+Bで表せ。
考え
largeの時が1<N<10^100なのでNを文字列で読み取る必要がある。
A,Bも似たような長さで出力する必要があるのでStringBuilderで用意する。
Nを一文字目から見ていき'4'が含まれるなら3と1に分解してA,Bにappend。含まれないならその数と'0'をappend。
最後にA,Bの前方に含まれている'0'列をトリムして出力。
フラグとして「すでに4を見た」というものを持っておくと最後のトリムは必要なくなる。
public static void main(String[] args) { Scanner sc=new Scanner(); int n=sc.nextInt(); StringBuilder ans=new StringBuilder(); for (int i = 0; i < n; i++) { String s=sc.next(); StringBuilder sb1 = new StringBuilder(); StringBuilder sb2 = new StringBuilder(); for (char c : s.toCharArray()) { if(c!='4'){ sb1.append(0); sb2.append(c); }else{ sb1.append(1); sb2.append(3); } } while(sb1.charAt(0)=='0'){ sb1.deleteCharAt(0); } ans.append(format("Case #%d: %s %s\n",i+1,sb1,sb2)); } put(ans); }
提出するためのクラス名が分からず3CE。
B You Can Go Your Own Way
問題
N*Nの方眼用紙があって左上のマスから右か下に一マスずつ進んでいき右下のマスに到着する手順が与えられる。自分も同様に左上のマスから右下のマスへ行きたいが、同じルートは通りたくない（同じマスは通ってよい）。同じルートを通らないような手順を出力せよ。
考え
線対称に動けば被らないように動くことができるので、EとSを反転するだけでいい。
public static void main(String[] args) {
Scanner sc=new Scanner();
int count=sc.nextInt();
StringBuilder ans=new StringBuilder();
for (int i = 0; i < count; i++) {
int n=sc.nextInt();
String line=sc.next();
ans.append(format("Case #%d: ",i+1));
for (char c : line.toCharArray()) {
if(c=='S'){
ans.append('E');
}else{
ans.append('S');
}
}
ans.append("\n");
}
put(ans);
}
C Cryptopangrams
D Dat Bae
問題
Nビット送るとB個の桁が消されてN-Bビット返ってくる。F(smallなら10、largeなら5)回そのクエリを出すことができるので消される桁を推定して出力。
考え
完全に証明なし理解なしでlargeまで通せた（自慢?）。
出すクエリを01010101.....,00110011.....,0000111100....みたいにすることは典型で何も考えずそうした。
動的計画法で返ってきたビットの何桁目が最小の場合元のビットの何桁目を表しているか、最大の場合元のビットの何桁目を表しているかを求めることはできるっぽい。。。すべてのN-B個の桁において最小=最大になると答えが分かるがこれだと上手くいかない場合がある（1 2 3の時とか）。
なので返ってくるN-B個の桁それぞれに対して元の桁の候補をTreeSetとして持っておき、動的計画法的に（合ってるか？）その範囲を狭めていくことで答えを求めた。
public static void main(String[] args) { Scanner sc=new Scanner(); int T=sc.nextInt(); for (int count = 0; count < T; count++) { int n=sc.nextInt(); int b=sc.nextInt(); int f=sc.nextInt(); TreeSet<Integer>[] lists = new TreeSet[n-b]; for (int i = 0; i < lists.length; i++) { lists[i] = new TreeSet<>(); lists[i].addAll(IntStream.range(i,i+16).boxed().collect(Collectors.toSet())); } for (int i = 0; i < f; i++) { StringBuilder token = new StringBuilder(); TreeSet<Integer> zeroSet = new TreeSet<>(); TreeSet<Integer> oneSet = new TreeSet<>(); for (int j = 0; j < n; j++) { if(j%(1<<(i+1))<(1<<i)){ token.append(0); zeroSet.add(j); }else{ token.append(1); oneSet.add(j); } } put(token); final String s=sc.next(); for (int j = 0; j < lists.length; j++) { TreeSet<Integer> useSet=null; if(s.charAt(j)=='0'){ useSet=zeroSet; }else{ useSet=oneSet; } int start=j==0?0:lists[j-1].first()+1; int end=j==lists.length-1?n:lists[j+1].last(); lists[j].retainAll(useSet.subSet(start,end)); } if(Arrays.stream(lists).allMatch(set->set.size()==1))break; } StringBuilder sb = new StringBuilder(); Set<Integer> notB = new HashSet<>(); for(Set<Integer> set:lists){ notB.addAll(set); } for (int j = 0; j < n; j++) { if(!notB.contains(j))sb.append(j+" "); } put(sb); int _=sc.nextInt(); } }
largeのポイントはL=min(15,N-1)なんですね。全然分からんかった。
まとめ
もう一度同じ問題やってDの解法が出てくるかというと微妙。
解けたのも運の要素が大きい。
なので私の実力はA,B,Cのsmallまでといったところだろう。
Round１はまあかなり厳しそう。
いや新社会人で7日連続スーツ出勤最終日にこれだけ解けたんならマシじゃないか？（クソブラック）
すごい眠かったし。
あとQualificationって相談有りなのか。。。
「Round本番からは本気出す」みたいな人出てくるんだろ（自分はこれで精いっぱいだったけれど）
怖すぎる
