n-ari n-ari

AtCoder Beginner Contest 037

結構簡単なセットでした。

A

小さい方で割り算してもいいし、割り算した結果の大きい方を取っても良い。個人的には前者。

入出力の体裁をちゃんとすること。あと「混ぜて買っても意味が無い」という点に気付くこと。

160518div2

入門者向けのセットです。

簡易解説

A : 入出力をしっかり覚えましょう。1行出力したら必ず最後は改行を忘れずに。
B : while文が想定解です。forでも出来なくは無いですがwhileも使い所によっては便利なのでぜひ使えるように。
C : 配列に保存して添字に注意して出力です。末尾に余計な空白は入れないように。
D : ほんの少し実装難。boolの配列で持ってるか持ってないかを保存してfor文で回しましょう。

160518div1

少しアルゴリズミックなことをしています。詳しくは「蟻本」を買うか、ググりましょう。

AtCoder Typical Contestというものがあるのですが、それの第一回・第二回のA問題でDFSとBFSが分かりやすくまとまっています。ぜひ参考にしてください。

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

A: 幅優先探索 - AtCoder Typical Contest 002 | AtCoder

160526

実装系を多めにしてみました。なお今日はJavaで書いてみました。慣れない。

簡易解説

A : 落ち着いて問題文を読んでループを実装
B : 1行入力するメソッドがわかれば(C++:getline, Java:nextLine)、文字を1文字ずつ見るだけ。Javaはsplit(" ")で長さを取るだけ。
C : ソートします。私はクラスを作ってソートしました(Javaの書き方わからない......)

160530 簡易解説

A : 書きます。
B : 剰余を取るといい感じになりそうですね。剰余取って0になった場合がコーナーケース。
C : 24*60通りしか無いのでboolの配列で持って順にアクセスしてもOK。考えられるパターンが多くなったら配列に入れておいてソートする、set(Java:treeset)といった平衡2分探索木を使う、など。
D : 始点と訪問する点をすべて含めた際、Cの形(輪っかの一部が切れてる)の様に訪れるのが最適です。輪っかのどこが切れてるかを全探索し、両端へ行くのにかかる時間をd_l,d_rとすれば、その切り方における最適解は $min(d_l,d_r)*2 + max(d_l,d_r)$ です。
E : 4通りの遷移、たかだか8回で解ける、ということから、4^8通り全探索です。再帰で書くと良さそう。ちなみに、同じ操作を2連続でやっても意味が無いので3^8通りには落とせますね。
F : 難問です。私は「(0,0)から(i,j)までにどれだけ*があるか」という配列を累積和を使うことで求めておいて、「各(i,j)から高さh,幅wで行けるかどうか」を探索していきます。ここで、hを最大、wを1として探索を初めて、(i,j)から(i+w,j+h)までの*のある数が0になるまでhを減らし、0になったら答えを更新、wをインクリメントする、という尺取法みたいな方法を使いました。計算量はO((W+H)WH)ぐらい。
なお、この問題にはO(WH)解法が存在しますが、私はあまり理解していません。以下のリンクを御覧ください。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=496648&tab=2#

160606 簡易解説

A

連続するjの数、oの数、iの数を求めておきます。j>=o<=iならレベルoのJOI列が生成されます。JOIの順に来ないこともあるのでその場合はちゃんとリセットするように。

Beginner's Crypto

Given val such that flag * 2^{10000} mod 10^{175} == val.

From definition of modulus, we get flag * 2^{10000} - k * 10^{175} == val.

Divide by 2^{175}, flag * 2^{10000-175} - k * 5^{175} == val / 2^{175}

	s = """
	エジプトから来ました
	／＼
	／┳┻＼
	／━┻┳┻＼
	／┻┳━┻┳┻＼
	／┳━┻┳━┻┳┻＼
	／━┻━━┻━━／⌒＼＼
	￣￣／　＿＿＿＿／⌒＼⊃
	（　／

	'use strict';

	const songList = [
	{diff: "上級+", rank: "S", LP: 20, point: 875},
	{diff: "上級+", rank: "A", LP: 20, point: 860},
	{diff: "上級+", rank: "B", LP: 20, point: 845},
	{diff: "上級+", rank: "C", LP: 20, point: 830},
	{diff: "上級", rank: "S", LP: 15, point: 600},
	{diff: "上級", rank: "A", LP: 15, point: 581},
	{diff: "上級", rank: "B", LP: 15, point: 562},

	#include <stdio.h>
	#include <algorithm>

	namespace sudoku {
	const char UNKNOWN = '_';
	char board[90];
	void input(){
	for(int row=0; row<9; row++){
	scanf("%s",board + 9*row);
	}